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

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

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

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

Определения

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

Простой граф

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

${\displaystyle G(V,E)=\left\langle V,E\right\rangle ,\quad V\neq \varnothing ,\quad E\subseteq V\times V,\quad \left\{v,v\right\}\notin E,\quad v\in V}$ ,

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

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

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

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

• Ребро (линия) ( англ. edge, line) графа ${\displaystyle G}$ есть элемент множества ребер ${\displaystyle e\in E(G)}$ , или ${\displaystyle e=\left\{v_{1},v_{2}\right\}}$ , где ${\displaystyle v_{1}\in V(G),\quad v_{2}\in V(G)}$ ;

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

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

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

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

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

• Соседние (смежные) вершины ( англ. neighbours, adjacent) есть такие вершины ${\displaystyle v_{1}}$ и ${\displaystyle v_{2}}$ что ${\displaystyle \left\{v_{1},v_{2}\right\}\in E(G)}$ или, другими, словами обе вершины являются концевыми для одного ребра;

• Смежные ребра ( англ. adjacent edges) это ребра, инцидентные одной вершине или ${\displaystyle e_{1}=\left\{v,v_{1}\right\}}$ и ${\displaystyle e_{2}=\left\{v,v_{2}\right\}}$ - смежные;

• Степень (валентность) вершины ( англ. degree, valency) ${\displaystyle \operatorname {\mathit {d}} \left(v\right)}$ есть количество инцидентных ей рёбер.
• Изолированной вершиной ( англ. isolated) называется вершина со степенью ${\displaystyle d(v)=0}$ , то есть не является концом ни для одного ребра;

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

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

Псевдограф

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

${\displaystyle G(V,E)=\left\langle V,E\right\rangle ,\quad V\neq \varnothing ,\quad E\subseteq V\times V}$

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

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

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

Мультиграф

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

${\displaystyle G(V,\mathbf {E})=\left\langle V,\mathbf {E} \right\rangle ,\quad V\neq \varnothing ,\quad \mathbf {E} \subseteq V\times V\quad \left\{v,v\right\}\notin \mathbf {E} ,\quad v\in V}$

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

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

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

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

${\displaystyle G(V,\mathbf {E})=\left\langle V,\mathbf {E} \right\rangle ,\quad V\neq \varnothing ,\quad \mathbf {E} \subseteq V\times V}$

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

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

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

${\displaystyle G(V,E)=\left\langle V,E\right\rangle ,\quad V\neq \varnothing ,\quad \left\langle \left\{v_{1},v_{2}\right\},\prec \right\rangle \in E,\quad v\in V}$ .

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

${\displaystyle init:E\rightarrow V,\quad ter:E\rightarrow V}$ ,

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

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

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

${\displaystyle G(V,E,U)=\left\langle V,E,U\right\rangle ,\quad V\neq \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}$ .

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

${\displaystyle init:E\rightarrow V,\quad ter:E\rightarrow V}$

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1

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

−1,

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

0

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

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

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

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

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

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

Список рёбер

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

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

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

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

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

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

• DOT
• GraphML
• Trivial Graph Format

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

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

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

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

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

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

См. также

• Прямое произведение графов
• ^*

Примечания

Литература

• Буркатовския Ю. Б. Теория графов. — Томск: Издательство Томского политехнического университета, 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. — С. -88. — 352 с.
• Салий В. Н., Богомолов А. М. Алгебраические основы теории дискретных систем. — М. : Физико-математическая литература, 1997. — ISBN 5-02-015033-9 .
• Уилсон Р. Введение в теорию графов. — М. : Мир, 1977. — 208 с.
• Харари Ф. Теория графов. — М. : Мир, 1973.