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

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

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

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

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

Определения

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

Простой граф

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

Определение. Простой граф [math]\displaystyle{ G(V,E) }[/math] есть совокупность двух множеств – непустого множества [math]\displaystyle{ V }[/math] и множества [math]\displaystyle{ E }[/math] неупорядоченных пар различных элементов множества [math]\displaystyle{ V }[/math] . Множество [math]\displaystyle{ V }[/math] называется множеством вершин, множество [math]\displaystyle{ E }[/math] называется множеством рёбер

[math]\displaystyle{ G(V,E) = \left \langle V,E \right \rangle, \quad V \ne \varnothing , \quad E \subseteq V \times V , \quad \left \{ v,v \right \} \notin E, \quad v \in V }[/math],

то есть множество [math]\displaystyle{ E }[/math] состоит из 2-элементных подмножеств множества [math]\displaystyle{ V }[/math].

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

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

Вершина (узел, точка) (англ. vertex, node, point) графа [math]\displaystyle{ G }[/math] есть элемент множества вершин [math]\displaystyle{ v \in V(G) }[/math];

Ребро (линия) (англ. edge, line) графа [math]\displaystyle{ G }[/math] есть элемент множества ребер [math]\displaystyle{ e \in E(G) }[/math], или [math]\displaystyle{ e = \left \{ v_1, v_2 \right \} }[/math], где [math]\displaystyle{ v_1 \in V(G), \quad v_2 \in V(G) }[/math];

Элементами графа [math]\displaystyle{ G }[/math] называются его вершины [math]\displaystyle{ v \in V(G) }[/math] и рёбра [math]\displaystyle{ e \in E(G) }[/math] графа;

Порядок (англ. order) графа [math]\displaystyle{ G }[/math] есть кардинальное число множества вершин [math]\displaystyle{ n = |V(G)| }[/math] или, другими словами, количество вершин;

Размер (англ. size) графа [math]\displaystyle{ G }[/math] есть кардинальное число множества ребер [math]\displaystyle{ m = |E(G)| }[/math] или, другими словами, количество ребер;

Вершина [math]\displaystyle{ v }[/math] инцидентна (англ. incident) ребру [math]\displaystyle{ e }[/math], если [math]\displaystyle{ v \in e }[/math]; тогда еще говорят, что [math]\displaystyle{ e }[/math] есть ребро при [math]\displaystyle{ v }[/math];

Концевые вершины (концы) (англ. endvertices, ends) есть две вершины, инцидентные ребру. Ребро соединяет (англ. joins) свои концевые вершины;

Соседние (смежные) вершины (англ. neighbours, adjacent) есть такие вершины [math]\displaystyle{ v_1 }[/math] и [math]\displaystyle{ v_2 }[/math] что [math]\displaystyle{ \left \{v_1, v_2 \right \} \in E(G) }[/math] или, другими, словами обе вершины являются концевыми для одного ребра;

Смежные ребра (англ. adjacent edges) это ребра, инцидентные одной вершине или [math]\displaystyle{ e_1=\left \{ v,v_1 \right \} }[/math] и [math]\displaystyle{ e_2=\left \{ v,v_2 \right \} }[/math] - смежные;

Степень (валентность) вершины (англ. degree, valency) есть количество инцидентных ей рёбер. Степень вершины обозначается как [math]\displaystyle{ d(v) }[/math];

Изолированной вершиной (англ. isolated) называется вершина со степенью [math]\displaystyle{ d(v)=0 }[/math] , то есть не является концом ни для одного ребра;

Висячей вершиной (листом) (англ. leaf) называется вершина со степенью [math]\displaystyle{ d(v)=1 }[/math], то есть которая является концом ровно одного ребра.

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

Псевдограф

Псевдограф [math]\displaystyle{ G(V,E) }[/math] есть совокупность двух множеств – непустого множества [math]\displaystyle{ V }[/math] и множества [math]\displaystyle{ E }[/math] неупорядоченных пар элементов множества [math]\displaystyle{ V }[/math].

[math]\displaystyle{ G(V,E) = \left \langle V,E \right \rangle, \quad V \ne \varnothing , \quad E \subseteq V \times V }[/math]

В множестве ребер псевдографа разрешен элемент [math]\displaystyle{ \left \{ v,v \right \} \in E(G) }[/math].

Петлёй (англ. loop) называется элемент [math]\displaystyle{ e=\left\{v,v \right \} }[/math], являющийся ребром, у которого концевые вершины совпадают.

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

Мультиграф

Мультиграф [math]\displaystyle{ G(V,\mathbf E) }[/math] есть совокупность двух множеств – непустого множества [math]\displaystyle{ V }[/math] и мультимножества [math]\displaystyle{ \mathbf E }[/math] неупорядоченных пар различных элементов множества [math]\displaystyle{ V }[/math].

[math]\displaystyle{ G(V,\mathbf E) = \left \langle V, \mathbf E \right \rangle, \quad V \ne \varnothing , \quad \mathbf E \subseteq V \times V \quad \left \{ v,v \right \} \notin \mathbf E, \quad v \in V }[/math]

Кратными рёбрами называются одинаковые элементы мультимножества [math]\displaystyle{ \left \{e,e, \dots ,e \right \} \in \mathbf E }[/math], то есть ребра, чьи концевые вершины совпадают.

Другими словами Если [math]\displaystyle{ E }[/math] не множество, а семейство, то есть если [math]\displaystyle{ \mathbf E }[/math] содержит одинаковые элементы, то такие элементы называются кратными рёбрами, а граф называется мультиграфом ^[2].

Псевдомультиграф

Псевдомультиграф [math]\displaystyle{ G(V,\mathbf E) }[/math] есть совокупность двух множеств – непустого множества [math]\displaystyle{ V }[/math] и мультимножества [math]\displaystyle{ \mathbf E }[/math] неупорядоченных пар элементов множества [math]\displaystyle{ V }[/math].

[math]\displaystyle{ G(V,\mathbf E) = \left \langle V, \mathbf E \right \rangle, \quad V \ne \varnothing , \quad \mathbf E \subseteq V \times V }[/math]

Другими словами Если [math]\displaystyle{ \mathbf E }[/math] семейство содержащее одинаковые элементы (кратные ребра) и [math]\displaystyle{ \mathbf E }[/math] может содержать петли, то граф называется псевдомультиграфом^[2].

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

Ориентированный граф (орграф) (англ. directed graph or dirgaph) [math]\displaystyle{ G(V,E) }[/math] есть совокупность двух множеств – непустого множества [math]\displaystyle{ V }[/math] и множества [math]\displaystyle{ E }[/math] дуг или упорядоченных пар различных элементов множества [math]\displaystyle{ V }[/math]

[math]\displaystyle{ G(V,E) = \left \langle V,E \right \rangle, \quad V \ne \varnothing , \quad \left \langle \left \{ v_1,v_2 \right \}, \prec \right \rangle \in E, \quad v \in V }[/math].

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

[math]\displaystyle{ init: E \rightarrow V, \quad ter: E \rightarrow V }[/math],

где отображение [math]\displaystyle{ init: E \rightarrow V }[/math] ставит в соответствие каждой дуге ее начальную вершину (начало дуги) [math]\displaystyle{ init(e) }[/math], а отображение [math]\displaystyle{ ter: E \rightarrow V }[/math] ставит в соответствие каждой дуге ее конечную вершину (конец дуги) [math]\displaystyle{ ter(e) }[/math]. Говорят что дуга [math]\displaystyle{ e }[/math] ведет из [math]\displaystyle{ init(e) }[/math] в [math]\displaystyle{ ter(e) }[/math]

Смешанный граф

Смешанный граф (англ. Mixed graph) [math]\displaystyle{ G(V,E,U) }[/math] — это совокупность трех множеств – непустого множества вершин [math]\displaystyle{ V }[/math], и множества дуг [math]\displaystyle{ E }[/math] или упорядоченных пар различных элементов множества [math]\displaystyle{ V }[/math] и множества ребер [math]\displaystyle{ U }[/math] неупорядоченных пар различных элементов множества [math]\displaystyle{ V }[/math]

[math]\displaystyle{ G(V,E,U) = \left \langle V,E,U \right \rangle, \quad V \ne \varnothing , \quad \left \langle \left \{ v_1,v_2 \right \}, \prec \right \rangle \in E, \quad \left \{ v_3 , v_4 \right \} \in U , \quad v \in V }[/math].

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

[math]\displaystyle{ init: E \rightarrow V, \quad ter: E \rightarrow V }[/math]

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

Изоморфные графы

Граф [math]\displaystyle{ G }[/math] называется изоморфным графу [math]\displaystyle{ H }[/math], если существует биекция [math]\displaystyle{ f }[/math] из множества вершин графа [math]\displaystyle{ G }[/math] в множество вершин графа [math]\displaystyle{ H }[/math], обладающая следующим свойством: если в графе [math]\displaystyle{ G }[/math] есть ребро из вершины [math]\displaystyle{ A }[/math] в вершину [math]\displaystyle{ B }[/math], то в графе [math]\displaystyle{ H }[/math] должно быть ребро из вершины [math]\displaystyle{ f(A) }[/math] в вершину [math]\displaystyle{ f(B) }[/math] и наоборот — если в графе [math]\displaystyle{ H }[/math] есть ребро из вершины [math]\displaystyle{ A }[/math] в вершину [math]\displaystyle{ B }[/math], то в графе [math]\displaystyle{ G }[/math] должно быть ребро из вершины [math]\displaystyle{ f^{-1}(A) }[/math] в вершину [math]\displaystyle{ f^{-1}(B) }[/math]. В случае ориентированного графа эта биекция также должна сохранять ориентацию ребра. В случае взвешенного графа биекция также должна сохранять вес ребра.

Прочие связанные определения

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

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

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

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

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

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

Бинарное отношение на множестве вершин графа, заданное как «существует путь из [math]\displaystyle{ u }[/math] в [math]\displaystyle{ v }[/math]», является отношением эквивалентности и, следовательно, разбивает это множество на классы эквивалентности, называемые компонентами связности графа. Если у графа ровно одна компонента связности, то граф связный. На компоненте связности можно ввести понятие расстояния между вершинами как минимальную длину пути, соединяющего эти вершины.

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

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

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

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

связным, если для любых вершин [math]\displaystyle{ u }[/math],[math]\displaystyle{ v }[/math] есть путь из [math]\displaystyle{ u }[/math] в [math]\displaystyle{ v }[/math].
сильно связным или ориентированно связным, если он ориентированный, и из любой вершины в любую другую имеется ориентированный путь.
деревом, если он связный и не содержит нетривиальных циклов.
полным, если любые его две (различные, если не допускаются петли) вершины соединены ребром.
двудольным, если его вершины можно разбить на два непересекающихся подмножества [math]\displaystyle{ V_1 }[/math] и [math]\displaystyle{ V_2 }[/math] так, что всякое ребро соединяет вершину из [math]\displaystyle{ V_1 }[/math] с вершиной из [math]\displaystyle{ V_2 }[/math].
k-дольным, если его вершины можно разбить на [math]\displaystyle{ k }[/math] непересекающихся подмножеств [math]\displaystyle{ V_1 }[/math], [math]\displaystyle{ V_2 }[/math], …, [math]\displaystyle{ V_k }[/math] так, что не будет рёбер, соединяющих вершины одного и того же подмножества.
полным двудольным, если каждая вершина одного подмножества соединена ребром с каждой вершиной другого подмножества.
планарным, если граф можно изобразить диаграммой на плоскости без пересечений рёбер.
взвешенным, если каждому ребру графа поставлено в соответствие некоторое число, называемое весом ребра.
хордальным, если граф не содержит индуцированных циклов с длиной больше трёх.

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

Обобщение понятия графа

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

Более абстрактно, граф можно задать как тройку [math]\displaystyle{ (V, E, \varphi) }[/math], где [math]\displaystyle{ V }[/math] и [math]\displaystyle{ E }[/math] — некоторые множества (вершин и рёбер, соотв.), а [math]\displaystyle{ \varphi }[/math] — функция инцидентности (или инцидентор), сопоставляющая каждому ребру [math]\displaystyle{ e\in E }[/math] (упорядоченную или неупорядоченную) пару вершин [math]\displaystyle{ u }[/math] и [math]\displaystyle{ v }[/math] из [math]\displaystyle{ V }[/math] (его концов). Частными случаями этого понятия являются:

эйлеровы графы — граф, в котором существует циклический эйлеров путь (эйлеров цикл);

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

Матрица смежности

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

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

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

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

Матрица инцидентности

Таблица, где строки соответствуют вершинам графа, а столбцы соответствуют связям (рёбрам) графа. В ячейку матрицы на пересечении строки [math]\displaystyle{ i }[/math] со столбцом [math]\displaystyle{ j }[/math] записывается:

1: в случае, если связь [math]\displaystyle{ j }[/math] «выходит» из вершины [math]\displaystyle{ i }[/math],
−1,: если связь «входит» в вершину,
0: во всех остальных случаях (то есть если связь является петлёй или связь не инцидентна вершине)

Данный способ является довольно ёмким (размер пропорционален [math]\displaystyle{ |V| |E| }[/math]) для хранения, поэтому применяется очень редко, в особых случаях (например, для быстрого нахождения циклов в графе).

Список смежности

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

Размер занимаемой памяти: [math]\displaystyle{ O(|V|+|E|) }[/math].

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

Список рёбер

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

Размер занимаемой памяти: [math]\displaystyle{ O(|E|) }[/math].

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

Языки описания и программы построения графов

Языки описания

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

Программы для построения

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

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

Программы для визуализации

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

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

См. также

Примечания

↑ Буркатовская, 2014, с. 3.
↑ ^2,0 ^2,1 ^2,2 Буркатовская, 2014, с. 6.
↑ Microsoft Automatic Graph Layout - Microsoft Research (неопр.). research.microsoft.com. Дата обращения: 15 ноября 2015. Архивировано 14 мая 2012 года.

Литература

Буркатовския Ю. Б. Теория графов. — Томск: Издательство Томского политехнического университета, 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.

[_e500f9b3a8f5534e-1] Буркатовская, 2014, с. 3.

[_e500f9b3a8f5534b-2] 2,0 ^2,1 ^2,2 Буркатовская, 2014, с. 6.

[3] Microsoft Automatic Graph Layout - Microsoft Research (неопр.). research.microsoft.com. Дата обращения: 15 ноября 2015. Архивировано 14 мая 2012 года.

[1]

[2]

[3]