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

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

Граф — основной объект изучения математической теории графов, совокупность непустого множества вершин и наборов пар вершин (связей между вершинами).

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

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

Определения

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

Граф

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

$V$ (а значит и, $E$, иначе оно было бы мультимножеством) обычно считаются конечными множествами. Многие результаты, полученные для конечных графов, неверны (или каким-либо образом отличаются) для бесконечных графов, поскольку не все утверждения, имеющие место для конечных совокупностей, выполняются в случае бесконечных множеств.

Вершины и рёбра графа называются также элементами графа, число вершин в графе $|V|$ — порядком, число рёбер $|E|$ — размером графа.

Вершины $u$ и $v$ называются концевыми вершинами (или просто концами) ребра $e=\{u,v\}$. Ребро, в свою очередь, соединяет эти вершины. Две концевые вершины одного и того же ребра называются соседними.

Два ребра называются смежными, если они имеют общую концевую вершину.

Два ребра называются кратными, если множества их концевых вершин совпадают.

Ребро называется петлёй, если его концы совпадают, то есть $e=\{v,v\}$.

Степенью $\deg V$ вершины $V$ называют количество инцидентных ей рёбер (при этом петли считают дважды).

Вершина называется изолированной, если она не является концом ни для одного ребра; висячей (или листом), если она является концом ровно одного ребра.

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

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

Дуга — это упорядоченная пара вершин $(v, w)$, где вершину $v$ называют началом, а $w$ — концом дуги. Можно сказать, что дуга $v \to w$ ведёт от вершины $v$ к вершине $w$.

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

Смешанный граф $G$ — это граф, в котором некоторые рёбра могут быть ориентированными, а некоторые — неориентированными. Записывается упорядоченной тройкой $G := (V, E, A)$, где $V$, $E$ и $A$ определены так же, как выше.

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

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

Граф $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, \varphi)$, где $V$ и $E$ — некоторые множества (вершин и рёбер, соотв.), а $\varphi$ — функция инцидентности (или инцидентор), сопоставляющая каждому ребру $e\in E$ (упорядоченную или неупорядоченную) пару вершин $u$ и $v$ из $V$ (его концов). Частными случаями этого понятия являются:

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

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

• гиперграф — если ребро может соединять более двух вершин.
• ультраграф — если между элементами $x_i$ и $u_j$ существуют бинарные отношения инцидентности.

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

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

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

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

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

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

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

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

1

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

−1,

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

0

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

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

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

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

Размер занимаемой памяти: $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).
• Библиотека GraphX — свободная библиотека для .NET для расчёта и отрисовки графов, использует WPF 4.0.

См. также

• Прямое произведение графов
• Объектный граф

Литература

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