Изменения

Перейти к: навигация, поиск

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

54 байта добавлено, 01:56, 23 декабря 2013
Нет описания правки
Стоит отметить, что для ориентированного графа справедлива [[Лемма о рукопожатиях|лемма о рукопожатиях]], связывающая количество ребер с суммой [[Основные определения теории графов#Степень вершины|степеней вершин]].
 
 
{{Определение
|definition =
'''Путём''' (маршрутом, path) в графе называется последовательность вида <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 =
'''Циклическим путём''' (closed walk) называется путь, в котором <tex>v_0 = v_k</tex>.
}}
{{Определение
|definition =
'''Цикл''' (integral cycle) {{---}} это [[Отношение эквивалентности#Классы эквивалентности|класс эквивалентности]] циклических путей на отношении эквивалентности таком, что два пути эквивалентны, если <tex> \exists j \forall i : e_{(i \mod k)} = e'_{(i + j) \mod k}</tex>; где <tex>e</tex> и <tex>e'</tex> {{---}} это две последовательности ребер в циклическом пути.
}}
==Неориентированные графы==
'''Степенью''' (degree, valency) вершины <tex>\operatorname{deg} v_i</tex> в неориентированном графе называют число ребер, инцидентных <tex>v_i</tex>. Будем считать, что петли добавляют к степени вершины <tex>2</tex>.
{{Определение|definition ='''Циклическим путём''' в неориентированном графе называется путь, в котором <tex>v_0 = v_k</tex>, а так же <tex> e_i \ne e_{(i+1) \mod k}</tex>.}}
Остальные определения в неориентированном графе совпадают с аналогичными определениями в ориентированном графе.
Если граф разрежен (sparse graph, <tex>|E| \ll |V^2|</tex>, то есть, неформально говоря, в нем не очень много ребер. Формально говорить не получается, потому что везде разреженные графы определяются по-разному), его лучше представить в виде списков смежности, где список для вершины <tex>v</tex> будет содержать вершины <tex>u: (v, u) \in E</tex>. Данный способ позволит сэкономить память, т.к. не придется хранить много нулей.
=== Матрица инцидентности Пути в графах ==={{Определение|definition ='''Путём''' (маршрутом, path) в графе называется последовательность вида <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 ='''Циклическим путём''' (closed walk) в ориентированном графе называется путь, в котором <tex>v_0 = v_k</tex>.}}
Имеет место и другое представление графа - [[Матрица инцидентности графа{{Определение|матрица инцидентности]]definition ='''Циклическим путём''' в неориентированном графе называется путь, которая сопоставляет множество вершин множеству ребер. То есть:# в котором <tex>graph[v][j] = 1 \wedge graph[u][j] v_0 = -1 \Leftrightarrow v = begin (e_j) \wedge u = end (e_j)v_k</tex>, в случае ориентированного графа.# а так же <tex>graph[v][j] = e_i \ne e_{(i+1 ) \Leftrightarrow v</tex> инцидентна ребру <tex>e_jmod k}</tex>, в случае неориентированного графа.# Во всех остальных случаях ячейки матрицы равны 0.}}
{{Определение
|definition =
'''Цикл''' (integral cycle) {{---}} это [[Отношение эквивалентности#Классы эквивалентности|класс эквивалентности]] циклических путей на отношении эквивалентности таком, что два пути эквивалентны, если <tex> \exists j \forall i : e_{(i \mod k)} = e'_{(i + j) \mod k}</tex>; где <tex>e</tex> и <tex>e'</tex> {{---}} это две последовательности ребер в циклическом пути.
}}
 
{{Определение
|definition=
'''Простой (вершинно-простой) путь''' {{---}} путь, в котором каждая из вершин графа встречается не более одного раза.
}}
{{Определение
|definition=
'''Реберно-простой путь''' {{---}} путь, в котором каждое из ребер графа встречается не более одного раза.
}}
 
{{Определение
|definition=
'''Длина пути''' {{---}} количество [[Основные определения теории графов|рёбер]], входящих в последовательность, задающую этот путь.
}}
==См. также==
* [[Лемма о рукопожатиях]]
Gfv
119
правок
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Служебная:Сравнение_версий/34608»

Навигация