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

Неориентированный граф с шестью вершинами и семью рёбрами

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

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

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

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

Определения

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

Простой граф

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

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

$G(V,E)=⟨V,E⟩,V\ne \varnothing ,E\subseteq V\times V,\{v,v\}\notin E,v\in V$,

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

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

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

• Вершина (узел, точка) (Шаблон:Lang-en) графа $G$ есть элемент множества вершин $v\in V(G)$;
• Ребро (линия) (Шаблон:Lang-en) графа $G$ есть элемент множества ребер $e\in E(G)$, или $e=\{v_1,v_2\}$, где $v_1\in V(G),v_2\in V(G)$;
• Элементами графа $G$ называются его вершины $v\in V(G)$ и рёбра $e\in E(G)$ графа;
• Порядок (Шаблон:Lang-en) графа $G$ есть кардинальное число множества вершин $n=|V(G)|$ или, другими словами, количество вершин;
• Размер (Шаблон:Lang-en) графа $G$ есть кардинальное число множества ребер $m=|E(G)|$ или, другими словами, количество ребер;
• Вершина $v$ инцидентна (Шаблон:Lang-en) ребру $e$, если $v\in e$; тогда еще говорят, что $e$ есть ребро при $v$;
• Концевые вершины (концы) (Шаблон:Lang-en) есть две вершины, инцидентные ребру. Ребро соединяет (Шаблон:Lang-en) свои концевые вершины;
• Соседние (смежные) вершины (Шаблон:Lang-en) есть такие вершины $v_1$ и $v_2$ что $\{v_1,v_2\}\in E(G)$ или, другими, словами обе вершины являются концевыми для одного ребра;
• Смежные ребра (Шаблон:Lang-en) это ребра, инцидентные одной вершине или $e_1=\{v,v_1\}$ и $e_2=\{v,v_2\}$ — смежные;
• Степень (валентность) вершины (Шаблон:Lang-en) $𝑑\left(v\right)$ есть количество инцидентных ей рёбер.
• Изолированной вершиной (Шаблон:Lang-en) называется вершина со степенью $d(v)=0$ , то есть не является концом ни для одного ребра;
• Висячей вершиной (листом) (Шаблон:Lang-en) называется вершина со степенью $d(v)=1$, то есть которая является концом ровно одного ребра.

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

Псевдограф

Псевдограф $G(V,E)$ есть совокупность двух множеств — непустого множества $V$ и множества $E$ неупорядоченных пар элементов множества $V$.

$G(V,E)=⟨V,E⟩,V\ne \varnothing ,E\subseteq V\times V$

В множестве ребер псевдографа разрешен элемент $\{v,v\}\in E(G)$.

• Петлёй (Шаблон:Lang-en) называется элемент $e=\{v,v\}$, являющийся ребром, у которого концевые вершины совпадают.

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

Мультиграф

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

Мультиграф $G(V,𝐄)$ есть совокупность двух множеств — непустого множества $V$ и мультимножества $𝐄$ неупорядоченных пар различных элементов множества $V$.

$G(V,𝐄)=⟨V,𝐄⟩,V\ne \varnothing ,𝐄\subseteq V\times V\{v,v\}\notin 𝐄,v\in V$

• Кратными рёбрами называются одинаковые элементы мультимножества $\{e,e,\dots ,e\}\in 𝐄$, то есть ребра, чьи концевые вершины совпадают.

Другими словами Если $E$ не множество, а семейство, то есть если $𝐄$ содержит одинаковые элементы, то такие элементы называются кратными рёбрами, а граф называется мультиграфом Шаблон:Sfn.

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

Псевдомультиграф $G(V,𝐄)$ есть совокупность двух множеств — непустого множества $V$ и мультимножества $𝐄$ неупорядоченных пар элементов множества $V$.

$G(V,𝐄)=⟨V,𝐄⟩,V\ne \varnothing ,𝐄\subseteq V\times V$

Другими словами, если $𝐄$ — семейство, содержащее одинаковые элементы (кратные ребра), и $𝐄$ может содержать петли, то граф называется псевдомультиграфомШаблон:Sfn.

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

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

Ориентированный граф (орграф) (Шаблон:Lang-en) $G(V,E)$ есть совокупность двух множеств — непустого множества $V$ и множества $E$ дуг или упорядоченных пар различных элементов множества $V$

$G(V,E)=⟨V,E⟩,V\ne \varnothing ,⟨\{v_1,v_2\},\prec ⟩\in E,v\in V$.

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

$init:E\to V,ter:E\to V$,

где отображение $init:E\to V$ ставит в соответствие каждой дуге ее начальную вершину (начало дуги) $init(e)$, а отображение $ter:E\to V$ ставит в соответствие каждой дуге ее конечную вершину (конец дуги) $ter(e)$. Говорят что дуга $e$ ведет из $init(e)$ в $ter(e)$

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

Шаблон:Main Смешанный граф (Шаблон:Lang-en) $G(V,E,U)$ — это совокупность трех множеств — непустого множества вершин $V$, и множества дуг $E$ или упорядоченных пар различных элементов множества $V$ и множества ребер $U$ неупорядоченных пар различных элементов множества $V$

$G(V,E,U)=⟨V,E,U⟩,V\ne \varnothing ,⟨\{v_1,v_2\},\prec ⟩\in E,\{v_3,v_4\}\in U,v\in V$.

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

$init:E\to V,ter:E\to V$

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

• k-раскрашиваемым
• k-хроматическим

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

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

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

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

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

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

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

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

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

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

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

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

1

в случае, если связь $j$ «выходит» из вершины $i$,

−1,

если связь «входит» в вершину,

0

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

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

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

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

Размер занимаемой памяти: $O(|V|+|E|)$.

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

Список рёбер

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

Размер занимаемой памяти: $O(|E|)$.

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

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

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

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

• DOT
• GraphML
• Trivial Graph Format
• GML
• GXL
• XGMML
• DGML

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

Разработана серия коммерческих программ для построения графов, так, построение графов лежит в основе прикладных программных пакетов фирмы 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.

См. также

• Прямое произведение графов
• Граф (тип данных)
• Графовая база данных

Литература

• Шаблон:Книга
• Шаблон:Книга
• Емеличев В. А., Мельников О. И., Сарванов В. И., Тышкевич Р. И. Лекции по теории графов. М.: Наука, 1990. 384с. (Изд.2, испр. М.: УРСС, 2009. 392 с.)
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга