Граф (математика)

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску
У этого термина существуют и другие значения, см. Граф (значения).
Неориентированный граф с шестью вершинами и семью рёбрами

Графматематическая абстракция реальной системы объектов любой природы, обладающих парными связями. Граф как математический объект есть совокупность двух множеств — множества самих объектов, называемого множеством вершин и множеством их парных связей, называемой множеством рёбер. Элемент множества рёбер есть пара элементов множества вершин.

Графы находят широкое применение в современной науке технике. Они используются и в естественных науках (физике и химии) и в социальных науках (например, социологии), но наибольших масштабов применение графов получило в информатике и сетевых технологиях.

В качестве примера моделируемой графом системы из повседневной жизни можно привести схему перелётов определённой авиакомпании, где вершинами графа являются города, а рёбрами — рейсы, соединяющие пары городов. Дерево каталогов в компьютере также является графом: диски, папки и файлы являются вершинами, а рёбра показывают вложенность файлов и папок в папки и диски[1].

Для разных областей применения виды графов могут различаться направленностью, ограничениями на количество связей и дополнительными данными о вершинах или рёбрах. Многие структуры, представляющие практический интерес в математике и информатике, могут быть представлены графами. Например, строение Википедии можно смоделировать при помощи ориентированного графа, в котором вершины — статьи, а дуги (ориентированные рёбра) — гиперссылки (тематическая карта).

Графы являются основным объектом изучения теории графов.

Определения[править | править код]

Основная статья: Глоссарий теории графов

Реальные системы, элементы которых обладают парными связями достаточно разнообразны, и описывающие их абстракции — графы также бывают различных типов. Простейшей абстракцией таких систем является простой граф.

Простой Граф[править | править код]

Пример диаграммы неориентированного графа

Определение. Простой граф есть совокупность двух множеств – непустого множества и множества неупорядоченных пар различных элементов множества . Множество называется множеством вершин, множество называется множеством рёбер

,

то есть множество состоит из 2-элементных подмножеств множества .

Сопутствующие термины

Теория графов не обладает устоявшейся терминологией. Поэтому в некоторых публикациях могут использоваться термины, отличные от приведенных ниже.

  • Вершина (узел, точка) (англ.  vertex, node, point) графа есть элемент множества вершин ;
  • Ребро (линия) (англ.  edge, line) графа есть элемент множества ребер , или , где ;
  • Элементами графа называются его вершины и рёбра графа;
  • Порядок (англ.  order) графа есть кардинальное число множества вершин или, другими словами, количество вершин;
  • Размер (англ.  size) графа есть кардинальное число множества ребер или, другими словами, количество ребер;
  • Вершина инцидентна (англ. incident) ребру , если ; тогда еще говорят, что есть ребро при ;
  • Концевые вершины (концы) (англ. endvertices, ends) есть две вершины, инцидентные ребру. Ребро соединяет (англ. joins) свои концевые вершины;
  • Соседние (смежные) вершины (англ. neighbours, adjacent) есть такие вершины и что или, другими, словами обе вершины являются концевыми для одного ребра;
  • Смежные ребра (англ. adjacent edges) это ребра, инцидентные одной вершине или и - смежные;
  • Степень (валентность) вершины (англ. degree, valency) есть количество инцидентных ей рёбер. Степень вершины обозначается как ;
  • Изолированной вершиной (англ. isolated) называется вершина со степенью , то есть не является концом ни для одного ребра;
  • Висячей вершиной (листом) (англ. leaf) называется вершина со степенью , то есть которая является концом ровно одного ребра.

Обычно граф изображают диаграммой: вершины – точками, ребра – линиями.

Псевдограф[править | править код]

Псевдограф есть совокупность двух множеств – непустого множества и множества неупорядоченных пар элементов множества .

В множестве ребер псевдографа разрешен элемент .

  • Петлей (англ. loop) называется элемент , являющийся ребром у которого концевые вершины совпадают.

Другими словами если элементами множества E могут быть петли, то граф называется псевдографом [2].

Мультиграф[править | править код]

Псевдомультиграф с кратными рёбрами (красные) и петлями (синие).

Мультиграф есть совокупность двух множеств – непустого множества и мультимножества неупорядоченных пар различных элементов множества .

  • Кратными ребрами называются одинаковые элементы мультимножества , то есть ребра, чьи концевые вершины совпадают.

Другими словами Если не множество, а семейство, то есть если содержит одинаковые элементы, то такие элементы называются кратными рёбрами, а граф называется мультиграфом [2].

Псевдомультиграф[править | править код]

Псевдомультиграф есть совокупность двух множеств – непустого множества и мультимножества неупорядоченных пар элементов множества .

Другими словами Если семейство содержащее одинаковые элементы (кратные ребра) и может содержать петли, то граф называется псевдомультиграфом[2].

Ориентированный граф[править | править код]

Ориентированный граф

Ориентированный граф (орграф) (англ.  directed graph or dirgaph) есть совокупность двух множеств – непустого множества и множества дуг или упорядоченных пар различных элементов множества

.

совместно с двумя отображениями

,

где отображение ставит в соответствие каждой дуге ее начальную вершину (начало дуги) , а отображение ставит в соответствие каждой дуге ее конечную вершину (конец дуги) . Говорят что дуга ведет из в

Смешанный граф[править | править код]

Основная статья: Смешанный граф

Смешанный граф (англ. Mixed graph)  — это совокупность трех множеств – непустого множества вершин , и множества дуг или упорядоченных пар различных элементов множества и множества ребер неупорядоченных пар различных элементов множества

.

совместно с двумя отображениями

Ориентированный и неориентированный графы являются частными случаями смешанного.

Изоморфные графы[править | править код]

Граф называется изоморфным графу , если существует биекция из множества вершин графа в множество вершин графа , обладающая следующим свойством: если в графе есть ребро из вершины в вершину , то в графе должно быть ребро из вершины в вершину и наоборот — если в графе есть ребро из вершины в вершину , то в графе должно быть ребро из вершины в вершину . В случае ориентированного графа эта биекция также должна сохранять ориентацию ребра. В случае взвешенного графа биекция также должна сохранять вес ребра.

Прочие связанные определения[править | править код]

Маршрутом в графе называют конечную последовательность вершин, в которой каждая вершина (кроме последней) соединена со следующей в последовательности вершиной ребром. Цепью называется маршрут без повторяющихся рёбер. Простой цепью называется маршрут без повторяющихся вершин (откуда следует, что в простой цепи нет повторяющихся рёбер).

Ориентированным маршрутом (или путём) в орграфе называют конечную последовательность вершин и дуг, в которой каждый элемент инцидентен предыдущему и последующему.

Циклом называют цепь, в которой первая и последняя вершины совпадают. При этом длиной пути (или цикла) называют число составляющих его рёбер. Заметим, что если вершины и являются концами некоторого ребра, то согласно данному определению, последовательность является циклом. Чтобы избежать таких «вырожденных» случаев, вводят следующие понятия.

Путь (или цикл) называют простым, если рёбра в нём не повторяются; элементарным, если он простой и вершины в нём не повторяются.

Простейшие свойства путей и циклов:

  • всякий путь, соединяющий две вершины, содержит элементарный путь, соединяющий те же две вершины;
  • всякий простой неэлементарный путь содержит элементарный цикл;
  • всякий простой цикл, проходящий через некоторую вершину (или ребро), содержит элементарный (под-)цикл, проходящий через ту же вершину (или ребро);
  • петля — элементарный цикл.

Бинарное отношение на множестве вершин графа, заданное как «существует путь из в », является отношением эквивалентности и, следовательно, разбивает это множество на классы эквивалентности, называемые компонентами связности графа. Если у графа ровно одна компонента связности, то граф связный. На компоненте связности можно ввести понятие расстояния между вершинами как минимальную длину пути, соединяющего эти вершины.

Всякий максимальный связный подграф графа называется связной компонентой (или просто компонентой) графа . Слово «максимальный» означает максимальный относительно включения, то есть не содержащийся в связном подграфе с большим числом элементов.

Ребро графа называется мостом, если его удаление увеличивает число компонент.

Дополнительные характеристики графов[править | править код]

Граф называется:

  • связным, если для любых вершин , есть путь из в .
  • сильно связным или ориентированно связным, если он ориентированный, и из любой вершины в любую другую имеется ориентированный путь.
  • деревом, если он связный и не содержит нетривиальных циклов.
  • полным, если любые его две (различные, если не допускаются петли) вершины соединены ребром.
  • двудольным, если его вершины можно разбить на два непересекающихся подмножества и так, что всякое ребро соединяет вершину из с вершиной из .
  • k-дольным, если его вершины можно разбить на непересекающихся подмножеств , , …, так, что не будет рёбер, соединяющих вершины одного и того же подмножества.
  • полным двудольным, если каждая вершина одного подмножества соединена ребром с каждой вершиной другого подмножества.
  • планарным, если граф можно изобразить диаграммой на плоскости без пересечений рёбер.
  • взвешенным, если каждому ребру графа поставлено в соответствие некоторое число, называемое весом ребра.
  • хордальным, если граф не содержит индуцированных циклов с длиной больше трёх.

Также бывает:

Обобщение понятия графа[править | править код]

Простой граф является одномерным симплициальным комплексом.

Более абстрактно, граф можно задать как тройку , где и  — некоторые множества (вершин и рёбер, соотв.), а  — функция инцидентности (или инцидентор), сопоставляющая каждому ребру (упорядоченную или неупорядоченную) пару вершин и из (его концов). Частными случаями этого понятия являются:

  • ориентированные графы (орграфы) — когда всегда является упорядоченной парой вершин;
  • неориентированные графы — когда всегда является неупорядоченной парой вершин;
  • смешанные графы — граф, в котором встречаются как ориентированные, так и неориентированные рёбра и петли;
  • эйлеровы графы — граф, в котором существует циклический эйлеров путь (эйлеров цикл);
  • мультиграфы — графы с кратными рёбрами, имеющими своими концами одну и ту же пару вершин;
  • псевдографы — это мультиграфы, допускающие наличие петель;
  • простые графы — не имеющие петель и кратных рёбер.

Под данное выше определение не подходят некоторые другие обобщения:

Способы представления графа в информатике[править | править код]

Матрица смежности[править | править код]

Основная статья: Матрица смежности

Таблица, где как столбцы, так и строки соответствуют вершинам графа. В каждой ячейке этой матрицы записывается число, определяющее наличие связи от вершины-строки к вершине-столбцу (либо наоборот).

Это наиболее удобный способ представления плотных графов.

Недостатком являются требования к памяти, прямо пропорциональные квадрату количества вершин.

  • Двумерный массив;
  • Матрица с пропусками;
  • Неявное задание (при помощи функции).

Матрица инцидентности[править | править код]

Основная статья: Матрица инцидентности

Таблица, где строки соответствуют вершинам графа, а столбцы соответствуют связям (рёбрам) графа. В ячейку матрицы на пересечении строки со столбцом записывается:

1
в случае, если связь «выходит» из вершины ,
−1,
если связь «входит» в вершину,
0
во всех остальных случаях (то есть если связь является петлёй или связь не инцидентна вершине)

Данный способ является довольно ёмким (размер пропорционален ) для хранения, поэтому применяется очень редко, в особых случаях (например, для быстрого нахождения циклов в графе).

Список смежности[править | править код]

Основная статья: Список смежности

Список, где каждой вершине графа соответствует строка, в которой хранится список смежных вершин. Такая структура данных не является таблицей в обычном понимании, а представляет собой «список списков».

Размер занимаемой памяти: .

Это наиболее удобный способ для представления разреженных графов, а также при реализации базовых алгоритмов обхода графа в ширину или глубину, где нужно быстро получать «соседей» текущей просматриваемой вершины.

Список рёбер[править | править код]

Список, где каждому ребру графа соответствует строка, в которой хранятся две вершины, инцидентные ребру.

Размер занимаемой памяти: .

Это наиболее компактный способ представления графов, поэтому часто применяется для внешнего хранения или обмена данными.

Языки описания и программы построения графов[править | править код]

Языки описания[править | править код]

Для описания графов, пригодного для машинной обработки и одновременно удобного для человеческого восприятия, используется несколько стандартизированных языков, среди которых:

Программы для построения[править | править код]

Разработана серия коммерческих программ для построения графов, так, построение графов лежит в основе прикладных программных пакетов фирмы ILOG (с 2009 года принадлежит корпорации IBM), среди других программ — GoView, Lassalle AddFlow, LEDA (есть бесплатная редакция).

Также существует свободная программа для построения графов igraph и свободная библиотека Boost.

Программы для визуализации[править | править код]

Для визуализации графов применяются следующие программные средства:

  • Graphviz (Eclipse Public License)
  • LION Graph Visualizer.
  • Графоанализатор — русскоязычная программа, с простым пользовательским интерфейсом (GNU LGPL; только для Windows).
  • Gephi — графическая оболочка для представления и изучения графов (GNU GPL, CDDL).
  • Библиотека GraphX — свободная библиотека для .NET для расчёта и отрисовки графов, использует WPF 4.0.
  • Библиотека MSAGL — свободная библиотека для .NET[3].

См. также[править | править код]

Примечания[править | править код]

  1. Буркатовская, 2014, с. 3.
  2. 1 2 3 Буркатовская, 2014, с. 6.
  3. Microsoft Automatic Graph Layout - Microsoft Research. research.microsoft.com. Дата обращения: 15 ноября 2015.

Литература[править | править код]

  • Буркатовския Ю. Б. Теория графов. — Томск: Издательство Томского политехнического университета, 2014. — Т. 1. — 200 с.
  • Дистель Р. Теория графов. — Новосибирск: Издательство Института математики им. С. Л. Соболева СО РАН, 2002. — 336 с. — ISBN 5-86134-101-Х.
  • Емеличев В. А., Мельников О. И., Сарванов В. И., Тышкевич Р. И. Лекции по теории графов. М.: Наука, 1990. 384с. (Изд.2, испр. М.: УРСС, 2009. 392 с.)
  • Касьянов В. Н., Евстигнеев В.А. Графы в программировании: обработка, визуализация и применение. — СПб.: БХВ-Петербург, 2003. — С. 1104. — ISBN 5-94157-184-4.
  • Кирсанов М. Н. Графы в Maple. — М.: Физматлит, 2007. — 168 с. — ISBN 978-5-9221-0745-7.
  • Кормен Т. М. и др. Часть VI. Алгоритмы для работы с графами // Алгоритмы: построение и анализ = Introduction to Algorithms. — 2-е изд. — М.: Вильямс, 2006. — С. 1296. — ISBN 0-07-013151-1.
  • Оре О. Теория графов. — М.: Наука, 1968. — 336 с.
  • Графы // Энциклопедический словарь юного математика / Сост. А. П. Савин. — М.: Педагогика, 1985. — С. 86-88. — 352 с.
  • Салий В. Н., Богомолов А. М. Алгебраические основы теории дискретных систем. — М.: Физико-математическая литература, 1997. — ISBN 5-02-015033-9.
  • Уилсон Р. Введение в теорию графов. — М.: Мир, 1977. — 208 с.
  • Харари Ф. Теория графов. — М.: Мир, 1973.