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

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

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

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

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

Конечным графом (англ. finite graph) [math]G[/math] называется граф, в котором множества [math]V[/math] и [math]E[/math] — конечны. Следует заметить, что большинство рассматриваевых нами графов — конечны.

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

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

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

Изоморфные графы — два графа A и B называются изоморфными, если можно установить биекцию между их вершинами и соответствующими им ребрами.

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

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

• [math] v [/math] — предок (англ. direct predecessor) [math] u [/math].
• [math] u [/math] и [math] v [/math] — смежные (англ. adjacent)
• Вершина [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, \operatorname{beg}, \operatorname{end})[/math] , где [math]V[/math] и [math]E[/math] — некоторые множества, а [math]\operatorname{beg}, \operatorname{end} : E \rightarrow V[/math]. Такой граф иногда называют псевдографом (англ. pseudograph).

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

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

Мультиграф

Псевдограф

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

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

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

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

Неориентированным графом (англ. undirected graph) [math]G[/math] называется пара [math]G = (V, E)[/math], где [math]V[/math] — множество вершин, а [math] E \subset \{\{v, u\}: v, u \in V\}[/math] — множество рёбер.

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

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

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

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

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

Неориентированным графом [math]G[/math] называется тройка [math]G = (V, E, \operatorname{ends})[/math] , где [math]V[/math] — множество вершин, [math]E[/math] — множество ребер, а [math]\operatorname{ends} : E \to \{\{u, v\}, u, v \in V\}[/math]. Это определение, в отличие от предыдущего, позволяет задавать графы с кратными ребрами.

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

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

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

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

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

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

Пути в графах

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

Путём (маршрутом, path) в графе называется последовательность вида [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] — длина пути.

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

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

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

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

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

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

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

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

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

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

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

Длина пути — количество рёбер, входящих в последовательность, задающую этот путь.

Часто используемые графы

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

[math]K_n[/math] — полный граф с [math]n[/math] вершинами.

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

[math]K_{n,m}[/math] — двудольный граф с [math]n[/math] вершинами в одной доле и [math]m[/math] во второй.

См. также

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

Литература

• Харари Фрэнк Теория графов = 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 (рус.)
• Wolfram Mathworld: Graph