419
правок
Изменения
Нет описания правки
{{Определение
|definition =
'''Ориентированным графом''' (directed graph) <tex>G</tex> называется пара <tex>G = (V, E)</tex>, где <tex>V</tex> {{---}} конечное множество вершин, а <tex> E \subset V \times V </tex> {{---}} множество рёбер. }} {{Определение|definition ='''Ребром''' (edge, дугой(arc), линией(line)) ориентированного графа называют упорядоченную пару вершин <tex> (v, u) \in E </tex>.
}}
* <tex> v </tex> {{---}} '''предок''' <tex> u </tex>.
* <tex> u </tex> и <tex> v </tex> {{---}} '''смежные'''
* Вершина <tex> u </tex> '''инцидентна''' ребру <tex> (v, u) </tex>, вершина * Вершина <tex> v </tex> '''инцидентна''' ребру <tex> (v, u) </tex>
Граф с <tex> p </tex> вершинами и <tex> q </tex> ребрами называют <tex> (p, q) </tex> - графом. <tex> (1, 0) </tex>-граф называют <b>тривиальным</b>.
Заметим, что по определению ориентированного графа, данному выше, любые две вершины <tex>u,~v</tex> нельзя соединить более чем одним ребром <tex>(u, v)</tex>.
Поэтому часто используют другое определение.
{{Определение
|id = def1
'''Ориентированным графом''' <tex>G</tex> называется четверка <tex>G = (V, E, beg, end)</tex> , где <tex>beg, end : E \rightarrow V </tex>, а <tex>V</tex> и <tex>E</tex> {{---}} некоторые абстрактные множества.
}}
Иногда граф, построенный таким образом , называют '''мультиграфом'''. В мультиграфе не допускаются петли, но пары вершин допускается соединять более чем одним ребром. Такие ребра называются '''кратными''' (иначе {{---}} '''параллельные''').
{|border="0" cellpadding="5" width=30% align=center
|[[Файл: directed_graph.png|thumb|300px|center|<font color=#ED1C24>Красным</font> выделено кратное ребро (6, 2)<br><font color=#22B14C>Зеленым</font> обозначена петля (6, 6)]]
{{Определение
|definition =
'''Путём'''(маршрутом) в графе называется последовательность вида <tex>v_0 e_1 v_1 ... e_k v_k</tex>, где <tex>e_i \in E,~e_i = (v_{i-1}, v_i)</tex>; <tex>k</tex> {{---}} '''длина''' пути.
}}
{{Определение
{{Определение
|definition =
'''Неориентированным графом''' (undirected graph) <tex>G</tex> называется пара <tex>G = (V, E)</tex>, где <tex>V</tex> {{---}} конечное множество вершин, а <tex> E \subset V \times V(uv \sim vu~\backslash~\{uu~|~u \in V\})</tex> {{---}} множество рёбер. }}{{Определение|definition ='''Ребром''' в неориентированном графе называют неупорядоченную пару вершин <tex> (v, u) \in E </tex>.
}}
[[Файл: Неорграф.png|thumb|300px|center|Неориентированный граф<br>]]
{{Определение
|definition =
'''Неориентированным графом''' <tex>G</tex> называется тройка <tex>G = (V, E, ends)</tex> , где <tex>ends : E \rightarrow V \times V</tex>, а <tex>V</tex> и <tex>E</tex> {{---}} некоторые абстрактные множества.
}}
Две вершины называются '''смежными''' , если между ними есть ребро.
'''Степенью''' вершины <tex>deg~v_i</tex> в неориентированном графе называют число ребер, инцидентных <tex>v_i</tex>. Будем считать, что петли добавляют к степени вершины <tex>2</tex>.
Остальные определения в неориентированном графе совпадают с аналогичными определениями в ориентированном графе.
== Представление графов ==
=== Матрица и списки смежности ===
Граф можно представить в виде [[Матрица смежности графа|матрицы смежности]], где <tex>graph[v][u] = true \Leftrightarrow (v, u) \in E</tex>. Также в ячейке матрицы можно хранить вес ребра или их количество (если в графе разрешены паралелльные ребра).
Для матрицы смежности существует [[Связь степени матрицы смежности и количества путей|теорема]], позволяющая связать степень матрицы и количество путей из вершины <tex>v</tex> в вершину <tex>u</tex>.
Если граф разрежен (<tex>|E| < |V^2|</tex>), его лучше представить в виде списков смежности, где список для вершины <tex>v</tex> будет содержать вершины <tex>u: (v, u) \in E</tex>. Данный способ позволит сэкономить память, т.к. не придется хранить много нулей.
=== Матрица инцидентности ===
Имеет место и другое представление графа - [[Матрица инцидентности графа|матрица инцидентности]], которая сопоставляет множество вершин множеству ребер. То есть:
# <tex>graph[v][j] = 1 \wedge graph[u][j] = -1 \Leftrightarrow v = begin (e_j) \wedge u = end (e_j)</tex>, в случае ориентированного графа.
# <tex>graph[v][j] = 1 \Leftrightarrow v</tex> инцидентна ребру <tex>e_j</tex>, в случае неориентированного графа.
# Во всех остальных случаях ячейки матрицы равны 0.
==См. также==
* [[Лемма о рукопожатиях]]
* [[Матрица смежности графа]]
* [[Связь степени матрицы смежности и количества путей]]
