Основные определения теории графов

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

Определение:

Ориентированным графом (directed graph) [math]G[/math] называется пара [math]G = (V, E)[/math], где [math]V[/math] — конечное множество вершин, а [math] E \subset V \times V [/math] — множество рёбер.

Определение:

Ребром (edge, дугой (arc), линией (line)) ориентированного графа называют упорядоченную пару вершин [math] (v, u) \in E [/math].

В графе ребро, концы которого совпадают, то есть [math]e=(v,v)[/math], называется петлей. Мультиграф с петлями принято называть псевдографом.

Если имеется ребро [math] (v, u) \in E [/math], то говорят:

• [math] v [/math] — предок [math] u [/math].
• [math] u [/math] и [math] v [/math] — смежные
• Вершина [math] u [/math] инцидентна ребру [math] (v, u) [/math]
• Вершина [math] v [/math] инцидентна ребру [math] (v, u) [/math]

Инцидентность — понятие, используемое только в отношении ребра и вершины. Две вершины или два ребра не могут быть инцидентны.

Граф с [math] p [/math] вершинами и [math] q [/math] ребрами называют [math] (p, q) [/math] - графом. [math] (1, 0) [/math]-граф называют тривиальным.

Заметим, что по определению ориентированного графа, данному выше, любые две вершины [math]u,~v[/math] нельзя соединить более чем одним ребром [math](u, v)[/math]. Поэтому часто используют другое определение.

Определение:

Ориентированным графом [math]G[/math] называется четверка [math]G = (V, E, beg, end)[/math] , где [math]beg, end : E \rightarrow V [/math], а [math]V[/math] и [math]E[/math] — некоторые абстрактные множества.

Иногда граф, построенный таким образом, называют мультиграфом. В мультиграфе не допускаются петли, но пары вершин допускается соединять более чем одним ребром. Такие ребра называются кратными (иначе — параллельные).

Красным выделено кратное ребро (6, 2) Синим обозначена петля (6, 6)

Мультиграф

Псевдограф

Также для ориентированных графов определяют полустепень исхода вершины [math]deg^-v_i = |\{e~|~beg~e = v_i\}|[/math] и полустепень захода вершины [math]deg^+v_i = |\{e~|~end~e = v_i\}|[/math].

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

Определение:

Путём (маршрутом) в графе называется последовательность вида [math]v_0 e_1 v_1 ... e_k v_k[/math], где [math]e_i \in E,~e_i = (v_{i-1}, v_i)[/math]; [math]k[/math] — длина пути.

Определение:

Циклическим путём называется путь, в котором [math]v_0 = v_k[/math].

Определение:

Цикл — это класс эквивалентности циклических путей на отношении эквивалентности таком, что два пути эквивалентны, если [math] \exists j : \forall i \Rightarrow e_{(i \mod k)} = e'_{(i + j) \mod k}[/math]; где [math]e[/math] и [math]e'[/math] — это две последовательности ребер в циклическом пути.

Неориентированные графы

Определение:

Неориентированным графом (undirected graph) [math]G[/math] называется пара [math]G = (V, E)[/math], где [math]V[/math] — конечное множество вершин, а [math] E \subset V \times V(uv \sim vu~\backslash~\{uu~|~u \in V\})[/math] — множество рёбер.

Определение:

Ребром в неориентированном графе называют неупорядоченную пару вершин [math] (v, u) \in E [/math].

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

Иное определение:

Определение:

Неориентированным графом [math]G[/math] называется тройка [math]G = (V, E, ends)[/math] , где [math]ends : E \rightarrow V \times V[/math], а [math]V[/math] и [math]E[/math] — некоторые абстрактные множества.

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

Степенью вершины [math]deg~v_i[/math] в неориентированном графе называют число ребер, инцидентных [math]v_i[/math]. Будем считать, что петли добавляют к степени вершины [math]2[/math].

Определение:

Циклическим путём в неориентированном графе называется путь, в котором [math]v_0 = v_k[/math], а так же [math] e_i \ne e_{(i+1) \mod k}[/math].

Остальные определения в неориентированном графе совпадают с аналогичными определениями в ориентированном графе.

Представление графов

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

Граф можно представить в виде матрицы смежности, где [math]graph[v][u] = true \Leftrightarrow (v, u) \in E[/math]. Также в ячейке матрицы можно хранить вес ребра или их количество (если в графе разрешены паралелльные ребра). Для матрицы смежности существует теорема, позволяющая связать степень матрицы и количество путей из вершины [math]v[/math] в вершину [math]u[/math].

Если граф разрежен ([math]|E| \lt |V^2|[/math]), его лучше представить в виде списков смежности, где список для вершины [math]v[/math] будет содержать вершины [math]u: (v, u) \in E[/math]. Данный способ позволит сэкономить память, т.к. не придется хранить много нулей.

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

Имеет место и другое представление графа - матрица инцидентности, которая сопоставляет множество вершин множеству ребер. То есть:

1. [math]graph[v][j] = 1 \wedge graph[u][j] = -1 \Leftrightarrow v = begin (e_j) \wedge u = end (e_j)[/math], в случае ориентированного графа.
2. [math]graph[v][j] = 1 \Leftrightarrow v[/math] инцидентна ребру [math]e_j[/math], в случае неориентированного графа.
3. Во всех остальных случаях ячейки матрицы равны 0.

См. также

• Лемма о рукопожатиях
• Матрица смежности графа
• Связь степени матрицы смежности и количества путей

Литература

• Харари Фрэнк Теория графов = Graph theory/Пер. с англ. и предисл. В. П. Козырева. Под ред. Г.П.Гаврилова. Изд. 2-е. — М.: Едиториал УРСС, 2003. — 296 с. — ISBN 5-354-00301-6
• Асанов М. О., Баранский В. А., Расин В. В. Дискретная математика: графы, матроиды, алгоритмы — НИЦ РХД, 2001. — 288 с. — ISBN 5-93972-076-5
• Кормен, Томас Х., Лейзерсон, Чарльз И., Ривест, Рональд Л., Штайн Клиффорд Алгоритмы: построение и анализ, 2-е издание. Пер. с англ. — М.:Издательский дом "Вильямс", 2010. — 1296 с.: ил. — Парал. тит. англ. — ISBN 978-5-8459-0857-5 (рус.)