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

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

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

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

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

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

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

Простой граф[править]

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

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

G (V, E) = ⟨ V, E ⟩, V \neq \emptyset, E \subseteq V \times V, {v, v} \notin E, v \in V

,

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

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

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

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

Ребро (линия) (англ. edge, line) графа $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)$ графа;

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

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

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

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

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

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

Степень (валентность) вершины (англ. degree, valency) есть количество инцидентных ей рёбер. Степень вершины обозначается как $d (v)$ ;

Изолированной вершиной (англ. isolated) называется вершина со степенью $d (v) = 0$ , то есть не является концом ни для одного ребра;

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

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

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

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

G (V, E) = ⟨ V, E ⟩, V \neq \emptyset, E \subseteq V \times V

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

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

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

Мультиграф[править]

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

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

G (V, 𝐄) = ⟨ V, 𝐄 ⟩, V \neq \emptyset, 𝐄 \subseteq V \times V {v, v} \notin 𝐄, v \in V

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

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

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

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

G (V, 𝐄) = ⟨ V, 𝐄 ⟩, V \neq \emptyset, 𝐄 \subseteq V \times V

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

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

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

G (V, E) = ⟨ V, E ⟩, V \neq \emptyset, ⟨ {v_{1}, v_{2}}, ≺ ⟩ \in E, v \in V

.

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

i n i t : E \to V, t e r : E \to V

,

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

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

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

G (V, E, U) = ⟨ V, E, U ⟩, V \neq \emptyset, ⟨ {v_{1}, v_{2}}, ≺ ⟩ \in E, {v_{3}, v_{4}} \in U, v \in V

.

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

i n i t : E \to V, t e r : 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}$ так, что не будет рёбер, соединяющих вершины одного и того же подмножества.
полным двудольным, если каждая вершина одного подмножества соединена ребром с каждой вершиной другого подмножества.
планарным, если граф можно изобразить диаграммой на плоскости без пересечений рёбер.
взвешенным, если каждому ребру графа поставлено в соответствие некоторое число, называемое весом ребра.
хордальным, если граф не содержит индуцированных циклов с длиной больше трёх.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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