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

Материал из Викиконспекты
(перенаправлено с «Ориентированный граф»)
Перейти к: навигация, поиск

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

Определение:
Ориентированным графом (англ. 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].


Определение:
Изоморфные графы (англ. isomorphic graphs) — два графа [math]A[/math] и [math]B[/math] называются изоморфными, если можно установить биекцию между их вершинами и соответствующими им рёбрами.


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

Два ребра, имеющие общую концевую вершину, то есть [math]e_1=(v, u_1)[/math] и [math]e_2=(v, u_2)[/math], называются смежными (англ. adjacent).

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

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

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

Граф с [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].

Данное определение разрешает соединять вершины более чем одним ребром. Такие рёбра называются кратными (иначе — параллельные, англ. multi-edge, parallel edge). Граф с кратными рёбрами принято называть мультиграфом (англ. multigraph). Если в мультиграфе присутствуют петли, то такой граф называют псевдографом (англ. pseudograph).

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


Определение:
Для ориентированных графов определяют полустепень исхода вершины (англ. outdegree) [math]\operatorname{deg}^+v_i = |\{e \mid \operatorname{beg(e)} = v_i\}|[/math] и полустепень захода вершины (англ. indegree) [math]\operatorname{deg}^-v_i = |\{e \mid \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]. Это определение, в отличие от предыдущего, позволяет задавать графы с кратными рёбрами.


Определение:
Простым графом [math]G[/math] называется граф, в котором нет петель и кратных рёбер.


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

Будем считать, что петли добавляют к степени вершины [math]2[/math].


Определение:
Изолированной вершиной (англ. isolated vertex) в неориентированном графе называют вершину степени [math]0[/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), k[/math]длина (англ. length) пути.


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


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


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


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


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


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


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

Определение:
Полный граф (англ. complete graph, clique) — граф, в котором каждая пара различных вершин смежна. Полный граф с [math]n[/math] вершинами имеет [math]n(n-1)/2[/math] рёбер и обозначается [math]K_n[/math].


Определение:
Двудольный граф или биграф (англ. bipartite graph) — граф, множество вершин которого можно разбить на две части таким образом, что каждое ребро графа соединяет какую-то вершину из одной части с какой-то вершиной другой части, то есть не существует ребра, соединяющего две вершины из одной и той же части. Двудольный граф с [math]n[/math] вершинами в одной доле и [math]m[/math] во второй обозначается [math]K_{n,m}[/math].


Определение:
Регулярный граф (англ. regular graph) — граф, степени всех вершин которого равны, то есть каждая вершина имеет одинаковое количество соседей. Регулярный граф с вершинами степени [math]k[/math] называется [math]k[/math]‑регулярным, или регулярным графом степени [math]k[/math].


Определение:
Дерево (англ. tree) — связный ациклический граф.


Определение:
Граф называется эйлеровым (англ. eulerian graph), если он содержит эйлеров цикл.


Основная статья: Гамильтоновы графы
Определение:
Граф называется гамильтоновым (англ. hamiltonian graph), если он содержит гамильтонов цикл.


Определение:
Граф называется планарным (англ. planar graph), если он обладает укладкой на плоскости. Плоским (англ. plane graph, planar embedding of the graph) называется граф уже уложенный на плоскости.


Основная статья: Лемма о безопасном ребре
Определение:
Остовное дерево (англ. spanning tree) — ациклический связный подграф данного связного неориентированного графа, в который входят все его вершины.


См. также

Источники информации

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