http://neerc.ifmo.ru/wiki/api.php?action=feedcontributions&user=%D0%90%D0%BD%D0%B4%D1%80%D0%B5%D0%B9+%D0%9A%D0%BE%D0%B7%D0%BB%D0%BE%D0%B2&feedformat=atomВикиконспекты - Вклад участника [ru]2024-03-19T02:24:33ZВклад участникаMediaWiki 1.30.0http://neerc.ifmo.ru/wiki/index.php?title=%D0%A4%D0%B0%D0%B9%D0%BB:Redei_kamion_10.png&diff=22136Файл:Redei kamion 10.png2012-05-09T12:04:01Z<p>Андрей Козлов: загружена новая версия «Файл:Redei kamion 10.png»</p>
<hr />
<div></div>Андрей Козловhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%9E%D1%81%D0%BD%D0%BE%D0%B2%D0%BD%D1%8B%D0%B5_%D0%BE%D0%BF%D1%80%D0%B5%D0%B4%D0%B5%D0%BB%D0%B5%D0%BD%D0%B8%D1%8F_%D1%82%D0%B5%D0%BE%D1%80%D0%B8%D0%B8_%D0%B3%D1%80%D0%B0%D1%84%D0%BE%D0%B2&diff=22124Основные определения теории графов2012-05-09T08:19:09Z<p>Андрей Козлов: /* Ориентированные графы */</p>
<hr />
<div>==Ориентированные графы==<br />
<br />
{{Определение<br />
|definition =<br />
'''Ориентированным графом''' (directed graph) <tex>G</tex> называется пара <tex>G = (V, E)</tex>, где <tex>V</tex> {{---}} конечное множество вершин, а <tex> E \subset V \times V </tex> {{---}} множество рёбер.<br />
}}<br />
<br />
{{Определение<br />
|definition =<br />
'''Ребром''' (edge, дугой (arc), линией (line)) ориентированного графа называют упорядоченную пару вершин <tex> (v, u) \in E </tex>.<br />
}}<br />
<br />
В графе ребро, концы которого совпадают, то есть <tex>e=(v,v)</tex>, называется <b>петлей</b>. Мультиграф с петлями принято называть '''псевдографом'''.<br />
<br />
Если имеется ребро <tex> (v, u) \in E </tex>, то говорят:<br />
* <tex> v </tex> {{---}} '''предок''' <tex> u </tex>.<br />
* <tex> u </tex> и <tex> v </tex> {{---}} '''смежные'''<br />
* Вершина <tex> u </tex> '''инцидентна''' ребру <tex> (v, u) </tex><br />
* Вершина <tex> v </tex> '''инцидентна''' ребру <tex> (v, u) </tex><br />
<br />
'''Инцидентность''' {{---}} понятие, используемое только в отношении ребра и вершины. Две вершины или два ребра не могут быть инцидентны.<br />
<br />
Граф с <tex> p </tex> вершинами и <tex> q </tex> ребрами называют <tex> (p, q) </tex> - графом. <tex> (1, 0) </tex>-граф называют <b>тривиальным</b>.<br />
<br />
Заметим, что по определению ориентированного графа, данному выше, любые две вершины <tex>u,~v</tex> нельзя соединить более чем одним ребром <tex>(u, v)</tex>.<br />
Поэтому часто используют другое определение. <br />
{{Определение<br />
|id = def1<br />
|definition =<br />
'''Ориентированным графом''' <tex>G</tex> называется четверка <tex>G = (V, E, beg, end)</tex> , где <tex>beg, end : E \rightarrow V </tex>, а <tex>V</tex> и <tex>E</tex> {{---}} некоторые абстрактные множества.<br />
}}<br />
Иногда граф, построенный таким образом, называют '''мультиграфом'''. В мультиграфе не допускаются петли, но пары вершин допускается соединять более чем одним ребром. Такие ребра называются '''кратными''' (иначе {{---}} '''параллельные''').<br />
{|border="0" cellpadding="5" width=30% align=center<br />
|[[Файл: Graph_definition_1.png|thumb|210px|center|<font color=#ff2a2a>Красным</font> выделено кратное ребро (6, 2)<br><font color=#3771c8>Синим</font> обозначена петля (6, 6)]]<br />
|[[Файл: Multi_graph.png|thumb|150px|center|Мультиграф]]<br />
|[[Файл: Pseudo_graph.png|thumb|150px|center|Псевдограф]]<br />
|<br />
|}<br />
<br />
<br />
<br />
Также для ориентированных графов определяют '''полустепень исхода вершины''' <tex>deg^-v_i = |\{e~|~beg~e = v_i\}|</tex> и '''полустепень захода вершины''' <tex>deg^+v_i = |\{e~|~end~e = v_i\}|</tex>.<br />
<br />
Стоит отметить, что для ориентированного графа справедлива [[Лемма о рукопожатиях|лемма о рукопожатиях]], связывающая количество ребер с суммой [[Основные определения теории графов#Степень вершины|степеней вершин]].<br />
<br />
<br />
{{Определение<br />
|definition =<br />
'''Путём''' (маршрутом) в графе называется последовательность вида <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> {{---}} '''длина''' пути.<br />
}}<br />
{{Определение<br />
|definition =<br />
'''Циклическим путём''' называется путь, в котором <tex>v_0 = v_k</tex>.<br />
}}<br />
{{Определение<br />
|definition =<br />
'''Цикл''' {{---}} это класс эквивалентности циклических путей на отношении эквивалентности таком, что два пути эквивалентны, если <tex> \exists j : \forall i \Rightarrow e_{(i \mod k)} = e'_{(i + j) \mod k}</tex>; где <tex>e</tex> и <tex>e'</tex> {{---}} это две последовательности ребер в циклическом пути.<br />
}}<br />
<br />
==Неориентированные графы==<br />
{{Определение<br />
|definition =<br />
'''Неориентированным графом''' (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> {{---}} множество рёбер.<br />
}}<br />
{{Определение<br />
|definition =<br />
'''Ребром''' в неориентированном графе называют неупорядоченную пару вершин <tex> (v, u) \in E </tex>.<br />
}}<br />
[[Файл: Graph_definition_2.png|thumb|210px|center|Неориентированный граф<br>]]<br />
Иное определение:<br />
<br />
{{Определение<br />
|definition =<br />
'''Неориентированным графом''' <tex>G</tex> называется тройка <tex>G = (V, E, ends)</tex> , где <tex>ends : E \rightarrow V \times V</tex>, а <tex>V</tex> и <tex>E</tex> {{---}} некоторые абстрактные множества. <br />
}}<br />
<br />
Две вершины называются '''смежными''', если между ними есть ребро.<br />
<br />
'''Степенью''' вершины <tex>deg~v_i</tex> в неориентированном графе называют число ребер, инцидентных <tex>v_i</tex>. Будем считать, что петли добавляют к степени вершины <tex>2</tex>.<br />
<br />
{{Определение<br />
|definition =<br />
'''Циклическим путём''' в неориентированном графе называется путь, в котором <tex>v_0 = v_k</tex>, а так же <tex> e_i \ne e_{(i+1) \mod k}</tex>.<br />
}}<br />
<br />
Остальные определения в неориентированном графе совпадают с аналогичными определениями в ориентированном графе.<br />
<br />
== Представление графов ==<br />
<br />
=== Матрица и списки смежности ===<br />
<br />
Граф можно представить в виде [[Матрица смежности графа|матрицы смежности]], где <tex>graph[v][u] = true \Leftrightarrow (v, u) \in E</tex>. Также в ячейке матрицы можно хранить вес ребра или их количество (если в графе разрешены паралелльные ребра).<br />
Для матрицы смежности существует [[Связь степени матрицы смежности и количества путей|теорема]], позволяющая связать степень матрицы и количество путей из вершины <tex>v</tex> в вершину <tex>u</tex>.<br />
<br />
Если граф разрежен (<tex>|E| < |V^2|</tex>), его лучше представить в виде списков смежности, где список для вершины <tex>v</tex> будет содержать вершины <tex>u: (v, u) \in E</tex>. Данный способ позволит сэкономить память, т.к. не придется хранить много нулей.<br />
<br />
=== Матрица инцидентности ===<br />
<br />
Имеет место и другое представление графа - [[Матрица инцидентности графа|матрица инцидентности]], которая сопоставляет множество вершин множеству ребер. То есть:<br />
# <tex>graph[v][j] = 1 \wedge graph[u][j] = -1 \Leftrightarrow v = begin (e_j) \wedge u = end (e_j)</tex>, в случае ориентированного графа.<br />
# <tex>graph[v][j] = 1 \Leftrightarrow v</tex> инцидентна ребру <tex>e_j</tex>, в случае неориентированного графа.<br />
# Во всех остальных случаях ячейки матрицы равны 0.<br />
<br />
==См. также==<br />
* [[Лемма о рукопожатиях]]<br />
* [[Матрица смежности графа]]<br />
* [[Связь степени матрицы смежности и количества путей]]<br />
<br />
==Литература==<br />
* Харари Фрэнк '''Теория графов''' = Graph theory/Пер. с англ. и предисл. В. П. Козырева. Под ред. Г.П.Гаврилова. Изд. 2-е. — М.: Едиториал УРСС, 2003. — 296 с. — ISBN 5-354-00301-6<br />
* Асанов М. О., Баранский В. А., Расин В. В. '''Дискретная математика: графы, матроиды, алгоритмы''' — НИЦ РХД, 2001. — 288 с. — ISBN 5-93972-076-5<br />
* ''Кормен, Томас Х., Лейзерсон, Чарльз И., Ривест, Рональд Л., Штайн Клиффорд'' '''Алгоритмы: построение и анализ''', 2-е издание. Пер. с англ. — М.:Издательский дом "Вильямс", 2010. — 1296 с.: ил. — Парал. тит. англ. — ISBN 978-5-8459-0857-5 (рус.)<br />
<br />
<br />
[[Категория: Алгоритмы и структуры данных]]<br />
[[Категория: Основные определения теории графов]]</div>Андрей Козловhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%A4%D0%B0%D0%B9%D0%BB:Graph_definition_1.png&diff=22123Файл:Graph definition 1.png2012-05-09T08:18:30Z<p>Андрей Козлов: загружена новая версия «Файл:Graph definition 1.png»</p>
<hr />
<div></div>Андрей Козловhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%9E%D1%81%D0%BD%D0%BE%D0%B2%D0%BD%D1%8B%D0%B5_%D0%BE%D0%BF%D1%80%D0%B5%D0%B4%D0%B5%D0%BB%D0%B5%D0%BD%D0%B8%D1%8F_%D1%82%D0%B5%D0%BE%D1%80%D0%B8%D0%B8_%D0%B3%D1%80%D0%B0%D1%84%D0%BE%D0%B2&diff=22122Основные определения теории графов2012-05-09T08:17:09Z<p>Андрей Козлов: /* Ориентированные графы */</p>
<hr />
<div>==Ориентированные графы==<br />
<br />
{{Определение<br />
|definition =<br />
'''Ориентированным графом''' (directed graph) <tex>G</tex> называется пара <tex>G = (V, E)</tex>, где <tex>V</tex> {{---}} конечное множество вершин, а <tex> E \subset V \times V </tex> {{---}} множество рёбер.<br />
}}<br />
<br />
{{Определение<br />
|definition =<br />
'''Ребром''' (edge, дугой (arc), линией (line)) ориентированного графа называют упорядоченную пару вершин <tex> (v, u) \in E </tex>.<br />
}}<br />
<br />
В графе ребро, концы которого совпадают, то есть <tex>e=(v,v)</tex>, называется <b>петлей</b>. Мультиграф с петлями принято называть '''псевдографом'''.<br />
<br />
Если имеется ребро <tex> (v, u) \in E </tex>, то говорят:<br />
* <tex> v </tex> {{---}} '''предок''' <tex> u </tex>.<br />
* <tex> u </tex> и <tex> v </tex> {{---}} '''смежные'''<br />
* Вершина <tex> u </tex> '''инцидентна''' ребру <tex> (v, u) </tex><br />
* Вершина <tex> v </tex> '''инцидентна''' ребру <tex> (v, u) </tex><br />
<br />
'''Инцидентность''' {{---}} понятие, используемое только в отношении ребра и вершины. Две вершины или два ребра не могут быть инцидентны.<br />
<br />
Граф с <tex> p </tex> вершинами и <tex> q </tex> ребрами называют <tex> (p, q) </tex> - графом. <tex> (1, 0) </tex>-граф называют <b>тривиальным</b>.<br />
<br />
Заметим, что по определению ориентированного графа, данному выше, любые две вершины <tex>u,~v</tex> нельзя соединить более чем одним ребром <tex>(u, v)</tex>.<br />
Поэтому часто используют другое определение. <br />
{{Определение<br />
|id = def1<br />
|definition =<br />
'''Ориентированным графом''' <tex>G</tex> называется четверка <tex>G = (V, E, beg, end)</tex> , где <tex>beg, end : E \rightarrow V </tex>, а <tex>V</tex> и <tex>E</tex> {{---}} некоторые абстрактные множества.<br />
}}<br />
Иногда граф, построенный таким образом, называют '''мультиграфом'''. В мультиграфе не допускаются петли, но пары вершин допускается соединять более чем одним ребром. Такие ребра называются '''кратными''' (иначе {{---}} '''параллельные''').<br />
{|border="0" cellpadding="5" width=30% align=center<br />
|[[Файл: Graph_definition_1.png|thumb|210px|center|<font color=#ff2a2a>Красным</font> выделено кратное ребро (6, 2)<br><font color=#3771c8>Зеленым</font> обозначена петля (6, 6)]]<br />
|[[Файл: Multi_graph.png|thumb|150px|center|Мультиграф]]<br />
|[[Файл: Pseudo_graph.png|thumb|150px|center|Псевдограф]]<br />
|<br />
|}<br />
<br />
<br />
<br />
Также для ориентированных графов определяют '''полустепень исхода вершины''' <tex>deg^-v_i = |\{e~|~beg~e = v_i\}|</tex> и '''полустепень захода вершины''' <tex>deg^+v_i = |\{e~|~end~e = v_i\}|</tex>.<br />
<br />
Стоит отметить, что для ориентированного графа справедлива [[Лемма о рукопожатиях|лемма о рукопожатиях]], связывающая количество ребер с суммой [[Основные определения теории графов#Степень вершины|степеней вершин]].<br />
<br />
<br />
{{Определение<br />
|definition =<br />
'''Путём''' (маршрутом) в графе называется последовательность вида <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> {{---}} '''длина''' пути.<br />
}}<br />
{{Определение<br />
|definition =<br />
'''Циклическим путём''' называется путь, в котором <tex>v_0 = v_k</tex>.<br />
}}<br />
{{Определение<br />
|definition =<br />
'''Цикл''' {{---}} это класс эквивалентности циклических путей на отношении эквивалентности таком, что два пути эквивалентны, если <tex> \exists j : \forall i \Rightarrow e_{(i \mod k)} = e'_{(i + j) \mod k}</tex>; где <tex>e</tex> и <tex>e'</tex> {{---}} это две последовательности ребер в циклическом пути.<br />
}}<br />
<br />
==Неориентированные графы==<br />
{{Определение<br />
|definition =<br />
'''Неориентированным графом''' (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> {{---}} множество рёбер.<br />
}}<br />
{{Определение<br />
|definition =<br />
'''Ребром''' в неориентированном графе называют неупорядоченную пару вершин <tex> (v, u) \in E </tex>.<br />
}}<br />
[[Файл: Graph_definition_2.png|thumb|210px|center|Неориентированный граф<br>]]<br />
Иное определение:<br />
<br />
{{Определение<br />
|definition =<br />
'''Неориентированным графом''' <tex>G</tex> называется тройка <tex>G = (V, E, ends)</tex> , где <tex>ends : E \rightarrow V \times V</tex>, а <tex>V</tex> и <tex>E</tex> {{---}} некоторые абстрактные множества. <br />
}}<br />
<br />
Две вершины называются '''смежными''', если между ними есть ребро.<br />
<br />
'''Степенью''' вершины <tex>deg~v_i</tex> в неориентированном графе называют число ребер, инцидентных <tex>v_i</tex>. Будем считать, что петли добавляют к степени вершины <tex>2</tex>.<br />
<br />
{{Определение<br />
|definition =<br />
'''Циклическим путём''' в неориентированном графе называется путь, в котором <tex>v_0 = v_k</tex>, а так же <tex> e_i \ne e_{(i+1) \mod k}</tex>.<br />
}}<br />
<br />
Остальные определения в неориентированном графе совпадают с аналогичными определениями в ориентированном графе.<br />
<br />
== Представление графов ==<br />
<br />
=== Матрица и списки смежности ===<br />
<br />
Граф можно представить в виде [[Матрица смежности графа|матрицы смежности]], где <tex>graph[v][u] = true \Leftrightarrow (v, u) \in E</tex>. Также в ячейке матрицы можно хранить вес ребра или их количество (если в графе разрешены паралелльные ребра).<br />
Для матрицы смежности существует [[Связь степени матрицы смежности и количества путей|теорема]], позволяющая связать степень матрицы и количество путей из вершины <tex>v</tex> в вершину <tex>u</tex>.<br />
<br />
Если граф разрежен (<tex>|E| < |V^2|</tex>), его лучше представить в виде списков смежности, где список для вершины <tex>v</tex> будет содержать вершины <tex>u: (v, u) \in E</tex>. Данный способ позволит сэкономить память, т.к. не придется хранить много нулей.<br />
<br />
=== Матрица инцидентности ===<br />
<br />
Имеет место и другое представление графа - [[Матрица инцидентности графа|матрица инцидентности]], которая сопоставляет множество вершин множеству ребер. То есть:<br />
# <tex>graph[v][j] = 1 \wedge graph[u][j] = -1 \Leftrightarrow v = begin (e_j) \wedge u = end (e_j)</tex>, в случае ориентированного графа.<br />
# <tex>graph[v][j] = 1 \Leftrightarrow v</tex> инцидентна ребру <tex>e_j</tex>, в случае неориентированного графа.<br />
# Во всех остальных случаях ячейки матрицы равны 0.<br />
<br />
==См. также==<br />
* [[Лемма о рукопожатиях]]<br />
* [[Матрица смежности графа]]<br />
* [[Связь степени матрицы смежности и количества путей]]<br />
<br />
==Литература==<br />
* Харари Фрэнк '''Теория графов''' = Graph theory/Пер. с англ. и предисл. В. П. Козырева. Под ред. Г.П.Гаврилова. Изд. 2-е. — М.: Едиториал УРСС, 2003. — 296 с. — ISBN 5-354-00301-6<br />
* Асанов М. О., Баранский В. А., Расин В. В. '''Дискретная математика: графы, матроиды, алгоритмы''' — НИЦ РХД, 2001. — 288 с. — ISBN 5-93972-076-5<br />
* ''Кормен, Томас Х., Лейзерсон, Чарльз И., Ривест, Рональд Л., Штайн Клиффорд'' '''Алгоритмы: построение и анализ''', 2-е издание. Пер. с англ. — М.:Издательский дом "Вильямс", 2010. — 1296 с.: ил. — Парал. тит. англ. — ISBN 978-5-8459-0857-5 (рус.)<br />
<br />
<br />
[[Категория: Алгоритмы и структуры данных]]<br />
[[Категория: Основные определения теории графов]]</div>Андрей Козловhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%A4%D0%B0%D0%B9%D0%BB:Graph_definition_1.png&diff=22121Файл:Graph definition 1.png2012-05-09T08:15:06Z<p>Андрей Козлов: загружена новая версия «Файл:Graph definition 1.png»</p>
<hr />
<div></div>Андрей Козловhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%A4%D0%B0%D0%B9%D0%BB:Redei_kamion_10.png&diff=22120Файл:Redei kamion 10.png2012-05-09T08:09:10Z<p>Андрей Козлов: загружена новая версия «Файл:Redei kamion 10.png»</p>
<hr />
<div></div>Андрей Козловhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%A4%D0%B0%D0%B9%D0%BB:Redei_kamion_2.png&diff=21193Файл:Redei kamion 2.png2012-04-24T07:56:03Z<p>Андрей Козлов: загружена новая версия «Файл:Redei kamion 2.png»</p>
<hr />
<div></div>Андрей Козловhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%A4%D0%B0%D0%B9%D0%BB:Redei_kamion_4.png&diff=21192Файл:Redei kamion 4.png2012-04-24T07:55:07Z<p>Андрей Козлов: загружена новая версия «Файл:Redei kamion 4.png»</p>
<hr />
<div></div>Андрей Козловhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%A4%D0%B0%D0%B9%D0%BB:Redei_kamion_1.png&diff=21191Файл:Redei kamion 1.png2012-04-24T07:53:37Z<p>Андрей Козлов: загружена новая версия «Файл:Redei kamion 1.png»</p>
<hr />
<div></div>Андрей Козловhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%A2%D0%B5%D0%BE%D1%80%D0%B5%D0%BC%D0%B0_%D0%A0%D0%B5%D0%B4%D0%B5%D0%B8-%D0%9A%D0%B0%D0%BC%D0%B8%D0%BE%D0%BD%D0%B0&diff=21190Теорема Редеи-Камиона2012-04-24T07:49:44Z<p>Андрей Козлов: </p>
<hr />
<div>{{Теорема<br />
|about=<br />
Редеи-Камиона (для пути)<br />
|statement=<br />
В любом [[Турниры|турнире]] есть [[Гамильтоновы_графы#.D0.9E.D1.81.D0.BD.D0.BE.D0.B2.D0.BD.D1.8B.D0.B5_.D0.BE.D0.BF.D1.80.D0.B5.D0.B4.D0.B5.D0.BB.D0.B5.D0.BD.D0.B8.D1.8F|гамильтонов путь]].<br />
|proof= <br />
Приведем доказательство по индукции по числу вершин в графе. Пусть <tex> n </tex> {{---}} количество вершин в графе.<br />
<br />
<u> ''База индукции:'' </u><br />
<br />
Очевидно, для <tex> n = 3 </tex> утверждение верно.<br />
<br />
<u> ''Индукционный переход:'' </u><br />
<br />
Пусть предположение верно для всех турниров с количеством вершин не более <tex> n </tex>. Рассмотрим турнир <tex> T </tex> с <tex> n + 1 </tex> вершинами.<br />
<br />
Пусть <tex> u </tex> – произвольная вершина турнира <tex> T </tex>. Тогда турнир <tex> T - u </tex> имеет <tex> n </tex> вершин, значит, в нем есть гамильтонов путь <tex> P: (v_1 \rightarrow v_2 \rightarrow \ldots \rightarrow v_n) </tex>.<br />
[[Файл: Redei_kamion_1.png|150px|thumb|center]]<br />
<br />
Одно из ребер <tex> (u, v_1) </tex> или <tex> (v_1, u) </tex> обязательно содержится в <tex> T </tex>.<br />
Если ребро <tex> (u, v_1) \in ET </tex>, то путь <tex> (u \rightarrow P) </tex> {{---}} гамильтонов.<br />
[[Файл: Redei_kamion_2.png|150px|thumb|center|<font color=#ff2a2a>Красным</font> цветом выделен искомый путь]]<br />
<br />
Пусть теперь ребро <tex> (u, v_1) \notin ET, v_i </tex> {{---}} первая вершина пути <tex> P </tex>, для которой ребро <tex> (u, v_i) \in T </tex>.<br />
Если такая вершина существует, то в <tex> T </tex> существует ребро <tex> (v_{i - 1}, u) </tex> и путь <tex> (v_1 \rightarrow \ldots \rightarrow v_{i - 1} \rightarrow u \rightarrow v_i \rightarrow \ldots v_n) </tex> – гамильтонов.<br />
[[Файл: Redei_kamion_3.png|180px|thumb|center|<font color=#ff2a2a>Красным</font> цветом выделен искомый путь]]<br />
<br />
Если такой вершины не существует, то путь <tex> (P \rightarrow u) </tex> {{---}} гамильтонов.<br />
[[Файл: Redei_kamion_4.png|150px|thumb|center|<font color=#ff2a2a>Красным</font> цветом выделен искомый путь]]<br />
<br />
Значит, в любом случае в турнире существует гамильтонов путь, q.e.d.<br />
}}<br />
<br />
{{Теорема<br />
|about=<br />
Редеи-Камиона (для цикла)<br />
|statement=<br />
В любом [[Отношение_связности,_компоненты_связности#.D0.A1.D0.B8.D0.BB.D1.8C.D0.BD.D0.B0.D1.8F_.D1.81.D0.B2.D1.8F.D0.B7.D0.BD.D0.BE.D1.81.D1.82.D1.8C|сильно связанном]] турнире есть [[Гамильтоновы_графы#.D0.9E.D1.81.D0.BD.D0.BE.D0.B2.D0.BD.D1.8B.D0.B5_.D0.BE.D0.BF.D1.80.D0.B5.D0.B4.D0.B5.D0.BB.D0.B5.D0.BD.D0.B8.D1.8F|гамильтонов цикл]].<br />
|proof= <br />
Приведем доказательство по индукции по числу вершин в цикле. Пусть <tex> n </tex> {{---}} количество вершин в графе.<br />
<br />
<u> ''База индукции:'' </u><br />
<br />
{{Утверждение<br />
|statement=<br />
Cильно связанный турнир <tex> T </tex> из <tex> n \geq 3 </tex> вершин содержит [[Основные_определения_теории_графов#.D0.9E.D1.80.D0.B8.D0.B5.D0.BD.D1.82.D0.B8.D1.80.D0.BE.D0.B2.D0.B0.D0.BD.D0.BD.D1.8B.D0.B5_.D0.B3.D1.80.D0.B0.D1.84.D1.8B|цикл]] длины <tex> 3 </tex>.<br />
|proof=<br />
Пусть <tex> u </tex> {{---}} произвольная вершина турнира <tex> T </tex>. Множество вершин <tex> VT - u </tex> распадается на <tex> 2 </tex> непересекающихся множества:<br />
* <tex> V_1 = \{ v_1 \in VT | (v_1, u) \in ET \} </tex>,<br />
* <tex> V_2 = \{ v_2 \in VT | (u, v_2) \in ET \} </tex>.<br />
[[Файл: Redei_kamion_5.png|290px|thumb|center]]<br />
<br />
<tex> T </tex> сильно связен, следовательно:<br />
# <tex> V_1 \neq \emptyset </tex>, иначе <tex> v </tex> {{---}} исток турнира<br />
# <tex> V_2 \neq \emptyset </tex>, иначе <tex> v </tex> {{---}} сток турнира<br />
# <tex> \exists e = (w_2, w_1) \in ET </tex>, иначе нет пути из <tex> V_2 </tex> в <tex> V_1 </tex>:<br />
#* <tex> w_1 \in V_1 </tex>,<br />
#* <tex> w_2 \in V_2 </tex>.<br />
[[Файл: Redei_kamion_6.png|290px|thumb|center|<font color=#ff2a2a>Красным</font> цветом выделен цикл длины <tex> 3 </tex>]]<br />
<br />
Цикл <tex> S_3: (u \rightarrow w_2 \rightarrow w_1 \rightarrow u) </tex> {{---}} искомый цикл длины <tex> 3 </tex>, q.e.d.<br />
}}<br />
<br />
<u> ''Индукционный переход:'' </u><br />
<br />
{{Утверждение<br />
|statement=<br />
Если сильно связанный турнир <tex> T </tex> из <tex> n \geq 3 </tex> вершин содержит цикл <tex> S_k </tex> длины <tex> k, (k < n)</tex>, то он содержит и цикл длины <tex> k + 1 </tex>.<br />
|proof=<br />
Пусть <tex> S_k = (v_1 \rightarrow v_2 \rightarrow \ldots \rightarrow v_k \rightarrow v_1) </tex>.<br />
<br />
Пусть <tex> v_0 : v_0 \notin S_k </tex> и верно, что <tex> \exists u, w \in S_k </tex>:<br />
* <tex> (v_0, u) \in ET </tex>,<br />
* <tex> (w, v_0) \in ET </tex>.<br />
<br />
Рассмотрим два случая:<br />
# существует такая вершина <tex> v_0 </tex>,<br />
# не существует такой вершины <tex> v_0 </tex>.<br />
Заметим, что при <tex> k = n - 1 </tex> такая вершина необходимо существует, так как иначе вершина, не входящая в цикл, будет являться либо стоком, либо истоком.<br />
<br />
<u> Первый случай: </u><br />
<br />
Перенумеруем вершины <tex> S_k </tex> так, чтобы ребро <tex> e = (v_1, v_0) \in ET </tex> для вершины <tex> v_1 \in S_k </tex>. Пусть <tex> v_i </tex> – первая вершина при обходе <tex> S_k </tex> из <tex> v_1 </tex>, для которой ребро <tex> f = (v_0, v_i) \in ET </tex>.<br />
[[Файл: Redei_kamion_7.png|150px|thumb|center]]<br />
<br />
Тогда ребро <tex> g = (v_{i - 1}, v_0) \in ET </tex>.<br />
[[Файл: Redei_kamion_8.png|150px|thumb|center|<font color=#ff2a2a>Красным</font> цветом выделен искомый цикл длины <tex> k + 1 </tex> ]]<br />
<br />
Тогда <tex> S_{k + 1} = (v_1 \rightarrow v_2 \rightarrow \ldots \rightarrow v_{i - 1} \rightarrow v_0 \rightarrow v_i \rightarrow \ldots \rightarrow v_k \rightarrow v_1) </tex> – искомый цикл длины <tex> k + 1 </tex>.<br />
<br />
<u> Второй случай: </u><br />
<br />
Пусть:<br />
* <tex> V_1 = \{ u \in VT | u \notin S_k, e = (u, v_i) \in ET, \forall i = \overline{1, n} \} </tex>,<br />
* <tex> V_2 = \{ u \in VT | u \notin S_k, f = (v_i, u) \in ET, \forall i = \overline{1, n} \} </tex>.<br />
Тогда <tex> V_1 \cap V_2 = \emptyset </tex>.<br />
[[Файл: Redei_kamion_9.png|290px|thumb|center]]<br />
<br />
Турнир сильно связен, следовательно:<br />
* <tex> V_1 \neq \emptyset </tex>, иначе <tex> T </tex> не будет сильно связным, так как тогда нет простых путей с началом в <tex> V_2 </tex> и концом в <tex> S_k </tex><br />
* <tex> V_2 \neq \emptyset </tex>, иначе <tex> T </tex> не будет сильно связным, так как тогда нет простых путей с началом в <tex> S_k </tex> и концом в <tex> V_1 </tex><br />
* <tex> \exists g = (w_2, w_1) \in ET </tex>, иначе <tex> T </tex> не будет сильно связным, так как тогда нет простых путей с началом в <tex> V_2 </tex> и концом в <tex> V_1 </tex>):<br />
** <tex> w_1 \in V_1 </tex>,<br />
** <tex> w_2 \in V_2 </tex>.<br />
[[Файл: Redei_kamion_10.png|290px|thumb|center|<font color=#ff2a2a>Красным</font> цветом выделен цикл длины <tex> k + 1 </tex>]]<br />
Тогда <tex> S_{k + 1} = (v_1 \rightarrow w_2 \rightarrow w_1 \rightarrow v_3 \rightarrow \ldots \rightarrow v_k \rightarrow v_1) </tex> – искомый цикл длины <tex> k + 1 </tex>.<br />
<br />
В любом случае утверждение верно, q.e.d.<br />
<br />
}}<br />
Таким образом, любой сильно связанный турнир <tex> T </tex> с <tex> n \geq 3 </tex> вершинами содержит цикл длины <tex> n </tex>, то есть гамильтонов цикл, q.e.d.<br />
}}<br />
<br />
{{Теорема<br />
|about=<br />
Следствие<br />
|statement=<br />
Турнир является сильно связанным тогда и только тогда, когда он имеет гамильтонов цикл.<br />
}}<br />
<br />
==См. также==<br />
* [[Гамильтоновы графы]]<br />
* [[Турниры]]<br />
<br />
== Литература ==<br />
* Асанов М., Баранский В., Расин В.: ''Дискретная математика: Графы, матроиды, алгоритмы''<br />
* Ф. Харари: ''Теория графов''<br />
<br />
[[Категория: Алгоритмы и структуры данных]]<br />
[[Категория: Обходы графов]]</div>Андрей Козловhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%A4%D0%B0%D0%B9%D0%BB:Colors.png&diff=21189Файл:Colors.png2012-04-24T07:44:17Z<p>Андрей Козлов: загружена новая версия «Файл:Colors.png»</p>
<hr />
<div></div>Андрей Козловhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%9E%D0%B1%D1%85%D0%BE%D0%B4_%D0%B2_%D0%B3%D0%BB%D1%83%D0%B1%D0%B8%D0%BD%D1%83,_%D1%86%D0%B2%D0%B5%D1%82%D0%B0_%D0%B2%D0%B5%D1%80%D1%88%D0%B8%D0%BD&diff=21188Обход в глубину, цвета вершин2012-04-24T07:41:14Z<p>Андрей Козлов: /* Дерево обхода в глубину */</p>
<hr />
<div>'''Обход в глубину''' (поиск в глубину, англ. '''Depth-First Search''', '''DFS''') — один из основных методов обхода [[Основные определения теории графов|графа]], часто используемый для [[Использование обхода в глубину для проверки связности|проверки связности]], поиска [[Использование обхода в глубину для поиска цикла в ориентированном графе|цикла]] и [[Использование обхода в глубину для поиска компонент сильной связности|компонент сильной связности]] и для [[Использование обхода в глубину для топологической сортировки|топологической сортировки]].<br />
<br />
== Алгоритм ==<br />
<br />
=== Общая идея ===<br />
Общая идея алгоритма состоит в следующем: для каждой ''не пройденной'' [[Основные определения теории графов|вершины]] необходимо найти все ''не пройденные'' [[Основные определения теории графов|смежные вершины]] и повторить поиск для них.<br />
<br />
=== Пошаговое представление ===<br />
#Выбираем любую вершину из еще ''не пройденных'', обозначим ее как <tex>u</tex>.<br />
#Запускаем процедуру <tex>dfs(u)</tex><br />
#*Помечаем вершину <tex>u</tex> как ''пройденную''<br />
#*Для каждой ''не пройденной'' смежной с <tex>u</tex> вершиной (назовем ее <tex>v</tex>) запускаем <tex>dfs(v)</tex><br />
#Повторяем шаги 1 и 2, пока все вершины не окажутся ''пройденными''.<br />
<br />
=== Реализация ===<br />
vector<bool> visited; //вектор для хранения информации о ''пройденных'' и ''не пройденных'' вершинах<br />
<br />
void dfs(int u) <br />
{<br />
visited[u] = true; //помечаем вершину как пройденную<br />
for (v таких, что (u, v) — ребро в G) //проходим по смежным с u вершинам<br />
if (!visited[v]) //проверяем, не находились ли мы ранее в выбранной вершине<br />
dfs(v);<br />
}<br />
<br />
int main()<br />
{<br />
... //задание графа G с количеством вершин n.<br />
visited.assign(n, false); //в начале все вершины в графе ''не пройденные''<br />
for (int i = 0; i < n; ++i) //проходим по всем вершинам графа...<br />
if (!visited[i]) //...не забыв проверить, были мы уже в очередной вершине или нет<br />
dfs(i);<br />
return 0;<br />
}<br />
<br />
=== Время работы ===<br />
Оценим время работы обхода в глубину. Процедура <tex>dfs</tex> вызывается от каждой вершины не более одного раза, а внутри процедуры рассматриваются все такие [[Основные определения теории графов|ребра]] <tex>\{e\ |\ begin(e) = u\}</tex>. Всего таких ребер для всех вершин в графе <tex>O(E)</tex>, следовательно, время работы алгоритма оценивается как <tex>O(V+E)</tex>.<br />
<br />
== Цвета вершин ==<br />
Зачастую, простой информации "были/не были в вершине" не хватает для конкретных целей.<br /> <br />
Поэтому в процессе алгоритма вершинам задают некоторые цвета:<br /><br />
:если вершина ''белая'', значит, мы в ней еще не были, вершина ''не пройдена'';<br /><br />
:''серая'' — вершина ''проходится'' в текущей процедуре <tex>dfs</tex>;<br /><br />
:''черная'' — вершина ''пройдена'', все итерации <tex>dfs</tex> от нее завершены.<br /><br />
<br />
Такие "метки" в основном используются при [[Использование обхода в глубину для поиска цикла в ориентированном графе|поиске цикла]].<br />
<br />
=== Реализация ===<br />
Отличие реализации с цветами от предыдущей лишь в массиве visited, который мы назовем теперь color.<br />
<br />
vector<color_t> color; //вектор для хранения информации о цвете вершин<br />
<br />
void dfs(int u) <br />
{<br />
color[u] = GRAY; //раскрашиваем вершину в ''серый'' цвет<br />
for (v таких, что (u, v) — ребро в G) //проходим по смежным с u вершинам<br />
if (color[v] == WHITE) //проверяем, не находились ли мы ранее в выбранной вершине, условие не требует изменений, <br />
dfs(v); //поскольку мы считаем вершину "не пройденной" только тогда, когда она ''белого'' цвета, т.е. когда color[v] == WHITE<br />
color[u] = BLACK; //раскрашиваем вершину в ''черный'' цвет<br />
}<br />
<br />
int main()<br />
{<br />
... //задание графа G с количеством вершин n.<br />
color.assign(n, WHITE); //в начале все вершины в графе ''не пройденные'', т.е. ''белые''.<br />
for (int i = 0; i < n; ++i) //проходим по всем вершинам графа...<br />
if (color[i] == WHITE) //...не забыв проверить, были мы уже в очередной вершине или нет<br />
dfs(i);<br />
return 0;<br />
}<br />
<br />
== Дерево обхода в глубину ==<br />
[[Image: Colors.png|thumb|240px|Типы ребер, определяемые деревом обхода:<br><br />
1) ребра дерева<br><br />
2) <font color=#3771c8>обратные</font> ребра<br><br />
3) <font color=#71c837>прямые</font> ребра<br><br />
4) <font color=#ff2a2a>перекрестные</font> ребра]]<br />
<br />
Рассмотрим подграф предшествования обхода в глубину <tex>G_p = (V, E_p)</tex>, где <tex>E_p = \{(p[u], u) : u \in V,\ p[u] \neq NIL\}</tex>, где в свою очередь <tex>p[u]</tex> — вершина, от которой был вызван <tex>dfs(u)\ </tex> (для вершин, от которых <tex>dfs</tex> был вызван нерекурсивно это значение соответственно равно <tex>NIL</tex>). Подграф предшествования поиска в глубину образует ''лес обхода в глубину'', который состоит из нескольких ''деревьев обхода в глубину''. С помощью полученного леса можно классифицировать ребра графа <tex>G</tex>:<br />
* ''Ребрами дерева'' назовем те ребра из <tex>G</tex>, которые вошли в <tex>G_p</tex>. <br />
* Ребра <tex>(u, v)</tex>, соединяющие вершину <tex>u</tex> с её предком <tex>v</tex> в дереве обхода в глубину назовем ''обратными ребрами'' (для неориентированного графа предок должен быть ''не родителем'', так как иначе ребро будет являться ребром дерева). <br />
* Ребра <tex>(u, v)</tex>, не являющиеся ребрами дерева и соединяющие вершину <tex>u</tex> с её потомком <tex>v</tex> в дереве обхода в глубину назовем ''прямыми ребрами'' (в неориентированном графе нет разницы между прямыми и обратными ребрами, поэтому все такие ребра считаются обратными). <br />
* Все остальные ребра назовем ''перекрестными ребрами'' — такие ребра могут соединять вершины одного и того же дерева обхода в глубину, когда ни одна из вершин не является предком другой, или соединять вершины в разных деревьях.<br />
Алгоритм <tex>dfs</tex> можно модифицировать так, что он будет классифицировать встречающиеся при работе ребра. Ключевая идея состоит в том, что каждое ребро <tex>(u, v)</tex> можно классифицировать при помощи цвета вершины <tex>v</tex> при первом его исследовании, а именно:<br />
* Белый цвет вершины <tex>v</tex> по определению <tex>dfs</tex> говорит о том, что это ''ребро дерева''.<br />
* Серый цвет в силу того, что серые вершины всегда образуют нисходящий путь в каком-либо из деревьев <tex>dfs</tex> и встреченная вершина <tex>v</tex> лежит на нем выше вершины <tex>u</tex>, определяет ''обратное ребро'' (для неориентированного графа необходимо проверить условие <tex>v \neq p[u]</tex>).<br />
* Черный цвет, соответственно, указывает на ''прямое'' или ''перекрестное ребро''.<br />
<br />
== Источники ==<br />
*[http://ru.wikipedia.org/wiki/Поиск_в_глубину Обход в глубину на ru.wikipedia.org]<br />
*[http://en.wikipedia.org/wiki/Depth-first_search Обход в глубину на en.wikipedia.org]<br />
*[http://www.e-maxx.ru/algo/dfs Обход в глубину. Реализации.]<br />
* Томас Кормен, Чарльз Лейзерсон, Рональд Ривест, Клиффорд Штайн. Алгоритмы: построение и анализ, второе издание. Пер. с англ. — Издательский дом "Вильямс", 2007. — 1296 с. — Глава 22. Элементарные алгоритмы для работы с графами.<br />
<br />
<br />
[[Категория: Алгоритмы и структуры данных]]<br />
[[Категория: Обход в глубину]]</div>Андрей Козловhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%94%D0%B2%D1%83%D0%B4%D0%BE%D0%BB%D1%8C%D0%BD%D1%8B%D0%B5_%D0%B3%D1%80%D0%B0%D1%84%D1%8B_%D0%B8_%D1%80%D0%B0%D1%81%D0%BA%D1%80%D0%B0%D1%81%D0%BA%D0%B0_%D0%B2_2_%D1%86%D0%B2%D0%B5%D1%82%D0%B0&diff=21187Двудольные графы и раскраска в 2 цвета2012-04-24T07:40:29Z<p>Андрей Козлов: /* Раскраска в 2 цвета */</p>
<hr />
<div>{{Определение<br />
<br />
|definition=<br />
Неориентированный граф <tex> G =(W, E) </tex> называется '''двудольным''', если множество его вершин можно разбить на две части <tex>U \cup V = W , |U| > 0, |V| > 0</tex>, так, что ни одна вершина в <tex>U</tex> не соединена с вершинами в <tex> U </tex> и ни одна вершина в <tex> V </tex> не соединена с вершинами в <tex>V</tex>.<br />
}}<br />
<br />
== Раскраска в 2 цвета ==<br />
<br />
{{Теорема <br />
|statement=<br />
Граф 2-раскрашиваемый тогда и только тогда, когда он двудольный.<br />
|proof= <br />
<br />
[[Файл: Bipartite_graph.png|thumb|300px|upright|Пример двудольного графа]]<br />
<br />
Если множество вершин двудольного графа можно разделить на два независимых подмножества так, что ни одна из вершин ни в одном из этих подмножеств не является смежной к вершине из этого же подмножества, тогда граф <tex>G = (W, E)</tex> — 2-раскрашиваем. <tex>\chi(G) = 2</tex>.<br />
<br />
Если же граф 2-раскрашиваемый, то множество его вершин можно разделить на два непересекающихся множества так, чтобы в каждом из них не нашлось двух смежных вершин. Тогда граф будет двудольным.<br />
}}<br />
<br />
==Теорема Кенига==<br />
{{Теорема <br />
|about=<br />
Кениг<br />
|statement=<br />
Граф <tex> G </tex> является двудольным тогда и только тогда, когда все циклы в графе <tex> G </tex> имеют чётную длину.<br />
|proof=<br />
<br />
''Достаточность.'' <br />
<br />
Рассмотрим двудольный граф. Начнем цикл в доли <tex> U </tex>. Нужно пройти по четному числу ребер, чтобы вернуться в <tex> U </tex> снова. Следовательно, при замыкании цикла число ребер будет четным.<br />
<br />
''Необходимость.''<br />
<br />
Пусть ненулевой граф <tex> G </tex> связен и не имеет циклов нечетной длины. Выберем произвольно вершину <tex> u </tex> и разобьем множество всех вершин на два непересекающихся множества <tex> U </tex> и <tex> V </tex> так, чтобы в <tex> U </tex> лежали вершины <tex> v_0 </tex>, такие что кратчайшая цепь <tex>(u, v_0)</tex> была чётной длины, а в <tex> V </tex> соответственно вершины <tex>v_1</tex>, для которых длина цепи <tex>(u, v_1)</tex> — нечётная. При этом <tex> u \in U </tex>. <br />
<br />
В графе <tex> G </tex> нет ребер <tex>ab</tex>, таких что <tex>a, b </tex> лежат одновременно в <tex> U </tex> и <tex>V</tex>. Докажем это от противного. Пусть <tex>a, b \in U </tex>. Зададим <tex> P_0 </tex> — кратчайшая <tex> (u, a) </tex> цепь, а <tex> P_1 </tex> — кратчайшая <tex> (u, b) </tex> цепь. Обе цепи четной длины. Пусть <tex> v_0 </tex> — последняя вершина цепи <tex> P_0 </tex>, принадлежащая <tex> P_1 </tex>. Тогда подцепи от <tex> u </tex> до <tex> v_0 </tex> в <tex> P_0</tex> и <tex>P_1</tex> имеют одинаковую длину (иначе бы, пройдя по более короткой подцепи от <tex>u</tex> до <tex>v_0</tex> мы смогли бы найти более короткую цепь от <tex> u </tex> до <tex> a </tex> или от <tex> u </tex> до <tex> b </tex>, чем цепь <tex> P_0 </tex> или <tex> P_1 </tex> ). Так как подцепи от <tex> v_0 </tex> до <tex> a </tex> и от <tex> v_0 </tex> до <tex> b </tex> в цепях <tex> P_0 </tex> и <tex> P_1 </tex> имеют одинаковую четность, а значит в сумме с ребром <tex> ab </tex> они образуют цикл нечётной длины, что невозможно.<br />
}}<br />
<br />
== Алгоритм ==<br />
<br />
Так как граф является двудольным тогда и только тогда, когда все циклы четны, определить двудольность можно за один проход в глубину.<br />
На каждом шаге обхода в глубину помечаем вершину. Допустим мы пошли в первую вершину — помечаем её как <tex> 1 </tex>. Затем просматриваем все смежные вершины и если не помечена вершина, то на ней ставим пометку <tex> 2 </tex> и рекурсивно переходим в нее. Если же она помечена и на ней стоит та же пометка, что и у той, из которой шли (в нашем случае <tex> 1 </tex>), значит граф не двудольный.<br />
<br />
<br />
== Источники ==<br />
1. Асанов М. О., Баранский В. А., Расин В. В. - Дискретная математика: Графы, матроиды, алгоритмы. '''ISBN 978-5-8114-1068-2'''<br /><br />
2. Харари Ф. - Теория графов. '''ISBN 978-5-397-00622-4'''<br />
<br />
==См. также ==<br />
* [http://rain.ifmo.ru/cat/view.php/theory/graph-coloring-layout| Графы. Раскраски и укладки.]<br />
<br />
[[Категория: Алгоритмы и структуры данных]]<br />
[[Категория: Раскраски графов]]</div>Андрей Козловhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%A3%D0%BA%D0%BB%D0%B0%D0%B4%D0%BA%D0%B0_%D0%B3%D1%80%D0%B0%D1%84%D0%B0_%D1%81_%D0%BF%D0%BB%D0%B0%D0%BD%D0%B0%D1%80%D0%BD%D1%8B%D0%BC%D0%B8_%D0%BA%D0%BE%D0%BC%D0%BF%D0%BE%D0%BD%D0%B5%D0%BD%D1%82%D0%B0%D0%BC%D0%B8_%D0%B2%D0%B5%D1%80%D1%88%D0%B8%D0%BD%D0%BD%D0%BE%D0%B9_%D0%B4%D0%B2%D1%83%D1%81%D0%B2%D1%8F%D0%B7%D0%BD%D0%BE%D1%81%D1%82%D0%B8&diff=21186Укладка графа с планарными компонентами вершинной двусвязности2012-04-24T07:39:21Z<p>Андрей Козлов: </p>
<hr />
<div>{{Теорема<br />
|about=об укладке графа с планарными компонентами вершинной двусвязности<br />
|statement=Если [[Отношение вершинной двусвязности|компоненты вершинной двусвязности]] [[Основные определения: граф, ребро, вершина, степень, петля, путь, цикл|графа]] <tex>G</tex> [[Укладка графа на плоскости|планарны]], то и сам граф <tex>G</tex> планарен.<br />
|proof=<br />
<br />
Докажем вспомогательную лемму.<br />
<br />
{{Лемма<br />
|id=l1<br />
|about=I<br />
|statement=Пусть графы <tex>G_1</tex> и <tex>G_2</tex> планарны. Граф <tex>G</tex> получается из <tex>G_1</tex> и <tex>G_2</tex> совмещением вершин <tex>v_1 \in G_1</tex> и <tex>v_2 \in G_2</tex>. Тогда <tex>G</tex> планарен.<br />
|proof=<br />
<br />
Предварительно заметим, что в доказательстве используются утверждения [[Укладка графа с планарными компонентами реберной двусвязности#l1|леммы I]] и [[Укладка графа с планарными компонентами реберной двусвязности#l2|леммы II]] из статьи [[Укладка графа с планарными компонентами реберной двусвязности]]. Итак, уложим <tex>G_2</tex> на сфере и уложим <tex>G_1</tex> на плоскости так, чтобы ребро <tex>e_1 \in G_1</tex> смежное с <tex>v_1</tex> (если таковое имеется) оказалось на границе внешней грани (по [[#l2|лемме II]] это возможно). Если такого ребра <tex>e_1</tex> не существует, значит вершина <tex>v_1</tex> изолирована, в таком случае возьмем любую укладку <tex>G_1</tex> на плоскости и переместим точку, соответствующую <tex>v_1</tex> во внешнюю грань. Иначе сожмем часть плоскости, содержащую укладку <tex>G_1</tex> так, чтобы она вмещалась в одну из граней укладки <tex>G_2</tex> смежную с <tex>v_1</tex>. Рассмотрим множество <tex>U</tex> вершин смежных с <tex>v_1</tex>. Уберем кривые, соответствующие ребрам, инцидентным <tex>v_1</tex>. Ясно, что после этого множество вершин <tex>U</tex> лежит на внешней границе укладки <tex>G_1</tex>. Соединим теперь каждую вершину из <tex>U</tex> c <tex>v_2</tex> непересекающимися жордановыми линиями так, чтобы они не задевали укладок <tex>G_1</tex> и <tex>G_2</tex> (рис. 1). Таким образом мы совместили вершины <tex>v_1</tex> и <tex>v_2</tex> в вершине <tex>v_2</tex>, а значит получили укладку графа <tex>G</tex> на сфере, следовательно <tex>G</tex> - планарен.<br />
[[Файл: Planar_vertex_biconnected_1.png|300px|center|thumb|рис. 1.]]<br />
}}<br />
<br />
Докажем утверждение теоремы для одной из компоненты связности графа <tex>G</tex>. Ясно, что имея укладки на плоскости каждой из компонент связности графа, мы можем получить укладку на плоскости и всего графа.<br />
Итак пусть граф <tex>G</tex> связен. Если <tex>G = K_1</tex>, то <tex>G</tex> очевидно планерен, поэтому предположим, что <tex>|EG| \ge 1</tex> , а значит имеется по-крайней мере один блок в <tex>G</tex>. Рассмотрим связный подграф <tex>T</tex> графа блоков и точек сочленений графа <tex>G</tex> такой, что <tex>\forall v</tex> - т.с. <tex>G</tex> имеем <tex>deg(v) \ge 2</tex>. Из [[Граф блоков-точек сочленения#lemma1|леммы]] и из связности <tex>T</tex> получаем, что <tex>T</tex> &mdash; двудольное [[Дерево, эквивалентные определения|дерево]]. <br />
<br />
Докажем индукцией по числу вершин в графе <tex>T</tex>, что подграф <tex>G'</tex> графа <tex>G</tex> состоящий из блоков графа <tex>G</tex> принадлежащих графу <tex>T</tex> планарен (далее будем говорить, что <tex>G'</tex> соответствует <tex>T</tex>).<br />
<br />
'''База индукции.''' <br />
<div style="border:1px dashed #000; width:90%; margin: 10px; padding:4px; background-color: #fdfdfd; padding-left:10px;"><br />
Если <tex>|VT| = 1</tex>, то граф <tex>T</tex> тривиальный. Его единственная вершина &mdash; это блок графа <tex>G</tex>, который по утверждению теоремы планарен.<br />
</div><br />
<br />
'''Индукционный переход.''' <br />
<br />
<div style="border:1px dashed #000; width:90%; margin: 10px; padding:4px; background-color: #fdfdfd; padding-left:10px;"><br />
Пусть утверждение верно для <tex>|VT| < m</tex>. Рассмотрим <tex>T</tex>, для которого <tex>|VT| = m > 1</tex>, и соответствующий <tex>T</tex> подграф <tex>G'</tex> графа <tex>G</tex>. Докажем, что <tex>G'</tex> планарен. <br />
<br />
Положим <tex>G_1</tex> &mdash; это блок графа <tex>G'</tex> являющийся висячей вершиной дерева <tex>T</tex> (вспомним, что в дереве, в котором более одной вершины, всегда есть есть висячие вершины, и то, что висячими вершинами в графе блоков и т.с. не могут быть т.с.), a <tex>v</tex> {{---}} т.с. в <tex>G'</tex> смежная с <tex>G_1</tex> в <tex>T</tex>. <tex>G_1</tex> планарен по утверждению теоремы, т.к. блоки графа <tex>G'</tex> совпадают с блоками графа <tex>G</tex>. Заметим, что <tex>deg(v) > 1</tex>, т.к. <tex>v</tex> {{---}} т.с., следовательно не висячая. Рассмотрим два случая:<br />
<br />
#<tex>deg(v) = 2</tex> в <tex>T</tex> (рис. 2). Обозначим за <tex>T'</tex> <tex>T\backslash \{u,v\}</tex>. Поскольку степень ни одной из т.с. <tex>G'</tex> принадлежащих <tex>T</tex> (кроме удаленной <tex>v</tex>) не уменьшилась, значит <tex>T'</tex> удовлетворяет условиям на <tex>T</tex> из предположения индукции. Заметим, что <tex>VT' = VT - 2 = m - 2 < m</tex>. Заметим также, что <tex>T'</tex> связен, т.к. <tex>u</tex> и <tex>v</tex> по очереди были висячими вершинами <tex>T</tex> и <tex>T\backslash \{u\}</tex>.[[Файл: Planar vertex biconnected 2.png|270px|center|thumb|рис. 2. Красные {{---}} точки сочленений. Голубые {{---}} блоки.]]<br />
#<tex>deg (v) > 2</tex> в <tex>T</tex> (рис. 3). Обозначим за <tex>T'</tex> <tex>T\backslash \{u\}</tex>. Поскольку степень ни одной из т.с. <tex>G'</tex> принадлежащих <tex>T</tex> (кроме <tex>v</tex>, для нее степень уменьшилась ровно на <tex>1</tex>) не уменьшилась, а для вершины <tex>v</tex> в <tex>T'</tex> верно, что <tex>deg(v) >= 2</tex>, то <tex>T'</tex> удовлетворяет условиям на <tex>T</tex> из предположения индукции. Заметим, что <tex>VT' = VT - 1 = m - 1 < m</tex>. Заметим также, что <tex>T'</tex> связен, т.к. <tex>u</tex> была висячей вершиной в <tex>T</tex>.[[Файл: Planar vertex biconnected 3.png|270px|center|thumb|рис. 3. Красные {{---}} точки сочленений. Голубые {{---}} блоки.]]<br />
<br />
Рассмотрим подграф <tex>G_2</tex> графа <tex>G'</tex> соответствующий дереву <tex>T'</tex>. Поскольку <tex>T'</tex> связен, степени вершин в <tex>T'</tex> соответствующих т.с. графа <tex>G'</tex> удовлетворяют предположению индукции и, очевидно, также как и <tex>T</tex> граф <tex>T'</tex> является подграфом графа блоков и точек сочленений <tex>G</tex>, получим, что <tex>G_2</tex> планарен по предположению индукции, т.к. <tex>VT' < m</tex>. <br />
<br />
Из определения ребер дерева блоков и точек сочленений получаем, что графы <tex>G_1</tex> и <tex>G_2</tex> имеют единственную общую точку {{---}} точку сочленения <tex>v</tex>. Поскольку множество блоков <tex>G'</tex> принадлежащих <tex>T</tex> состоит из <tex>G_1</tex> и множества блоков <tex>T'</tex>, то <tex>G' = G_1\cup G_2</tex>. <tex>G_1, G_2, G'</tex> удовлетворяют условию [[#l1|леммы I]], поэтому получим укладку <tex>G</tex> из укладок <tex>G_1</tex> и <tex>G_2</tex> так, как это сделано в доказательстве леммы. Получаем, что <tex>G'</tex> планарен. А значит предположение индукции верно.<br />
</div><br />
<br />
Рассматривая в качестве <tex>T</tex> граф <tex>T_G</tex> блоков и точек сочленений <tex>G</tex>. По [[Граф блоков-точек сочленения|лемме]] <tex>T_G</tex> {{---}} дерево, следовательно каждая его вершина имеет степень как минимум <tex>1</tex>. Поскольку граф <tex>G</tex> содержит хотя бы один блок. Если это единственный блок, то <tex>T_G</tex> не содержит ни одной точки сочленения. Если граф <tex>G</tex> содержит хотя бы <tex>2</tex> блока и, следовательно хотя бы одну точку сочленения, то <tex>T_G</tex> {{---}} дерево, содержащее хотя бы одно ребро. Поскольку в графе блоков и точек сочленений точки сочленений не могут быть висячими вершинами, то каждая из т.с. графа <tex>G</tex> принадлежащих <tex>T_G</tex> имеет степень как минимум <tex>2</tex>. Получаем, что <tex>T_G</tex> удовлетворяет условиям на <tex>T</tex> из предположения индукции, а значит <tex>G</tex> планарен.<br />
}}<br />
<br />
'''Замечание.''' В доказательстве теоремы непосредственно указывается способ получения укладки графа <tex>G</tex> из имеющихся укладок его блоков.<br />
<br />
==Источники==<br />
<br />
* Асанов М. О., Баранский В. А., Расин В. В. '''Дискретная математика: графы, матроиды, алгоритмы''' — НИЦ РХД, 2001. — 288 с. — ISBN 5-93972-076-5<br />
<br />
* H. Whitney '''Non-separable and planar graphs''' — Trans. Amer. Math. Soc., 1932.<br />
<br />
[[Категория: Алгоритмы и структуры данных]]<br />
[[Категория: Укладки графов ]]</div>Андрей Козловhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%A3%D0%BA%D0%BB%D0%B0%D0%B4%D0%BA%D0%B0_%D0%B3%D1%80%D0%B0%D1%84%D0%B0_%D1%81_%D0%BF%D0%BB%D0%B0%D0%BD%D0%B0%D1%80%D0%BD%D1%8B%D0%BC%D0%B8_%D0%BA%D0%BE%D0%BC%D0%BF%D0%BE%D0%BD%D0%B5%D0%BD%D1%82%D0%B0%D0%BC%D0%B8_%D1%80%D1%91%D0%B1%D0%B5%D1%80%D0%BD%D0%BE%D0%B9_%D0%B4%D0%B2%D1%83%D1%81%D0%B2%D1%8F%D0%B7%D0%BD%D0%BE%D1%81%D1%82%D0%B8&diff=21185Укладка графа с планарными компонентами рёберной двусвязности2012-04-24T07:37:38Z<p>Андрей Козлов: </p>
<hr />
<div>{{Теорема<br />
|about=об укладке графа с планарными компонентами реберной двусвязности<br />
|statement=Если [[Отношение реберной двусвязности|компоненты реберной двусвязности]] [[Основные определения: граф, ребро, вершина, степень, петля, путь, цикл|графа]] <tex>G</tex> [[Укладка графа на плоскости|планарны]], то и сам граф <tex>G</tex> планарен.<br />
|proof=<br />
<br />
Докажем для начала ряд вспомогательных лемм.<br />
<br />
{{Лемма<br />
|id=l1<br />
|about=I<br />
|statement=Граф <tex>G</tex> планарен тогда и только тогда, когда он обладает укладкой на сфере<br />
|proof=<br />
<br />
Рассмотрим укладку графа <tex>G</tex> на сфере. Возьмем на сфере точку <tex>N</tex>, не лежащую на ребре, и не вершину. Выберем на сфере точку <tex>S</tex> противолежащую <tex>N</tex> (<tex>N</tex> и <tex>S</tex> лежат на одном диаметре и при этом не совпадают). Проведем через точку <tex>S</tex> касательную к сфере плоскость. Спроектируем на плоскость все точки сферы, проведя все возможные лучи из точки <tex>N</tex> через точки сферы до пересечения с плоскостью (рис. 1) . Ясно, что эта проекция дает укладку графа <tex>G</tex> на плоскости.<br />
<br />
[[Файл: Planar_edge_biconnected_1.png|390px|thumb|center|рис. 1. Проекция графа со сферы на плоскость. <tex>S</tex> {{---}} точка касания, <tex>N</tex> {{---}} противоположная точка.]]<br />
<br />
<br />
Обратно рассмотрим укладку графа <tex>G</tex> на плоскости. Возьмем сферу, которая касается плоскости, и обозначим точку касания за <tex>S</tex>. Противолежащую <tex>S</tex> точку на сфере обозначим за <tex>N</tex>. Проведем все возможные лучи от точек плоскости через точки сферы до точки <tex>N</tex>. Ясно что при этом укладка графа <tex>G</tex> на плоскости будет перенесена на некоторую укладку графа <tex>G</tex> на сфере.<br />
}}<br />
<br />
<br />
{{Лемма<br />
|id=l2<br />
|about=II<br />
|statement=Для любого выделенного ребра планарного графа найдется такая укладка графа на плоскости, что выделенное ребро будет лежать на границе внешней грани.<br />
|proof=<br />
<br />
Возьмем укладку графа на сфере. Перенесем эту укладку графа на сфере в укладку на плоскости так как это сделано в [[#l1|лемме I]], за точку <tex>N</tex> возьмем точку на сфере, не лежащую на ребре, не являющуюся вершиной и принадлежащую грани на границе которой лежит выделенное ребро. Полученная укладка на плоскости обладает нужным нам свойством (рис. 2).<br />
<br />
[[Файл: Planar_edge_biconnected_2.png|220px|thumb|center|рис. 2.]]<br />
}}<br />
<br />
Докажем утверждение теоремы для одной из компонент связности графа <tex>G</tex>. Ясно, что имея укладки на плоскости каждой из компонент связности графа, мы можем получить укладку на плоскости и всего графа.<br />
Итак пусть граф <tex>G</tex> связен. Рассмотрим связный подграф <tex>T</tex> графа компонент реберной двусвязности графа <tex>G</tex>. Из [[Граф компонент реберной двусвязности|леммы]] и из связности <tex>T</tex> получаем, что <tex>T</tex> &mdash; [[Дерево, эквивалентные определения|дерево]]. <br />
<br />
Докажем индукцией по числу вершин в графе <tex>T</tex>, что подграф <tex>G'</tex> графа <tex>G</tex> состоящий из компонент реберной двусвязности и мостов графа <tex>G</tex> принадлежащих графу <tex>T</tex> планарен (далее будем говорить, что <tex>G'</tex> соответствует <tex>T</tex>).<br />
<br />
'''База индукции.''' <br />
<br />
<div style="border:1px dashed #000; width:90%; margin: 10px; padding:4px; background-color: #fdfdfd; padding-left:10px;"><br />
Если <tex>|VT| = 1</tex>, то граф <tex>T</tex> {{---}} тривиальный граф. Его единственная вершина - это компонента реберной двусвязности графа <tex>G</tex>, которая по условию теоремы планарна.<br />
</div><br />
<br />
'''Индукционный переход.''' <br />
<br />
<div style="border:1px dashed #000; width:90%; margin: 10px; padding:4px; background-color: #fdfdfd; padding-left:10px;"><br />
Пусть утверждение верно для <tex>|VT| < m</tex>. Рассмотрим <tex>T</tex>, для которого <tex>|VT| = m > 1</tex>, и соответствующий <tex>T</tex> подграф <tex>G'</tex> графа <tex>G</tex>. Докажем, что <tex>G'</tex> планарен. <br />
<br />
Положим <tex>G_1</tex> &mdash; компонента реберной двусвязности графа <tex>G'</tex> являющийся висячей вершиной дерева <tex>T</tex>, a <tex>e</tex> &mdash; мост в <tex>G'</tex> инцидентный <tex>G_1</tex> в <tex>T</tex> (рис. 3). <tex>G_1</tex> планарен по условию теоремы, т.к. компоненты реберной двусвязности графа <tex>G'</tex> совпадают с компонентами реберной двусвязности графа <tex>G</tex>. Далее рассмотрим подграф <tex>G_2</tex> графа <tex>G'</tex>, соответствующий дереву <tex>T\backslash \{G_1\}</tex>. Поскольку <tex>G_1</tex> &mdash; висячая вершина <tex>T</tex>, то <tex>T\backslash \{G_1\}</tex> связен, и, очевидно, также как и <tex>T</tex> является подграфом графа компонент реберной двусвязности <tex>G</tex>. Итак <tex>G_2</tex> планарен по предположению индукции, т.к. <tex>|V(T\backslash \{G_1\})| = |VT| - 1 = m - 1 < m</tex>. <br />
Из определения ребер графа компонент реберной двусвязности получаем, что графы <tex>G_1</tex> и <tex>G_2</tex> соединены в графе <tex>G'</tex> единственным мостом <tex>e \in G'</tex> инцидентным блоку <tex>G_1</tex> в дереве <tex>T</tex>. Поскольку <tex>T = G_1\cup e\cup G_2</tex>, то и <tex>G' = G_1\cup e\cup G_2</tex>. Покажем как из укладок <tex>G_1</tex> и <tex>G_2</tex> получить укладку <tex>G'</tex>.<br />
<br />
[[Файл: Planar_edge_biconnected_3.png|240px|thumb|center|рис. 3. Удаление <tex>G_1</tex> из графа компонент реберной двусвязности]]<br />
<br />
Уложим <tex>G_2</tex> на сфере и уложим <tex>G_1</tex> на плоскости так, чтобы ребро <tex>e_1 \in G_1</tex> смежное с <tex>e</tex> в G' (если таковое имеется) оказалось на границе внешней грани (по [[#l2|лемме II]] это возможно, рис. 4). Если такого ребра <tex>e_1</tex> не существует, значит компонента реберной двусвязности <tex>G_1</tex> &mdash; тривиальный граф, в таком случае возьмем любую укладку <tex>G_1</tex> на плоскости. Пусть <tex>u\in G_2</tex> {{---}} вершина инцидентная <tex>e</tex>. Сожмем часть плоскости, содержащую укладку <tex>G_1</tex>, так, чтобы она вмещалась в одну из граней укладки <tex>G_2</tex> смежную с <tex>u</tex>. Проведем жорднанову кривую, соответствующую ребру <tex>e</tex>, от вершины <tex>u</tex> к инцидентной <tex>e</tex> вершине графа <tex>G_1</tex> так, чтобы она не пересекалась с укладками <tex>G_1</tex> и <tex>G_2</tex>. Мы получили укладку графа <tex>G'</tex> на сфере, а значит (по [[#l1|лемме I]]) <tex>G'</tex> планарен, следовательно предположение индукции верно.<br />
<br />
[[Файл: Planar_edge_biconnected_4.png|thumb|220px|center|рис. 4. Укладка <tex>G_1</tex> и <tex>G_2</tex> на сфере]]<br />
</div><br />
<br />
<br />
<br />
Рассматривая в качестве <tex>T</tex> граф компонент реберной двусвязности <tex>G</tex> получаем что <tex>G</tex> - планарен.<br />
}}<br />
<br />
'''Замечание.''' В доказательстве теоремы непосредственно указывается способ получения укладки графа <tex>G</tex> из укладок его компонент реберной двусвязности.<br />
<br />
==Источники==<br />
<br />
* Асанов М. О., Баранский В. А., Расин В. В. '''Дискретная математика: графы, матроиды, алгоритмы''' — НИЦ РХД, 2001. — 288 с. — ISBN 5-93972-076-5<br />
<br />
* H. Whitney '''Non-separable and planar graphs''' — Trans. Amer. Math. Soc., 1932.<br />
<br />
[[Категория: Алгоритмы и структуры данных]]<br />
[[Категория: Укладки графов ]]</div>Андрей Козловhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%A2%D0%B5%D0%BE%D1%80%D0%B5%D0%BC%D0%B0_%D0%A5%D0%B2%D0%B0%D1%82%D0%B0%D0%BB%D0%B0&diff=21184Теорема Хватала2012-04-24T07:35:19Z<p>Андрей Козлов: </p>
<hr />
<div>{{Определение<br />
|definition=<br />
Пусть [[Основные_определения_теории_графов#.D0.9D.D0.B5.D0.BE.D1.80.D0.B8.D0.B5.D0.BD.D1.82.D0.B8.D1.80.D0.BE.D0.B2.D0.B0.D0.BD.D0.BD.D1.8B.D0.B5_.D0.B3.D1.80.D0.B0.D1.84.D1.8B|неориентированный граф]] <tex> G </tex> имеет <tex> n </tex> вершин: <tex> v_1, v_2, \ldots, v_n </tex>. Пусть <tex> d_i = \deg v_i \mbox{ } (i = \overline{1, n}) </tex> и вершины графа упорядочены таким образом, что <tex> d_1 \leq d_2 \leq \ldots \leq d_n </tex>. Последовательность <tex> d_1, d_2, \ldots, d_n </tex> называют '''последовательностью степеней''' графа <tex> G </tex>.<br />
}}<br />
<br />
{{Лемма<br />
|about=<br />
О добавлении ребра в граф<br />
|statement=<br />
Пусть неориентированный граф <tex> G' </tex> получен из неориентированного графа <tex> G </tex> добавлением одного нового ребра <tex> e </tex>. Тогда последовательность степеней графа <tex> G </tex> мажорируется последовательностью степеней графа <tex> G' </tex>.<br />
|proof=<br />
''Замечание'': Если в неубывающей последовательности <tex> d_1, d_2, \ldots, d_n </tex> увеличить на единицу число <tex> d_i </tex>, а затем привести последовательность к неубывающему виду, переставив число <tex> d_i + 1 </tex> на положенное место <tex> j </tex>, то исходная последовательность будет мажорироваться полученной. Если <tex>j = i</tex>, то утверждение леммы, очевидно, выполняется. Пусть <tex>j \neq i</tex>.<br />
[[Файл: Hvatal_1.png|270px|thumb|center|Исходная последовательность степеней <tex> d </tex>]]<br />
<br />
* Рассмотрим элементы с номерами <tex> s = \overline{1, i - 1} </tex>. Они не изменились, следовательно мажорируются собой.<br />
* Рассмотрим элементы с номерами <tex> s = \overline{i, j - 1} </tex>. <tex> s </tex>-й элемент полученной последовательности равен <tex> s + 1 </tex>-му элементу исходной. <tex> d_s \leq d_{s + 1} \Rightarrow d_s \leq d'_s = d_{s + 1} </tex>.<br />
* Расмотрим <tex>j</tex>-ый элемент. Имеем <tex>d'_j \ge d'_{j-1} = d_{j} </tex>.<br />
* Рассмотрим элементы с номерами <tex> s = \overline{j + 1, n} </tex>. Они не изменились, следовательно мажорируются собой.<br />
[[Файл: Hvatal_2.png|290px|thumb|center|Новая последовательность степеней <tex> d' </tex>]]<br />
При добавлении в граф ребра <tex> e = uv, \mbox{ } (u \neq v) </tex>, степени вершин <tex> u </tex> и <tex> v </tex> увеличатся на единицу. Для доказательства леммы, дважды воспользуемся замечанием.<br />
Значит, последовательность степеней полученного графа мажорирует последовательность степеней исходного, q.e.d.<br />
}}<br />
<br />
{{Теорема<br />
|about=<br />
Хватал<br />
|statement=<br />
Пусть:<br />
* <tex> G </tex> — [[Отношение_связности,_компоненты_связности#.D0.A1.D0.BB.D1.83.D1.87.D0.B0.D0.B9_.D0.BD.D0.B5.D0.BE.D1.80.D0.B8.D0.B5.D0.BD.D1.82.D0.B8.D1.80.D0.BE.D0.B2.D0.B0.D0.BD.D0.BD.D0.BE.D0.B3.D0.BE_.D0.B3.D1.80.D0.B0.D1.84.D0.B0|связный граф]],<br />
* <tex> n = |VG| \geq 3 </tex> — количество вершин,<br />
* <tex> d_1 \leq d_2 \leq \ldots \leq d_n </tex> — его последовательность степеней.<br />
Тогда если <tex> \forall k \in \mathbb N </tex> верна импликация: <br><br />
<center><tex> d_k \leq k < n/2 \rightarrow d_{n - k} \geq n - k, (*) </tex></center><br />
то граф <tex> G </tex> [[Гамильтоновы_графы#.D0.9E.D1.81.D0.BD.D0.BE.D0.B2.D0.BD.D1.8B.D0.B5_.D0.BE.D0.BF.D1.80.D0.B5.D0.B4.D0.B5.D0.BB.D0.B5.D0.BD.D0.B8.D1.8F|гамильтонов]].<br />
|proof=<br />
Для доказательства теоремы, докажем 3 леммы.<br />
{{Лемма<br />
|about=<br />
1<br />
|statement=<br />
<tex> d_k \leq k \Leftrightarrow |\{ v \in VG | d_v \leq k \}| \geq k. </tex><br />
|proof=<br />
"<tex> \Rightarrow </tex>" Пусть:<br />
* <tex> d_1 \leq d_2 \leq \ldots \leq d_k </tex>,<br />
* <tex> d_k \leq k </tex>,<br />
* <tex> |\{ d_1, d_2, \ldots, d_k \}| = k </tex>.<br />
<tex> \{ d_1, d_2, \ldots, d_k \} \subseteq \{ v \in VG | d_v \leq k \} \Rightarrow |\{ v \in VG | d_v \leq k \}| \geq k </tex>, q.e.d.<br />
<br />
"<tex> \Leftarrow </tex>" Пусть:<br />
* <tex> |\{ v \in VG | d_v \leq k \}| = k + p </tex>,<br />
* <tex> p \geq 0 </tex>.<br />
Расположим вершины в неубывающем порядке их степеней. <br><br />
<tex> d_1 \leq d_2 \leq \ldots \leq d_k \leq \ldots \leq d_{k + p} \leq k \Rightarrow d_k \leq k </tex>, q.e.d.<br />
}}<br />
<br />
{{Лемма<br />
|about=<br />
2<br />
|statement=<br />
<tex>\ d_{n - k} \geq n - k \Leftrightarrow |\{ v \in VG | d_v \geq n - k \}| \geq k + 1. </tex><br />
|proof=<br />
"<tex> \Rightarrow </tex>" Пусть:<br />
* <tex> d_{n - k} \geq n - k </tex>,<br />
* <tex> d_{n - k} \leq d_{n - k + 1} \leq \ldots \leq d_n </tex>, <br />
* <tex> |\{ d_{n - k}, d_{n - k + 1}, \ldots , d_n \}| = k + 1 </tex>.<br />
<tex> \{ d_{n - k}, d_{n - k + 1}, \ldots , d_n \} \subseteq \{ v \in VG | d_v \geq n - k \} \Rightarrow \{ v \in VG | d_v \geq n - k \} \geq k + 1 </tex>, q.e.d.<br />
<br />
"<tex> \Leftarrow </tex>" Пусть:<br />
* <tex> |\{ v \in VG | d_v \geq n - k \}| = k + 1 + p, (p \geq 0)</tex>,<br />
Расположим вершины в неубывающем порядке их степеней.<br />
<tex> d_n \geq d_{n - 1} \ldots \geq d_{n - k} \geq \ldots \geq d_{n - k - p} \geq n - k \Rightarrow d_{n - k} \geq n - k </tex>, q.e.d. <br />
}}<br />
<br />
{{Лемма<br />
|about=<br />
3<br />
|statement=<br />
Если импликация <tex> (*) </tex> верна для некоторой последовательности степеней <tex> d </tex>, то она верна и для неубывающей последовательности <tex> d' </tex>, мажорирующей <tex> d </tex>.<br />
|proof=<br />
# Пусть <tex> d'_k > k </tex>. Тогда первый аргумент импликации всегда ложен, следовательно импликация верна вне зависимости от второго аргумента. Значит, в этом случае импликация <tex> (*) </tex> верна для последовательности <tex> d' </tex>.<br />
# Пусть <tex> d'_k \leq k, \mbox{ } d'_{n - k} \geq d_{n - k} \geq n - k </tex>. Тогда оба аргумента импликации всегда истинны. Значит, и в этом случае импликация <tex> (*) </tex> верна для последовательности <tex> d' </tex>.<br />
Значит, импликация <tex> (*) </tex> выполняется и для последовательности <tex> d' </tex>, q.e.d.<br />
}}<br />
<br />
Приведем доказательство от противного.<br />
<br />
Пусть существует граф с числом вершин <tex> n \geq 3 </tex>, удовлетворяющий <tex> (*) </tex>, но негамильтонов.<br />
Будем добавлять в него ребра до тех пор, пока не получим максимально возможный негамильтонов граф <tex> G </tex> (то есть добавление еще одного ребра сделает граф <tex> G </tex> гамильтоновым). <br />
По лемме о добавлении ребра и лемме №3 импликация <tex> (*) </tex> остается верной для графа <tex> G </tex>.<br />
Очевидно, что граф <tex>\ K_n </tex> гамильтонов при <tex> k \geq 3 </tex>.<br />
Будем считать <tex> G </tex> максимальным негамильтоновым остовным подграфом графа <tex> K_n </tex>.<br />
<br />
Выберем две несмежные вершины <tex> u </tex> и <tex> v </tex> графа <tex> G </tex>, такие что <tex> \deg u + \deg v </tex> — максимально.<br />
Будем считать, что <tex> \deg u \leq \deg v </tex>.<br />
Добавив к <tex> G </tex> новое ребро <tex> e = uv </tex>, получим гамильтонов граф <tex> G + e </tex>.<br />
Рассмотрим гамильтонов цикл графа <tex> G + e </tex>: в нём обязательно присутствует ребро <tex> e </tex>.<br />
Отбрасывая ребро <tex> e </tex>, получим гамильтонову <tex> (u, v) </tex>-цепь в графе <tex> G </tex>: <tex> u = u_1 \rightarrow u_2 \rightarrow \ldots \rightarrow u_n = v </tex>.<br />
<br />
Пусть <tex> S = \{ i | e_i = u_1 u_{i + 1} \in EG\}, T = \{ i |f_i = u_i u_n \in EG\} </tex>.<br />
[[Файл: Hvatal_3.png|330px|thumb|center|Множество <tex> S </tex> обозначено красным цветом, множество <tex> T </tex> обозначено синим цветом]]<br />
<br />
{{Утверждение<br />
|statement=<br />
<tex> S \cap T = \emptyset </tex>.<br />
|proof=<br />
Пусть <tex> j \in S \cap T </tex>. Тогда получим гамильтонов цикл графа <tex> G </tex>: <tex> u_1 \xrightarrow{e_j} u_{j + 1} \rightarrow \ldots \rightarrow u_n \xrightarrow{f_j} u_j \rightarrow u_{j - 1} \rightarrow \ldots \rightarrow u_1 </tex>, что противоречит условию, что граф негамильтонов.<br />
[[Файл: Hvatal_4.png|270px|thumb|center|]]<br />
Значит, <tex> S \cap T </tex>, q.e.d.<br />
}}<br />
<br />
Из определений <tex> S </tex> и <tex> T </tex> следует, что <tex> S \cup T \subseteq \{1, 2, ..., n - 1 \} \Rightarrow 2 \deg u \leq \deg u + \deg v = |S| + |T| = |S \cup T| < n </tex>. Значит, <tex> \deg u < n/2 </tex>.<br />
<br />
Так как <tex> S \cap T = \emptyset </tex>, ни одна вершина <tex> u_j </tex> не смежна с <tex> v = u_n </tex> (для <tex> j \in S </tex>). В силу выбора <tex> u </tex> и <tex> v </tex>, получим, что <tex> \deg u_j \leq \deg u </tex>. Пусть <tex> k = \deg u = |S| </tex>. Значит, <tex> \exists k </tex> вершин, степень которых не превосходит <tex> k </tex>.<br />
<br />
По лемме №1: <tex> d_k \leq k < n/2 </tex>. В силу импликации <tex> (*) </tex>: <tex> d_{n - k} \geq n - k </tex>.<br />
<br />
По лемме №2, <tex> \exists k + 1 </tex> вершин, степень которых не меньше <tex> n - k </tex>.<br />
<br />
Так как <tex> k = \deg u </tex>, то вершина <tex> u </tex> может быть смежна максимум с <tex> k </tex> из этих <tex> k+1 </tex> вершин. Значит, существует вершина <tex> w </tex>, не являющаяся смежной с <tex> u </tex> и для которой <tex> \deg w \geq n - k </tex>. Тогда получим, что <tex> \deg u + \deg w \geq k + (n - k) = n > \deg u + \deg v </tex>, что противоречит выбору <tex> u </tex> и <tex> v </tex>.<br />
<br />
Значит, предположение неверно, q.e.d.<br />
}}<br />
<br />
==См. также==<br />
* [[Гамильтоновы графы]]<br />
* [[Теорема Дирака]]<br />
* [[Теорема Оре]]<br />
<br />
== Литература ==<br />
* Асанов М., Баранский В., Расин В.: ''Дискретная математика: Графы, матроиды, алгоритмы''<br />
<br />
[[Категория: Алгоритмы и структуры данных]]<br />
[[Категория: Обходы графов]]</div>Андрей Козловhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%9E%D1%82%D0%BD%D0%BE%D1%88%D0%B5%D0%BD%D0%B8%D0%B5_%D0%B2%D0%B5%D1%80%D1%88%D0%B8%D0%BD%D0%BD%D0%BE%D0%B9_%D0%B4%D0%B2%D1%83%D1%81%D0%B2%D1%8F%D0%B7%D0%BD%D0%BE%D1%81%D1%82%D0%B8&diff=21183Отношение вершинной двусвязности2012-04-24T07:32:56Z<p>Андрей Козлов: </p>
<hr />
<div>==Вершинная двусвязность==<br />
{{Определение<br />
|definition=<br />
Два ребра [[Основные определения: граф, ребро, вершина, степень, петля, путь, цикл|графа]] называются '''вершинно двусвязными''', если существуют вершинно непересекающиеся пути, соединяющие их концы.<br />
}}<br />
Заметим, что если имеется два различных двусвязных ребра, то они лежат на некотором вершинно простом цикле.<br />
<br />
<br />
{{Теорема<br />
|statement=<br />
Отношение вершинной двусвязности является отношением эквивалентности на ребрах.<br />
|proof=<br />
[[Файл: Vertex_biconnected.png|370px|thumb|right|К доказательству транзитивности]]<br />
'''Рефлексивность:'''<br />
В данном случае имеем 2 пустых пути, которые, очевидно, не пересекаются.<br />
<br />
'''Симметричность:'''<br />
Следует из симметричности определения.<br />
<br />
'''Транзитивность:'''<br />
Пусть имеем ребра: <tex>ef</tex> вершинно двусвязно с <tex>cd</tex>, <tex>cd</tex> вершинно двусвязно с <tex>ab</tex>, при этом все они различны. Ребра <tex>ef</tex> и <tex>cd</tex> лежат на вершинно простом цикле <tex>C</tex>. Будем считать, что существуют непересекающиеся пути <tex>P : a \leadsto c</tex>, <tex>Q : b \leadsto d</tex> (ситуация, когда они идут наоборот, разбирается аналогично). Пусть <tex>x</tex> {{---}} первая вершина на <tex>P</tex>, лежащая также на <tex>C</tex>, <tex>y</tex> {{---}} первая вершина на <tex>Q</tex>, лежащая на <tex>C</tex>. Проделав пути от <tex>a</tex> до <tex>x</tex> и от <tex>b</tex> до <tex>y</tex>, далее пойдем по циклу <tex>C</tex> в нужные (различные) стороны, чтобы достичь <tex>e</tex> и <tex>f</tex>.<br />
}}<br />
<br />
''Замечание.'' Рассмотрим следующее определение: вершины <tex>u</tex> и <tex>v</tex> называются вершинно двусвязными, если между ними существуют 2 пути, не пересекающихся по вершинам, за исключением концов. Это определение не может претендовать на корректность, так как в этом случае отношение вершинной двусвязности перестанет быть транзитивным.<br />
<br />
==Блоки==<br />
{{Определение<br />
|definition=<br />
'''Блоками''', или компонентами вершинной двусвязности графа, называют его подграфы, множества ребер которых - классы эквивалентности вершинной двусвязности, а множества вершин {{---}} множества всевозможных концов ребер из соответствующих классов.<br />
}}<br />
<br />
==Точки сочленения==<br />
{{main|Точка сочленения, эквивалентные определения}}<br />
{{Определение<br />
|definition=<br />
'''Точка сочленения''' графа <tex>G</tex> {{---}} вершина, принадлежащая как минимум двум блокам <tex>G</tex>.<br />
}}<br />
{{Определение<br />
|definition=<br />
'''Точка сочленения''' графа <tex>G</tex> {{---}} вершина, при удалении которой в <tex>G</tex> увеличивается число компонент связности.<br />
}}<br />
<br />
==Литература==<br />
* Харари, Ф. Теория графов. — М.: Книжный дом «ЛИБРОКОМ», 2009<br />
<br />
== См. также ==<br />
* [[Отношение реберной двусвязности]]<br />
<br />
[[Категория:Алгоритмы и структуры данных]]<br />
[[Категория:Связность в графах]]</div>Андрей Козловhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%9E%D1%82%D0%BD%D0%BE%D1%88%D0%B5%D0%BD%D0%B8%D0%B5_%D1%80%D1%91%D0%B1%D0%B5%D1%80%D0%BD%D0%BE%D0%B9_%D0%B4%D0%B2%D1%83%D1%81%D0%B2%D1%8F%D0%B7%D0%BD%D0%BE%D1%81%D1%82%D0%B8&diff=21182Отношение рёберной двусвязности2012-04-24T07:31:47Z<p>Андрей Козлов: /* Реберная двусвязность */</p>
<hr />
<div>== Реберная двусвязность ==<br />
{{Определение<br />
|definition =<br />
Две вершины <tex>u</tex> и <tex> v</tex> [[Основные определения теории графов|графа]] <tex>G</tex> называются '''реберно двусвязными''', если между этими вершинами существуют два реберно непересекающихся пути.<br />
}}<br />
<br />
{{Теорема<br />
|statement=<br />
Отношение реберной двусвязности является отношением эквивалентности на вершинах.<br />
|proof=<br />
<br />
<br />
Пусть <tex>R</tex> {{---}} отношение реберной двусвязности.[[Файл: Edge_biconnected.png|right|300px|thumb|К доказательству транзитивности.]]<br />
<br />
'''Рефлексивность:''' <tex>(u, u)\in R. </tex> (Очевидно)<br />
<br />
'''Симметричность:''' <tex>(u, v)\in R \Rightarrow (v, u)\in R. </tex> (Очевидно)<br />
<br />
'''Транзитивность:''' <tex>(u, v)\in R </tex> и <tex>(v, w)\in R \Rightarrow (u, w)\in R. </tex><br />
<br />
''Доказательство:''<br />
Пусть из <tex> w </tex> в <tex> v </tex> есть два реберно непересекающихся пути, <tex> P_1 </tex> и <tex> P_2 </tex> соответственно. Обозначим за <tex> C </tex> объединение двух реберно непересекающихся путей из <tex> u </tex> в <tex> v </tex>. <br />
<tex> C </tex> будет реберно-простым циклом. <br />
Пусть вершины <tex>a</tex> и <tex>b</tex> {{---}} первые со стороны <tex>w</tex> вершины на пересечении <tex> P_1 </tex> и <tex> P_2 </tex> с <tex> C </tex> соответственно.<br />
Рассмотрим два пути <tex> wau </tex> и <tex> wbu </tex>, такие, что части <tex> au </tex> и <tex> bu </tex> идут в разные стороны по циклу <tex> C </tex>. Наличие двух таких реберно непересекающихся путей очевидно, а значит <tex> u </tex> и <tex> w </tex> реберно двусвязны.<br />
<br />
<br />
}}<br />
<br />
== Компоненты реберной двусвязности ==<br />
<br />
{{Определение<br />
|definition =<br />
'''Компонентами реберной двусвязности''' графа называют его подграфы, множества вершин которых - классы эквивалентности реберной двусвязности, а множества ребер - множества ребер из соответствующих классов эквивалентности.<br />
}}<br />
<br />
== См. также ==<br />
*[[Отношение вершинной двусвязности]]<br />
*[http://rain.ifmo.ru/cat/view.php/vis/graph-general/biconnected-components-2005 Визуализатор - компоненты двусвязности]<br />
<br />
== Литература ==<br />
* Харари Фрэнк '''Теория графов''' = Graph theory/Пер. с англ. и предисл. В. П. Козырева. Под ред. Г.П.Гаврилова. Изд. 2-е. — М.: Едиториал УРСС, 2003. — 60 с. — ISBN 5-354-00301-6<br />
<br />
[[Категория:Алгоритмы и структуры данных]]<br />
[[Категория:Связность в графах]]</div>Андрей Козловhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%9C%D0%B0%D1%82%D1%80%D0%B8%D1%86%D0%B0_%D1%81%D0%BC%D0%B5%D0%B6%D0%BD%D0%BE%D1%81%D1%82%D0%B8_%D0%B3%D1%80%D0%B0%D1%84%D0%B0&diff=21181Матрица смежности графа2012-04-24T07:29:37Z<p>Андрей Козлов: </p>
<hr />
<div>__NOTOC__<br />
{{Определение<br />
|definition ='''Матрицей смежности''' (англ. Adjacency matrix) <tex>A=||\alpha_{i,j}||</tex> ''помеченного графа'' <tex>G(V,E)</tex> называется матрица <tex>A_{[V\times{}V]}</tex>, в которой <tex>\alpha_{i,j}</tex> — количество рёбер, соединяющих вершины <tex>v_i</tex> и <tex>v_j</tex>, причём при <tex>i=j</tex> каждую петлю учитываем дважды, если граф не является ориентированным, и один раз, если граф ориентирован.<br />
}}<br />
<br />
== Пример ==<br />
{| border="1" cellpadding="5" cellspacing="0" style="text-align:center"<br />
!style="background:#f2f2f2"|Граф<br />
!style="background:#f2f2f2"|Матрица смежности<br />
|-<br />
|style="background:#f9f9f9"|[[Файл: Adjacency matrix.png|180px]]<br />
|style="background:#f9f9f9"|<tex>\begin{pmatrix}<br />
0 & 1 & 0 & 0 & 1\\<br />
1 & 0 & 1 & 1 & 1\\<br />
0 & 1 & 0 & 1 & 0\\<br />
0 & 1 & 1 & 0 & 1\\<br />
1 & 1 & 0 & 1 & 0\\<br />
\end{pmatrix}</tex><br />
|}<br />
<br />
== Свойства ==<br />
Для графов без петель и кратных рёбер матрица смежности бинарна (состоит из нулей и единиц), причём её главная диагональ целиком состоит из нулей.<br />
<br />
=== Случай ориентированного графа ===<br />
Сумма элементов <tex>i</tex>-й строки равна <tex>deg^- v_i</tex>, то есть <tex>\sum\limits_{j=1}^{n}\alpha_{i,j} = deg^- v_i</tex>.<br />
Аналогично сумма элементов <tex>j</tex>-го стоблца равна <tex>deg^+ v_j</tex>, то есть <tex>\sum\limits_{i=1}^{n}\alpha_{i,j} = deg^+ v_j</tex>.<br />
<br />
=== Случай неориентированного графа ===<br />
Для неориентированных графов матрица смежности является симметричной.<br />
<br />
Сумма элементов <tex>i</tex>-й строки равна <tex>deg \; v_i</tex>, то есть <tex>\sum\limits_{j=1}^{n}\alpha_{i,j} = deg \; v_i</tex>. Вследствие симметричности суммы элементов <tex>i</tex>-й строки и <tex>i</tex>-го столбца равны.<br />
<br />
== См. также ==<br />
* [[Связь степени матрицы смежности и количества путей]]<br />
* [[Матрица инцидентности графа]]<br />
== Литература ==<br />
* Харари Фрэнк '''Теория графов''' = Graph theory/Пер. с англ. и предисл. В. П. Козырева. Под ред. Г.П.Гаврилова. Изд. 2-е. — М.: Едиториал УРСС, 2003. — 296 с. — ISBN 5-354-00301-6<br />
* Асанов М. О., Баранский В. А., Расин В. В. '''Дискретная математика: графы, матроиды, алгоритмы''' — НИЦ РХД, 2001. — 288 с. — ISBN 5-93972-076-5<br />
<br />
[[Категория: Алгоритмы и структуры данных]]<br />
[[Категория: Основные определения теории графов]]</div>Андрей Козловhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%9E%D1%81%D0%BD%D0%BE%D0%B2%D0%BD%D1%8B%D0%B5_%D0%BE%D0%BF%D1%80%D0%B5%D0%B4%D0%B5%D0%BB%D0%B5%D0%BD%D0%B8%D1%8F_%D1%82%D0%B5%D0%BE%D1%80%D0%B8%D0%B8_%D0%B3%D1%80%D0%B0%D1%84%D0%BE%D0%B2&diff=21180Основные определения теории графов2012-04-24T07:27:33Z<p>Андрей Козлов: /* Неориентированные графы */</p>
<hr />
<div>==Ориентированные графы==<br />
<br />
{{Определение<br />
|definition =<br />
'''Ориентированным графом''' (directed graph) <tex>G</tex> называется пара <tex>G = (V, E)</tex>, где <tex>V</tex> {{---}} конечное множество вершин, а <tex> E \subset V \times V </tex> {{---}} множество рёбер.<br />
}}<br />
<br />
{{Определение<br />
|definition =<br />
'''Ребром''' (edge, дугой (arc), линией (line)) ориентированного графа называют упорядоченную пару вершин <tex> (v, u) \in E </tex>.<br />
}}<br />
<br />
В графе ребро, концы которого совпадают, то есть <tex>e=(v,v)</tex>, называется <b>петлей</b>. Мультиграф с петлями принято называть '''псевдографом'''.<br />
<br />
Если имеется ребро <tex> (v, u) \in E </tex>, то говорят:<br />
* <tex> v </tex> {{---}} '''предок''' <tex> u </tex>.<br />
* <tex> u </tex> и <tex> v </tex> {{---}} '''смежные'''<br />
* Вершина <tex> u </tex> '''инцидентна''' ребру <tex> (v, u) </tex><br />
* Вершина <tex> v </tex> '''инцидентна''' ребру <tex> (v, u) </tex><br />
<br />
'''Инцидентность''' {{---}} понятие, используемое только в отношении ребра и вершины. Две вершины или два ребра не могут быть инцидентны.<br />
<br />
Граф с <tex> p </tex> вершинами и <tex> q </tex> ребрами называют <tex> (p, q) </tex> - графом. <tex> (1, 0) </tex>-граф называют <b>тривиальным</b>.<br />
<br />
Заметим, что по определению ориентированного графа, данному выше, любые две вершины <tex>u,~v</tex> нельзя соединить более чем одним ребром <tex>(u, v)</tex>.<br />
Поэтому часто используют другое определение. <br />
{{Определение<br />
|id = def1<br />
|definition =<br />
'''Ориентированным графом''' <tex>G</tex> называется четверка <tex>G = (V, E, beg, end)</tex> , где <tex>beg, end : E \rightarrow V </tex>, а <tex>V</tex> и <tex>E</tex> {{---}} некоторые абстрактные множества.<br />
}}<br />
Иногда граф, построенный таким образом, называют '''мультиграфом'''. В мультиграфе не допускаются петли, но пары вершин допускается соединять более чем одним ребром. Такие ребра называются '''кратными''' (иначе {{---}} '''параллельные''').<br />
{|border="0" cellpadding="5" width=30% align=center<br />
|[[Файл: Graph_definition_1.png|thumb|210px|center|<font color=#ff2a2a>Красным</font> выделено кратное ребро (6, 2)<br><font color=#71c837>Зеленым</font> обозначена петля (6, 6)]]<br />
|[[Файл: Multi_graph.png|thumb|150px|center|Мультиграф]]<br />
|[[Файл: Pseudo_graph.png|thumb|150px|center|Псевдограф]]<br />
|<br />
|}<br />
<br />
<br />
<br />
Также для ориентированных графов определяют '''полустепень исхода вершины''' <tex>deg^-v_i = |\{e~|~beg~e = v_i\}|</tex> и '''полустепень захода вершины''' <tex>deg^+v_i = |\{e~|~end~e = v_i\}|</tex>.<br />
<br />
Стоит отметить, что для ориентированного графа справедлива [[Лемма о рукопожатиях|лемма о рукопожатиях]], связывающая количество ребер с суммой [[Основные определения теории графов#Степень вершины|степеней вершин]].<br />
<br />
<br />
{{Определение<br />
|definition =<br />
'''Путём''' (маршрутом) в графе называется последовательность вида <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> {{---}} '''длина''' пути.<br />
}}<br />
{{Определение<br />
|definition =<br />
'''Циклическим путём''' называется путь, в котором <tex>v_0 = v_k</tex>.<br />
}}<br />
{{Определение<br />
|definition =<br />
'''Цикл''' - это класс эквивалентности циклических путей на отношении эквивалентности таком, что два пути эквивалентны, если <tex> \exists j : \forall i \Rightarrow e_{(i \mod k)} = e'_{(i + j) \mod k}</tex>; где <tex>e</tex> и <tex>e'</tex> {{---}} это две последовательности ребер в циклическом пути.<br />
}}<br />
<br />
==Неориентированные графы==<br />
{{Определение<br />
|definition =<br />
'''Неориентированным графом''' (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> {{---}} множество рёбер.<br />
}}<br />
{{Определение<br />
|definition =<br />
'''Ребром''' в неориентированном графе называют неупорядоченную пару вершин <tex> (v, u) \in E </tex>.<br />
}}<br />
[[Файл: Graph_definition_2.png|thumb|210px|center|Неориентированный граф<br>]]<br />
Иное определение:<br />
<br />
{{Определение<br />
|definition =<br />
'''Неориентированным графом''' <tex>G</tex> называется тройка <tex>G = (V, E, ends)</tex> , где <tex>ends : E \rightarrow V \times V</tex>, а <tex>V</tex> и <tex>E</tex> {{---}} некоторые абстрактные множества. <br />
}}<br />
<br />
Две вершины называются '''смежными''', если между ними есть ребро.<br />
<br />
'''Степенью''' вершины <tex>deg~v_i</tex> в неориентированном графе называют число ребер, инцидентных <tex>v_i</tex>. Будем считать, что петли добавляют к степени вершины <tex>2</tex>.<br />
<br />
{{Определение<br />
|definition =<br />
'''Циклическим путём''' в неориентированном графе называется путь, в котором <tex>v_0 = v_k</tex>, а так же <tex> e_i \ne e_{(i+1) \mod k}</tex>.<br />
}}<br />
<br />
Остальные определения в неориентированном графе совпадают с аналогичными определениями в ориентированном графе.<br />
<br />
== Представление графов ==<br />
<br />
=== Матрица и списки смежности ===<br />
<br />
Граф можно представить в виде [[Матрица смежности графа|матрицы смежности]], где <tex>graph[v][u] = true \Leftrightarrow (v, u) \in E</tex>. Также в ячейке матрицы можно хранить вес ребра или их количество (если в графе разрешены паралелльные ребра).<br />
Для матрицы смежности существует [[Связь степени матрицы смежности и количества путей|теорема]], позволяющая связать степень матрицы и количество путей из вершины <tex>v</tex> в вершину <tex>u</tex>.<br />
<br />
Если граф разрежен (<tex>|E| < |V^2|</tex>), его лучше представить в виде списков смежности, где список для вершины <tex>v</tex> будет содержать вершины <tex>u: (v, u) \in E</tex>. Данный способ позволит сэкономить память, т.к. не придется хранить много нулей.<br />
<br />
=== Матрица инцидентности ===<br />
<br />
Имеет место и другое представление графа - [[Матрица инцидентности графа|матрица инцидентности]], которая сопоставляет множество вершин множеству ребер. То есть:<br />
# <tex>graph[v][j] = 1 \wedge graph[u][j] = -1 \Leftrightarrow v = begin (e_j) \wedge u = end (e_j)</tex>, в случае ориентированного графа.<br />
# <tex>graph[v][j] = 1 \Leftrightarrow v</tex> инцидентна ребру <tex>e_j</tex>, в случае неориентированного графа.<br />
# Во всех остальных случаях ячейки матрицы равны 0.<br />
<br />
==См. также==<br />
* [[Лемма о рукопожатиях]]<br />
* [[Матрица смежности графа]]<br />
* [[Связь степени матрицы смежности и количества путей]]<br />
<br />
==Литература==<br />
* Харари Фрэнк '''Теория графов''' = Graph theory/Пер. с англ. и предисл. В. П. Козырева. Под ред. Г.П.Гаврилова. Изд. 2-е. — М.: Едиториал УРСС, 2003. — 296 с. — ISBN 5-354-00301-6<br />
* Асанов М. О., Баранский В. А., Расин В. В. '''Дискретная математика: графы, матроиды, алгоритмы''' — НИЦ РХД, 2001. — 288 с. — ISBN 5-93972-076-5<br />
* ''Кормен, Томас Х., Лейзерсон, Чарльз И., Ривест, Рональд Л., Штайн Клиффорд'' '''Алгоритмы: построение и анализ''', 2-е издание. Пер. с англ. — М.:Издательский дом "Вильямс", 2010. — 1296 с.: ил. — Парал. тит. англ. — ISBN 978-5-8459-0857-5 (рус.)<br />
<br />
<br />
[[Категория: Алгоритмы и структуры данных]]<br />
[[Категория: Основные определения теории графов]]</div>Андрей Козловhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%9E%D1%81%D0%BD%D0%BE%D0%B2%D0%BD%D1%8B%D0%B5_%D0%BE%D0%BF%D1%80%D0%B5%D0%B4%D0%B5%D0%BB%D0%B5%D0%BD%D0%B8%D1%8F_%D1%82%D0%B5%D0%BE%D1%80%D0%B8%D0%B8_%D0%B3%D1%80%D0%B0%D1%84%D0%BE%D0%B2&diff=21179Основные определения теории графов2012-04-24T07:26:57Z<p>Андрей Козлов: /* Ориентированные графы */</p>
<hr />
<div>==Ориентированные графы==<br />
<br />
{{Определение<br />
|definition =<br />
'''Ориентированным графом''' (directed graph) <tex>G</tex> называется пара <tex>G = (V, E)</tex>, где <tex>V</tex> {{---}} конечное множество вершин, а <tex> E \subset V \times V </tex> {{---}} множество рёбер.<br />
}}<br />
<br />
{{Определение<br />
|definition =<br />
'''Ребром''' (edge, дугой (arc), линией (line)) ориентированного графа называют упорядоченную пару вершин <tex> (v, u) \in E </tex>.<br />
}}<br />
<br />
В графе ребро, концы которого совпадают, то есть <tex>e=(v,v)</tex>, называется <b>петлей</b>. Мультиграф с петлями принято называть '''псевдографом'''.<br />
<br />
Если имеется ребро <tex> (v, u) \in E </tex>, то говорят:<br />
* <tex> v </tex> {{---}} '''предок''' <tex> u </tex>.<br />
* <tex> u </tex> и <tex> v </tex> {{---}} '''смежные'''<br />
* Вершина <tex> u </tex> '''инцидентна''' ребру <tex> (v, u) </tex><br />
* Вершина <tex> v </tex> '''инцидентна''' ребру <tex> (v, u) </tex><br />
<br />
'''Инцидентность''' {{---}} понятие, используемое только в отношении ребра и вершины. Две вершины или два ребра не могут быть инцидентны.<br />
<br />
Граф с <tex> p </tex> вершинами и <tex> q </tex> ребрами называют <tex> (p, q) </tex> - графом. <tex> (1, 0) </tex>-граф называют <b>тривиальным</b>.<br />
<br />
Заметим, что по определению ориентированного графа, данному выше, любые две вершины <tex>u,~v</tex> нельзя соединить более чем одним ребром <tex>(u, v)</tex>.<br />
Поэтому часто используют другое определение. <br />
{{Определение<br />
|id = def1<br />
|definition =<br />
'''Ориентированным графом''' <tex>G</tex> называется четверка <tex>G = (V, E, beg, end)</tex> , где <tex>beg, end : E \rightarrow V </tex>, а <tex>V</tex> и <tex>E</tex> {{---}} некоторые абстрактные множества.<br />
}}<br />
Иногда граф, построенный таким образом, называют '''мультиграфом'''. В мультиграфе не допускаются петли, но пары вершин допускается соединять более чем одним ребром. Такие ребра называются '''кратными''' (иначе {{---}} '''параллельные''').<br />
{|border="0" cellpadding="5" width=30% align=center<br />
|[[Файл: Graph_definition_1.png|thumb|210px|center|<font color=#ff2a2a>Красным</font> выделено кратное ребро (6, 2)<br><font color=#71c837>Зеленым</font> обозначена петля (6, 6)]]<br />
|[[Файл: Multi_graph.png|thumb|150px|center|Мультиграф]]<br />
|[[Файл: Pseudo_graph.png|thumb|150px|center|Псевдограф]]<br />
|<br />
|}<br />
<br />
<br />
<br />
Также для ориентированных графов определяют '''полустепень исхода вершины''' <tex>deg^-v_i = |\{e~|~beg~e = v_i\}|</tex> и '''полустепень захода вершины''' <tex>deg^+v_i = |\{e~|~end~e = v_i\}|</tex>.<br />
<br />
Стоит отметить, что для ориентированного графа справедлива [[Лемма о рукопожатиях|лемма о рукопожатиях]], связывающая количество ребер с суммой [[Основные определения теории графов#Степень вершины|степеней вершин]].<br />
<br />
<br />
{{Определение<br />
|definition =<br />
'''Путём''' (маршрутом) в графе называется последовательность вида <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> {{---}} '''длина''' пути.<br />
}}<br />
{{Определение<br />
|definition =<br />
'''Циклическим путём''' называется путь, в котором <tex>v_0 = v_k</tex>.<br />
}}<br />
{{Определение<br />
|definition =<br />
'''Цикл''' - это класс эквивалентности циклических путей на отношении эквивалентности таком, что два пути эквивалентны, если <tex> \exists j : \forall i \Rightarrow e_{(i \mod k)} = e'_{(i + j) \mod k}</tex>; где <tex>e</tex> и <tex>e'</tex> {{---}} это две последовательности ребер в циклическом пути.<br />
}}<br />
<br />
==Неориентированные графы==<br />
{{Определение<br />
|definition =<br />
'''Неориентированным графом''' (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> {{---}} множество рёбер.<br />
}}<br />
{{Определение<br />
|definition =<br />
'''Ребром''' в неориентированном графе называют неупорядоченную пару вершин <tex> (v, u) \in E </tex>.<br />
}}<br />
[[Файл: Graph_definition_2.png|thumb|350px|center|Неориентированный граф<br>]]<br />
Иное определение:<br />
<br />
{{Определение<br />
|definition =<br />
'''Неориентированным графом''' <tex>G</tex> называется тройка <tex>G = (V, E, ends)</tex> , где <tex>ends : E \rightarrow V \times V</tex>, а <tex>V</tex> и <tex>E</tex> {{---}} некоторые абстрактные множества. <br />
}}<br />
<br />
Две вершины называются '''смежными''', если между ними есть ребро.<br />
<br />
'''Степенью''' вершины <tex>deg~v_i</tex> в неориентированном графе называют число ребер, инцидентных <tex>v_i</tex>. Будем считать, что петли добавляют к степени вершины <tex>2</tex>.<br />
<br />
{{Определение<br />
|definition =<br />
'''Циклическим путём''' в неориентированном графе называется путь, в котором <tex>v_0 = v_k</tex>, а так же <tex> e_i \ne e_{(i+1) \mod k}</tex>.<br />
}}<br />
<br />
Остальные определения в неориентированном графе совпадают с аналогичными определениями в ориентированном графе.<br />
<br />
== Представление графов ==<br />
<br />
=== Матрица и списки смежности ===<br />
<br />
Граф можно представить в виде [[Матрица смежности графа|матрицы смежности]], где <tex>graph[v][u] = true \Leftrightarrow (v, u) \in E</tex>. Также в ячейке матрицы можно хранить вес ребра или их количество (если в графе разрешены паралелльные ребра).<br />
Для матрицы смежности существует [[Связь степени матрицы смежности и количества путей|теорема]], позволяющая связать степень матрицы и количество путей из вершины <tex>v</tex> в вершину <tex>u</tex>.<br />
<br />
Если граф разрежен (<tex>|E| < |V^2|</tex>), его лучше представить в виде списков смежности, где список для вершины <tex>v</tex> будет содержать вершины <tex>u: (v, u) \in E</tex>. Данный способ позволит сэкономить память, т.к. не придется хранить много нулей.<br />
<br />
=== Матрица инцидентности ===<br />
<br />
Имеет место и другое представление графа - [[Матрица инцидентности графа|матрица инцидентности]], которая сопоставляет множество вершин множеству ребер. То есть:<br />
# <tex>graph[v][j] = 1 \wedge graph[u][j] = -1 \Leftrightarrow v = begin (e_j) \wedge u = end (e_j)</tex>, в случае ориентированного графа.<br />
# <tex>graph[v][j] = 1 \Leftrightarrow v</tex> инцидентна ребру <tex>e_j</tex>, в случае неориентированного графа.<br />
# Во всех остальных случаях ячейки матрицы равны 0.<br />
<br />
==См. также==<br />
* [[Лемма о рукопожатиях]]<br />
* [[Матрица смежности графа]]<br />
* [[Связь степени матрицы смежности и количества путей]]<br />
<br />
==Литература==<br />
* Харари Фрэнк '''Теория графов''' = Graph theory/Пер. с англ. и предисл. В. П. Козырева. Под ред. Г.П.Гаврилова. Изд. 2-е. — М.: Едиториал УРСС, 2003. — 296 с. — ISBN 5-354-00301-6<br />
* Асанов М. О., Баранский В. А., Расин В. В. '''Дискретная математика: графы, матроиды, алгоритмы''' — НИЦ РХД, 2001. — 288 с. — ISBN 5-93972-076-5<br />
* ''Кормен, Томас Х., Лейзерсон, Чарльз И., Ривест, Рональд Л., Штайн Клиффорд'' '''Алгоритмы: построение и анализ''', 2-е издание. Пер. с англ. — М.:Издательский дом "Вильямс", 2010. — 1296 с.: ил. — Парал. тит. англ. — ISBN 978-5-8459-0857-5 (рус.)<br />
<br />
<br />
[[Категория: Алгоритмы и структуры данных]]<br />
[[Категория: Основные определения теории графов]]</div>Андрей Козловhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%A4%D0%B0%D0%B9%D0%BB:Planar_vertex_biconnected_3.png&diff=21152Файл:Planar vertex biconnected 3.png2012-04-23T21:14:06Z<p>Андрей Козлов: загружена новая версия «Файл:Planar vertex biconnected 3.png»</p>
<hr />
<div></div>Андрей Козловhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%A4%D0%B0%D0%B9%D0%BB:Planar_vertex_biconnected_2.png&diff=21151Файл:Planar vertex biconnected 2.png2012-04-23T21:11:39Z<p>Андрей Козлов: загружена новая версия «Файл:Planar vertex biconnected 2.png»</p>
<hr />
<div></div>Андрей Козловhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%A4%D0%B0%D0%B9%D0%BB:Planar_vertex_biconnected_1.png&diff=21150Файл:Planar vertex biconnected 1.png2012-04-23T21:09:46Z<p>Андрей Козлов: загружена новая версия «Файл:Planar vertex biconnected 1.png»</p>
<hr />
<div></div>Андрей Козловhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%A4%D0%B0%D0%B9%D0%BB:Planar_vertex_biconnected_2.png&diff=21149Файл:Planar vertex biconnected 2.png2012-04-23T21:06:11Z<p>Андрей Козлов: загружена новая версия «Файл:Planar vertex biconnected 2.png»</p>
<hr />
<div></div>Андрей Козловhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%A4%D0%B0%D0%B9%D0%BB:Planar_vertex_biconnected_1.png&diff=21147Файл:Planar vertex biconnected 1.png2012-04-23T21:03:12Z<p>Андрей Козлов: загружена новая версия «Файл:Planar vertex biconnected 1.png»</p>
<hr />
<div></div>Андрей Козловhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%A4%D0%B0%D0%B9%D0%BB:Planar_edge_biconnected_1.png&diff=21145Файл:Planar edge biconnected 1.png2012-04-23T20:53:44Z<p>Андрей Козлов: загружена новая версия «Файл:Planar edge biconnected 1.png»</p>
<hr />
<div></div>Андрей Козловhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%A4%D0%B0%D0%B9%D0%BB:Planar_edge_biconnected_1.png&diff=21144Файл:Planar edge biconnected 1.png2012-04-23T20:51:20Z<p>Андрей Козлов: загружена новая версия «Файл:Planar edge biconnected 1.png»</p>
<hr />
<div></div>Андрей Козловhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%A4%D0%B0%D0%B9%D0%BB:Planar_edge_biconnected_1.png&diff=21143Файл:Planar edge biconnected 1.png2012-04-23T20:50:12Z<p>Андрей Козлов: загружена новая версия «Файл:Planar edge biconnected 1.png»</p>
<hr />
<div></div>Андрей Козловhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%A4%D0%B0%D0%B9%D0%BB:Planar_edge_biconnected_4.png&diff=21138Файл:Planar edge biconnected 4.png2012-04-23T20:39:00Z<p>Андрей Козлов: загружена новая версия «Файл:Planar edge biconnected 4.png»</p>
<hr />
<div></div>Андрей Козловhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%A4%D0%B0%D0%B9%D0%BB:Planar_edge_biconnected_2.png&diff=21137Файл:Planar edge biconnected 2.png2012-04-23T20:36:32Z<p>Андрей Козлов: загружена новая версия «Файл:Planar edge biconnected 2.png»</p>
<hr />
<div></div>Андрей Козловhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%A4%D0%B0%D0%B9%D0%BB:Planar_edge_biconnected_3.png&diff=21135Файл:Planar edge biconnected 3.png2012-04-23T20:35:05Z<p>Андрей Козлов: загружена новая версия «Файл:Planar edge biconnected 3.png»</p>
<hr />
<div></div>Андрей Козловhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%A4%D0%B0%D0%B9%D0%BB:Colors.png&diff=21133Файл:Colors.png2012-04-23T20:17:04Z<p>Андрей Козлов: загружена новая версия «Файл:Colors.png»</p>
<hr />
<div></div>Андрей Козловhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%9E%D0%B1%D1%85%D0%BE%D0%B4_%D0%B2_%D0%B3%D0%BB%D1%83%D0%B1%D0%B8%D0%BD%D1%83,_%D1%86%D0%B2%D0%B5%D1%82%D0%B0_%D0%B2%D0%B5%D1%80%D1%88%D0%B8%D0%BD&diff=21120Обход в глубину, цвета вершин2012-04-23T19:53:08Z<p>Андрей Козлов: /* Дерево обхода в глубину */</p>
<hr />
<div>'''Обход в глубину''' (поиск в глубину, англ. '''Depth-First Search''', '''DFS''') — один из основных методов обхода [[Основные определения теории графов|графа]], часто используемый для [[Использование обхода в глубину для проверки связности|проверки связности]], поиска [[Использование обхода в глубину для поиска цикла в ориентированном графе|цикла]] и [[Использование обхода в глубину для поиска компонент сильной связности|компонент сильной связности]] и для [[Использование обхода в глубину для топологической сортировки|топологической сортировки]].<br />
<br />
== Алгоритм ==<br />
<br />
=== Общая идея ===<br />
Общая идея алгоритма состоит в следующем: для каждой ''не пройденной'' [[Основные определения теории графов|вершины]] необходимо найти все ''не пройденные'' [[Основные определения теории графов|смежные вершины]] и повторить поиск для них.<br />
<br />
=== Пошаговое представление ===<br />
#Выбираем любую вершину из еще ''не пройденных'', обозначим ее как <tex>u</tex>.<br />
#Запускаем процедуру <tex>dfs(u)</tex><br />
#*Помечаем вершину <tex>u</tex> как ''пройденную''<br />
#*Для каждой ''не пройденной'' смежной с <tex>u</tex> вершиной (назовем ее <tex>v</tex>) запускаем <tex>dfs(v)</tex><br />
#Повторяем шаги 1 и 2, пока все вершины не окажутся ''пройденными''.<br />
<br />
=== Реализация ===<br />
vector<bool> visited; //вектор для хранения информации о ''пройденных'' и ''не пройденных'' вершинах<br />
<br />
void dfs(int u) <br />
{<br />
visited[u] = true; //помечаем вершину как пройденную<br />
for (v таких, что (u, v) — ребро в G) //проходим по смежным с u вершинам<br />
if (!visited[v]) //проверяем, не находились ли мы ранее в выбранной вершине<br />
dfs(v);<br />
}<br />
<br />
int main()<br />
{<br />
... //задание графа G с количеством вершин n.<br />
visited.assign(n, false); //в начале все вершины в графе ''не пройденные''<br />
for (int i = 0; i < n; ++i) //проходим по всем вершинам графа...<br />
if (!visited[i]) //...не забыв проверить, были мы уже в очередной вершине или нет<br />
dfs(i);<br />
return 0;<br />
}<br />
<br />
=== Время работы ===<br />
Оценим время работы обхода в глубину. Процедура <tex>dfs</tex> вызывается от каждой вершины не более одного раза, а внутри процедуры рассматриваются все такие [[Основные определения теории графов|ребра]] <tex>\{e\ |\ begin(e) = u\}</tex>. Всего таких ребер для всех вершин в графе <tex>O(E)</tex>, следовательно, время работы алгоритма оценивается как <tex>O(V+E)</tex>.<br />
<br />
== Цвета вершин ==<br />
Зачастую, простой информации "были/не были в вершине" не хватает для конкретных целей.<br /> <br />
Поэтому в процессе алгоритма вершинам задают некоторые цвета:<br /><br />
:если вершина ''белая'', значит, мы в ней еще не были, вершина ''не пройдена'';<br /><br />
:''серая'' — вершина ''проходится'' в текущей процедуре <tex>dfs</tex>;<br /><br />
:''черная'' — вершина ''пройдена'', все итерации <tex>dfs</tex> от нее завершены.<br /><br />
<br />
Такие "метки" в основном используются при [[Использование обхода в глубину для поиска цикла в ориентированном графе|поиске цикла]].<br />
<br />
=== Реализация ===<br />
Отличие реализации с цветами от предыдущей лишь в массиве visited, который мы назовем теперь color.<br />
<br />
vector<color_t> color; //вектор для хранения информации о цвете вершин<br />
<br />
void dfs(int u) <br />
{<br />
color[u] = GRAY; //раскрашиваем вершину в ''серый'' цвет<br />
for (v таких, что (u, v) — ребро в G) //проходим по смежным с u вершинам<br />
if (color[v] == WHITE) //проверяем, не находились ли мы ранее в выбранной вершине, условие не требует изменений, <br />
dfs(v); //поскольку мы считаем вершину "не пройденной" только тогда, когда она ''белого'' цвета, т.е. когда color[v] == WHITE<br />
color[u] = BLACK; //раскрашиваем вершину в ''черный'' цвет<br />
}<br />
<br />
int main()<br />
{<br />
... //задание графа G с количеством вершин n.<br />
color.assign(n, WHITE); //в начале все вершины в графе ''не пройденные'', т.е. ''белые''.<br />
for (int i = 0; i < n; ++i) //проходим по всем вершинам графа...<br />
if (color[i] == WHITE) //...не забыв проверить, были мы уже в очередной вершине или нет<br />
dfs(i);<br />
return 0;<br />
}<br />
<br />
== Дерево обхода в глубину ==<br />
[[Image: Colors.png|thumb|250px|Типы ребер, определяемые деревом обхода:<br><br />
1) ребра дерева<br><br />
2) <font color=#3771c8>обратные</font> ребра<br><br />
3) <font color=#71c837>прямые</font> ребра<br><br />
4) <font color=#ff2a2a>перекрестные</font> ребра]]<br />
<br />
Рассмотрим подграф предшествования обхода в глубину <tex>G_p = (V, E_p)</tex>, где <tex>E_p = \{(p[u], u) : u \in V,\ p[u] \neq NIL\}</tex>, где в свою очередь <tex>p[u]</tex> — вершина, от которой был вызван <tex>dfs(u)\ </tex> (для вершин, от которых <tex>dfs</tex> был вызван нерекурсивно это значение соответственно равно <tex>NIL</tex>). Подграф предшествования поиска в глубину образует ''лес обхода в глубину'', который состоит из нескольких ''деревьев обхода в глубину''. С помощью полученного леса можно классифицировать ребра графа <tex>G</tex>:<br />
* ''Ребрами дерева'' назовем те ребра из <tex>G</tex>, которые вошли в <tex>G_p</tex>. <br />
* Ребра <tex>(u, v)</tex>, соединяющие вершину <tex>u</tex> с её предком <tex>v</tex> в дереве обхода в глубину назовем ''обратными ребрами'' (для неориентированного графа предок должен быть ''не родителем'', так как иначе ребро будет являться ребром дерева). <br />
* Ребра <tex>(u, v)</tex>, не являющиеся ребрами дерева и соединяющие вершину <tex>u</tex> с её потомком <tex>v</tex> в дереве обхода в глубину назовем ''прямыми ребрами'' (в неориентированном графе нет разницы между прямыми и обратными ребрами, поэтому все такие ребра считаются обратными). <br />
* Все остальные ребра назовем ''перекрестными ребрами'' — такие ребра могут соединять вершины одного и того же дерева обхода в глубину, когда ни одна из вершин не является предком другой, или соединять вершины в разных деревьях.<br />
Алгоритм <tex>dfs</tex> можно модифицировать так, что он будет классифицировать встречающиеся при работе ребра. Ключевая идея состоит в том, что каждое ребро <tex>(u, v)</tex> можно классифицировать при помощи цвета вершины <tex>v</tex> при первом его исследовании, а именно:<br />
* Белый цвет вершины <tex>v</tex> по определению <tex>dfs</tex> говорит о том, что это ''ребро дерева''.<br />
* Серый цвет в силу того, что серые вершины всегда образуют нисходящий путь в каком-либо из деревьев <tex>dfs</tex> и встреченная вершина <tex>v</tex> лежит на нем выше вершины <tex>u</tex>, определяет ''обратное ребро'' (для неориентированного графа необходимо проверить условие <tex>v \neq p[u]</tex>).<br />
* Черный цвет, соответственно, указывает на ''прямое'' или ''перекрестное ребро''.<br />
<br />
== Источники ==<br />
*[http://ru.wikipedia.org/wiki/Поиск_в_глубину Обход в глубину на ru.wikipedia.org]<br />
*[http://en.wikipedia.org/wiki/Depth-first_search Обход в глубину на en.wikipedia.org]<br />
*[http://www.e-maxx.ru/algo/dfs Обход в глубину. Реализации.]<br />
* Томас Кормен, Чарльз Лейзерсон, Рональд Ривест, Клиффорд Штайн. Алгоритмы: построение и анализ, второе издание. Пер. с англ. — Издательский дом "Вильямс", 2007. — 1296 с. — Глава 22. Элементарные алгоритмы для работы с графами.<br />
<br />
<br />
[[Категория: Алгоритмы и структуры данных]]<br />
[[Категория: Обход в глубину]]</div>Андрей Козловhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%A4%D0%B0%D0%B9%D0%BB:Bipartite_graph.png&diff=21115Файл:Bipartite graph.png2012-04-23T19:25:42Z<p>Андрей Козлов: загружена новая версия «Файл:Bipartite graph.png»</p>
<hr />
<div></div>Андрей Козловhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%A4%D0%B0%D0%B9%D0%BB:Redei_kamion_3.png&diff=21103Файл:Redei kamion 3.png2012-04-23T18:29:49Z<p>Андрей Козлов: загружена новая версия «Файл:Redei kamion 3.png»</p>
<hr />
<div></div>Андрей Козловhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%A4%D0%B0%D0%B9%D0%BB:Redei_kamion_4.png&diff=21097Файл:Redei kamion 4.png2012-04-23T18:20:45Z<p>Андрей Козлов: загружена новая версия «Файл:Redei kamion 4.png»</p>
<hr />
<div></div>Андрей Козловhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%A2%D0%B5%D0%BE%D1%80%D0%B5%D0%BC%D0%B0_%D0%A0%D0%B5%D0%B4%D0%B5%D0%B8-%D0%9A%D0%B0%D0%BC%D0%B8%D0%BE%D0%BD%D0%B0&diff=21095Теорема Редеи-Камиона2012-04-23T18:18:01Z<p>Андрей Козлов: </p>
<hr />
<div>{{Теорема<br />
|about=<br />
Редеи-Камиона (для пути)<br />
|statement=<br />
В любом [[Турниры|турнире]] есть [[Гамильтоновы_графы#.D0.9E.D1.81.D0.BD.D0.BE.D0.B2.D0.BD.D1.8B.D0.B5_.D0.BE.D0.BF.D1.80.D0.B5.D0.B4.D0.B5.D0.BB.D0.B5.D0.BD.D0.B8.D1.8F|гамильтонов путь]].<br />
|proof= <br />
Приведем доказательство по индукции по числу вершин в графе. Пусть <tex> n </tex> {{---}} количество вершин в графе.<br />
<br />
<u> ''База индукции:'' </u><br />
<br />
Очевидно, для <tex> n = 3 </tex> утверждение верно.<br />
<br />
<u> ''Индукционный переход:'' </u><br />
<br />
Пусть предположение верно для всех турниров с количеством вершин не более <tex> n </tex>. Рассмотрим турнир <tex> T </tex> с <tex> n + 1 </tex> вершинами.<br />
<br />
Пусть <tex> u </tex> – произвольная вершина турнира <tex> T </tex>. Тогда турнир <tex> T - u </tex> имеет <tex> n </tex> вершин, значит, в нем есть гамильтонов путь <tex> P: (v_1 \rightarrow v_2 \rightarrow \ldots \rightarrow v_n) </tex>.<br />
[[Файл: Redei_kamion_1.png|250px|thumb|center]]<br />
<br />
Одно из ребер <tex> (u, v_1) </tex> или <tex> (v_1, u) </tex> обязательно содержится в <tex> T </tex>.<br />
Если ребро <tex> (u, v_1) \in ET </tex>, то путь <tex> (u \rightarrow P) </tex> {{---}} гамильтонов.<br />
[[Файл: Redei_kamion_2.png|250px|thumb|center|<font color=#ff2a2a>Красным</font> цветом выделен искомый путь]]<br />
<br />
Пусть теперь ребро <tex> (u, v_1) \notin ET, v_i </tex> {{---}} первая вершина пути <tex> P </tex>, для которой ребро <tex> (u, v_i) \in T </tex>.<br />
Если такая вершина существует, то в <tex> T </tex> существует ребро <tex> (v_{i - 1}, u) </tex> и путь <tex> (v_1 \rightarrow \ldots \rightarrow v_{i - 1} \rightarrow u \rightarrow v_i \rightarrow \ldots v_n) </tex> – гамильтонов.<br />
[[Файл: Redei_kamion_3.png|250px|thumb|center|<font color=#ff2a2a>Красным</font> цветом выделен искомый путь]]<br />
<br />
Если такой вершины не существует, то путь <tex> (P \rightarrow u) </tex> {{---}} гамильтонов.<br />
[[Файл: Redei_kamion_4.png|250px|thumb|center|<font color=#ff2a2a>Красным</font> цветом выделен искомый путь]]<br />
<br />
Значит, в любом случае в турнире существует гамильтонов путь, q.e.d.<br />
}}<br />
<br />
{{Теорема<br />
|about=<br />
Редеи-Камиона (для цикла)<br />
|statement=<br />
В любом [[Отношение_связности,_компоненты_связности#.D0.A1.D0.B8.D0.BB.D1.8C.D0.BD.D0.B0.D1.8F_.D1.81.D0.B2.D1.8F.D0.B7.D0.BD.D0.BE.D1.81.D1.82.D1.8C|сильно связанном]] турнире есть [[Гамильтоновы_графы#.D0.9E.D1.81.D0.BD.D0.BE.D0.B2.D0.BD.D1.8B.D0.B5_.D0.BE.D0.BF.D1.80.D0.B5.D0.B4.D0.B5.D0.BB.D0.B5.D0.BD.D0.B8.D1.8F|гамильтонов цикл]].<br />
|proof= <br />
Приведем доказательство по индукции по числу вершин в цикле. Пусть <tex> n </tex> {{---}} количество вершин в графе.<br />
<br />
<u> ''База индукции:'' </u><br />
<br />
{{Утверждение<br />
|statement=<br />
Cильно связанный турнир <tex> T </tex> из <tex> n \geq 3 </tex> вершин содержит [[Основные_определения_теории_графов#.D0.9E.D1.80.D0.B8.D0.B5.D0.BD.D1.82.D0.B8.D1.80.D0.BE.D0.B2.D0.B0.D0.BD.D0.BD.D1.8B.D0.B5_.D0.B3.D1.80.D0.B0.D1.84.D1.8B|цикл]] длины <tex> 3 </tex>.<br />
|proof=<br />
Пусть <tex> u </tex> {{---}} произвольная вершина турнира <tex> T </tex>. Множество вершин <tex> VT - u </tex> распадается на <tex> 2 </tex> непересекающихся множества:<br />
* <tex> V_1 = \{ v_1 \in VT | (v_1, u) \in ET \} </tex>,<br />
* <tex> V_2 = \{ v_2 \in VT | (u, v_2) \in ET \} </tex>.<br />
[[Файл: Redei_kamion_5.png|350px|thumb|center]]<br />
<br />
<tex> T </tex> сильно связен, следовательно:<br />
# <tex> V_1 \neq \emptyset </tex>, иначе <tex> v </tex> {{---}} исток турнира<br />
# <tex> V_2 \neq \emptyset </tex>, иначе <tex> v </tex> {{---}} сток турнира<br />
# <tex> \exists e = (w_2, w_1) \in ET </tex>, иначе нет пути из <tex> V_2 </tex> в <tex> V_1 </tex>:<br />
#* <tex> w_1 \in V_1 </tex>,<br />
#* <tex> w_2 \in V_2 </tex>.<br />
[[Файл: Redei_kamion_6.png|350px|thumb|center|<font color=#ff2a2a>Красным</font> цветом выделен цикл длины <tex> 3 </tex>]]<br />
<br />
Цикл <tex> S_3: (u \rightarrow w_2 \rightarrow w_1 \rightarrow u) </tex> {{---}} искомый цикл длины <tex> 3 </tex>, q.e.d.<br />
}}<br />
<br />
<u> ''Индукционный переход:'' </u><br />
<br />
{{Утверждение<br />
|statement=<br />
Если сильно связанный турнир <tex> T </tex> из <tex> n \geq 3 </tex> вершин содержит цикл <tex> S_k </tex> длины <tex> k, (k < n)</tex>, то он содержит и цикл длины <tex> k + 1 </tex>.<br />
|proof=<br />
Пусть <tex> S_k = (v_1 \rightarrow v_2 \rightarrow \ldots \rightarrow v_k \rightarrow v_1) </tex>.<br />
<br />
Пусть <tex> v_0 : v_0 \notin S_k </tex> и верно, что <tex> \exists u, w \in S_k </tex>:<br />
* <tex> (v_0, u) \in ET </tex>,<br />
* <tex> (w, v_0) \in ET </tex>.<br />
<br />
Рассмотрим два случая:<br />
# существует такая вершина <tex> v_0 </tex>,<br />
# не существует такой вершины <tex> v_0 </tex>.<br />
Заметим, что при <tex> k = n - 1 </tex> такая вершина необходимо существует, так как иначе вершина, не входящая в цикл, будет являться либо стоком, либо истоком.<br />
<br />
<u> Первый случай: </u><br />
<br />
Перенумеруем вершины <tex> S_k </tex> так, чтобы ребро <tex> e = (v_1, v_0) \in ET </tex> для вершины <tex> v_1 \in S_k </tex>. Пусть <tex> v_i </tex> – первая вершина при обходе <tex> S_k </tex> из <tex> v_1 </tex>, для которой ребро <tex> f = (v_0, v_i) \in ET </tex>.<br />
[[Файл: Redei_kamion_7.png|250px|thumb|center]]<br />
<br />
Тогда ребро <tex> g = (v_{i - 1}, v_0) \in ET </tex>.<br />
[[Файл: Redei_kamion_8.png|250px|thumb|center|<font color=#ff2a2a>Красным</font> цветом выделен искомый цикл длины <tex> k + 1 </tex> ]]<br />
<br />
Тогда <tex> S_{k + 1} = (v_1 \rightarrow v_2 \rightarrow \ldots \rightarrow v_{i - 1} \rightarrow v_0 \rightarrow v_i \rightarrow \ldots \rightarrow v_k \rightarrow v_1) </tex> – искомый цикл длины <tex> k + 1 </tex>.<br />
<br />
<u> Второй случай: </u><br />
<br />
Пусть:<br />
* <tex> V_1 = \{ u \in VT | u \notin S_k, e = (u, v_i) \in ET, \forall i = \overline{1, n} \} </tex>,<br />
* <tex> V_2 = \{ u \in VT | u \notin S_k, f = (v_i, u) \in ET, \forall i = \overline{1, n} \} </tex>.<br />
Тогда <tex> V_1 \cap V_2 = \emptyset </tex>.<br />
[[Файл: Redei_kamion_9.png|350px|thumb|center]]<br />
<br />
Турнир сильно связен, следовательно:<br />
* <tex> V_1 \neq \emptyset </tex>, иначе <tex> T </tex> не будет сильно связным, так как тогда нет простых путей с началом в <tex> V_2 </tex> и концом в <tex> S_k </tex><br />
* <tex> V_2 \neq \emptyset </tex>, иначе <tex> T </tex> не будет сильно связным, так как тогда нет простых путей с началом в <tex> S_k </tex> и концом в <tex> V_1 </tex><br />
* <tex> \exists g = (w_2, w_1) \in ET </tex>, иначе <tex> T </tex> не будет сильно связным, так как тогда нет простых путей с началом в <tex> V_2 </tex> и концом в <tex> V_1 </tex>):<br />
** <tex> w_1 \in V_1 </tex>,<br />
** <tex> w_2 \in V_2 </tex>.<br />
[[Файл: Redei_kamion_10.png|350px|thumb|center|<font color=#ff2a2a>Красным</font> цветом выделен цикл длины <tex> k + 1 </tex>]]<br />
Тогда <tex> S_{k + 1} = (v_1 \rightarrow w_2 \rightarrow w_1 \rightarrow v_3 \rightarrow \ldots \rightarrow v_k \rightarrow v_1) </tex> – искомый цикл длины <tex> k + 1 </tex>.<br />
<br />
В любом случае утверждение верно, q.e.d.<br />
<br />
}}<br />
Таким образом, любой сильно связанный турнир <tex> T </tex> с <tex> n \geq 3 </tex> вершинами содержит цикл длины <tex> n </tex>, то есть гамильтонов цикл, q.e.d.<br />
}}<br />
<br />
{{Теорема<br />
|about=<br />
Следствие<br />
|statement=<br />
Турнир является сильно связанным тогда и только тогда, когда он имеет гамильтонов цикл.<br />
}}<br />
<br />
==См. также==<br />
* [[Гамильтоновы графы]]<br />
* [[Турниры]]<br />
<br />
== Литература ==<br />
* Асанов М., Баранский В., Расин В.: ''Дискретная математика: Графы, матроиды, алгоритмы''<br />
* Ф. Харари: ''Теория графов''<br />
<br />
[[Категория: Алгоритмы и структуры данных]]<br />
[[Категория: Обходы графов]]</div>Андрей Козловhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%A4%D0%B0%D0%B9%D0%BB:Redei_kamion_2.png&diff=21094Файл:Redei kamion 2.png2012-04-23T18:16:11Z<p>Андрей Козлов: загружена новая версия «Файл:Redei kamion 2.png»</p>
<hr />
<div></div>Андрей Козловhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%A4%D0%B0%D0%B9%D0%BB:Redei_kamion_1.png&diff=21093Файл:Redei kamion 1.png2012-04-23T18:15:04Z<p>Андрей Козлов: загружена новая версия «Файл:Redei kamion 1.png»</p>
<hr />
<div></div>Андрей Козловhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%A4%D0%B0%D0%B9%D0%BB:Redei_kamion_8.png&diff=21090Файл:Redei kamion 8.png2012-04-23T18:09:37Z<p>Андрей Козлов: загружена новая версия «Файл:Redei kamion 8.png»</p>
<hr />
<div></div>Андрей Козловhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%A4%D0%B0%D0%B9%D0%BB:Redei_kamion_7.png&diff=21089Файл:Redei kamion 7.png2012-04-23T18:08:35Z<p>Андрей Козлов: загружена новая версия «Файл:Redei kamion 7.png»</p>
<hr />
<div></div>Андрей Козловhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%A2%D0%B5%D0%BE%D1%80%D0%B5%D0%BC%D0%B0_%D0%A0%D0%B5%D0%B4%D0%B5%D0%B8-%D0%9A%D0%B0%D0%BC%D0%B8%D0%BE%D0%BD%D0%B0&diff=21081Теорема Редеи-Камиона2012-04-23T17:31:10Z<p>Андрей Козлов: </p>
<hr />
<div>{{Теорема<br />
|about=<br />
Редеи-Камиона (для пути)<br />
|statement=<br />
В любом [[Турниры|турнире]] есть [[Гамильтоновы_графы#.D0.9E.D1.81.D0.BD.D0.BE.D0.B2.D0.BD.D1.8B.D0.B5_.D0.BE.D0.BF.D1.80.D0.B5.D0.B4.D0.B5.D0.BB.D0.B5.D0.BD.D0.B8.D1.8F|гамильтонов путь]].<br />
|proof= <br />
Приведем доказательство по индукции по числу вершин в графе. Пусть <tex> n </tex> {{---}} количество вершин в графе.<br />
<br />
<u> ''База индукции:'' </u><br />
<br />
Очевидно, для <tex> n = 3 </tex> утверждение верно.<br />
<br />
<u> ''Индукционный переход:'' </u><br />
<br />
Пусть предположение верно для всех турниров с количеством вершин не более <tex> n </tex>. Рассмотрим турнир <tex> T </tex> с <tex> n + 1 </tex> вершинами.<br />
<br />
Пусть <tex> u </tex> – произвольная вершина турнира <tex> T </tex>. Тогда турнир <tex> T - u </tex> имеет <tex> n </tex> вершин, значит, в нем есть гамильтонов путь <tex> P: (v_1 \rightarrow v_2 \rightarrow \ldots \rightarrow v_n) </tex>.<br />
[[Файл: Redei_kamion_1.png|250px|thumb|center]]<br />
<br />
Одно из ребер <tex> (u, v_1) </tex> или <tex> (v_1, u) </tex> обязательно содержится в <tex> T </tex>.<br />
Если ребро <tex> (u, v_1) \in ET </tex>, то путь <tex> (u \rightarrow P) </tex> {{---}} гамильтонов.<br />
[[Файл: Redei_kamion_2.png|250px|thumb|center|<font color=#ED1C24>Красным</font> цветом выделен искомый путь]]<br />
<br />
Пусть теперь ребро <tex> (u, v_1) \notin ET, v_i </tex> {{---}} первая вершина пути <tex> P </tex>, для которой ребро <tex> (u, v_i) \in T </tex>.<br />
Если такая вершина существует, то в <tex> T </tex> существует ребро <tex> (v_{i - 1}, u) </tex> и путь <tex> (v_1 \rightarrow \ldots \rightarrow v_{i - 1} \rightarrow u \rightarrow v_i \rightarrow \ldots v_n) </tex> – гамильтонов.<br />
[[Файл: Redei_kamion_3.png|250px|thumb|center|<font color=#ED1C24>Красным</font> цветом выделен искомый путь]]<br />
<br />
Если такой вершины не существует, то путь <tex> (P \rightarrow u) </tex> {{---}} гамильтонов.<br />
[[Файл: Redei_kamion_4.png|250px|thumb|center|<font color=#ED1C24>Красным</font> цветом выделен искомый путь]]<br />
<br />
Значит, в любом случае в турнире существует гамильтонов путь, q.e.d.<br />
}}<br />
<br />
{{Теорема<br />
|about=<br />
Редеи-Камиона (для цикла)<br />
|statement=<br />
В любом [[Отношение_связности,_компоненты_связности#.D0.A1.D0.B8.D0.BB.D1.8C.D0.BD.D0.B0.D1.8F_.D1.81.D0.B2.D1.8F.D0.B7.D0.BD.D0.BE.D1.81.D1.82.D1.8C|сильно связанном]] турнире есть [[Гамильтоновы_графы#.D0.9E.D1.81.D0.BD.D0.BE.D0.B2.D0.BD.D1.8B.D0.B5_.D0.BE.D0.BF.D1.80.D0.B5.D0.B4.D0.B5.D0.BB.D0.B5.D0.BD.D0.B8.D1.8F|гамильтонов цикл]].<br />
|proof= <br />
Приведем доказательство по индукции по числу вершин в цикле. Пусть <tex> n </tex> {{---}} количество вершин в графе.<br />
<br />
<u> ''База индукции:'' </u><br />
<br />
{{Утверждение<br />
|statement=<br />
Cильно связанный турнир <tex> T </tex> из <tex> n \geq 3 </tex> вершин содержит [[Основные_определения_теории_графов#.D0.9E.D1.80.D0.B8.D0.B5.D0.BD.D1.82.D0.B8.D1.80.D0.BE.D0.B2.D0.B0.D0.BD.D0.BD.D1.8B.D0.B5_.D0.B3.D1.80.D0.B0.D1.84.D1.8B|цикл]] длины <tex> 3 </tex>.<br />
|proof=<br />
Пусть <tex> u </tex> {{---}} произвольная вершина турнира <tex> T </tex>. Множество вершин <tex> VT - u </tex> распадается на <tex> 2 </tex> непересекающихся множества:<br />
* <tex> V_1 = \{ v_1 \in VT | (v_1, u) \in ET \} </tex>,<br />
* <tex> V_2 = \{ v_2 \in VT | (u, v_2) \in ET \} </tex>.<br />
[[Файл: Redei_kamion_5.png|350px|thumb|center]]<br />
<br />
<tex> T </tex> сильно связен, следовательно:<br />
# <tex> V_1 \neq \emptyset </tex>, иначе <tex> v </tex> {{---}} исток турнира<br />
# <tex> V_2 \neq \emptyset </tex>, иначе <tex> v </tex> {{---}} сток турнира<br />
# <tex> \exists e = (w_2, w_1) \in ET </tex>, иначе нет пути из <tex> V_2 </tex> в <tex> V_1 </tex>:<br />
#* <tex> w_1 \in V_1 </tex>,<br />
#* <tex> w_2 \in V_2 </tex>.<br />
[[Файл: Redei_kamion_6.png|350px|thumb|center|<font color=#ED1C24>Красным</font> цветом выделен цикл длины <tex> 3 </tex>]]<br />
<br />
Цикл <tex> S_3: (u \rightarrow w_2 \rightarrow w_1 \rightarrow u) </tex> {{---}} искомый цикл длины <tex> 3 </tex>, q.e.d.<br />
}}<br />
<br />
<u> ''Индукционный переход:'' </u><br />
<br />
{{Утверждение<br />
|statement=<br />
Если сильно связанный турнир <tex> T </tex> из <tex> n \geq 3 </tex> вершин содержит цикл <tex> S_k </tex> длины <tex> k, (k < n)</tex>, то он содержит и цикл длины <tex> k + 1 </tex>.<br />
|proof=<br />
Пусть <tex> S_k = (v_1 \rightarrow v_2 \rightarrow \ldots \rightarrow v_k \rightarrow v_1) </tex>.<br />
<br />
Пусть <tex> v_0 : v_0 \notin S_k </tex> и верно, что <tex> \exists u, w \in S_k </tex>:<br />
* <tex> (v_0, u) \in ET </tex>,<br />
* <tex> (w, v_0) \in ET </tex>.<br />
<br />
Рассмотрим два случая:<br />
# существует такая вершина <tex> v_0 </tex>,<br />
# не существует такой вершины <tex> v_0 </tex>.<br />
Заметим, что при <tex> k = n - 1 </tex> такая вершина необходимо существует, так как иначе вершина, не входящая в цикл, будет являться либо стоком, либо истоком.<br />
<br />
<u> Первый случай: </u><br />
<br />
Перенумеруем вершины <tex> S_k </tex> так, чтобы ребро <tex> e = (v_1, v_0) \in ET </tex> для вершины <tex> v_1 \in S_k </tex>. Пусть <tex> v_i </tex> – первая вершина при обходе <tex> S_k </tex> из <tex> v_1 </tex>, для которой ребро <tex> f = (v_0, v_i) \in ET </tex>.<br />
[[Файл: Redei_kamion_7.png|250px|thumb|center]]<br />
<br />
Тогда ребро <tex> g = (v_{i - 1}, v_0) \in ET </tex>.<br />
[[Файл: Redei_kamion_8.png|250px|thumb|center|<font color=#ED1C24>Красным</font> цветом выделен искомый цикл длины <tex> k + 1 </tex> ]]<br />
<br />
Тогда <tex> S_{k + 1} = (v_1 \rightarrow v_2 \rightarrow \ldots \rightarrow v_{i - 1} \rightarrow v_0 \rightarrow v_i \rightarrow \ldots \rightarrow v_k \rightarrow v_1) </tex> – искомый цикл длины <tex> k + 1 </tex>.<br />
<br />
<u> Второй случай: </u><br />
<br />
Пусть:<br />
* <tex> V_1 = \{ u \in VT | u \notin S_k, e = (u, v_i) \in ET, \forall i = \overline{1, n} \} </tex>,<br />
* <tex> V_2 = \{ u \in VT | u \notin S_k, f = (v_i, u) \in ET, \forall i = \overline{1, n} \} </tex>.<br />
Тогда <tex> V_1 \cap V_2 = \emptyset </tex>.<br />
[[Файл: Redei_kamion_9.png|350px|thumb|center]]<br />
<br />
Турнир сильно связен, следовательно:<br />
* <tex> V_1 \neq \emptyset </tex>, иначе <tex> T </tex> не будет сильно связным, так как тогда нет простых путей с началом в <tex> V_2 </tex> и концом в <tex> S_k </tex><br />
* <tex> V_2 \neq \emptyset </tex>, иначе <tex> T </tex> не будет сильно связным, так как тогда нет простых путей с началом в <tex> S_k </tex> и концом в <tex> V_1 </tex><br />
* <tex> \exists g = (w_2, w_1) \in ET </tex>, иначе <tex> T </tex> не будет сильно связным, так как тогда нет простых путей с началом в <tex> V_2 </tex> и концом в <tex> V_1 </tex>):<br />
** <tex> w_1 \in V_1 </tex>,<br />
** <tex> w_2 \in V_2 </tex>.<br />
[[Файл: Redei_kamion_10.png|350px|thumb|center|<font color=#ED1C24>Красным</font> цветом выделен цикл длины <tex> k + 1 </tex>]]<br />
Тогда <tex> S_{k + 1} = (v_1 \rightarrow w_2 \rightarrow w_1 \rightarrow v_3 \rightarrow \ldots \rightarrow v_k \rightarrow v_1) </tex> – искомый цикл длины <tex> k + 1 </tex>.<br />
<br />
В любом случае утверждение верно, q.e.d.<br />
<br />
}}<br />
Таким образом, любой сильно связанный турнир <tex> T </tex> с <tex> n \geq 3 </tex> вершинами содержит цикл длины <tex> n </tex>, то есть гамильтонов цикл, q.e.d.<br />
}}<br />
<br />
{{Теорема<br />
|about=<br />
Следствие<br />
|statement=<br />
Турнир является сильно связанным тогда и только тогда, когда он имеет гамильтонов цикл.<br />
}}<br />
<br />
==См. также==<br />
* [[Гамильтоновы графы]]<br />
* [[Турниры]]<br />
<br />
== Литература ==<br />
* Асанов М., Баранский В., Расин В.: ''Дискретная математика: Графы, матроиды, алгоритмы''<br />
* Ф. Харари: ''Теория графов''<br />
<br />
[[Категория: Алгоритмы и структуры данных]]<br />
[[Категория: Обходы графов]]</div>Андрей Козловhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%A4%D0%B0%D0%B9%D0%BB:Redei_kamion_10.png&diff=21080Файл:Redei kamion 10.png2012-04-23T17:27:19Z<p>Андрей Козлов: загружена новая версия «Файл:Redei kamion 10.png»</p>
<hr />
<div></div>Андрей Козловhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%A4%D0%B0%D0%B9%D0%BB:Redei_kamion_9.png&diff=21079Файл:Redei kamion 9.png2012-04-23T17:24:16Z<p>Андрей Козлов: загружена новая версия «Файл:Redei kamion 9.png»</p>
<hr />
<div></div>Андрей Козловhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%A4%D0%B0%D0%B9%D0%BB:Redei_kamion_6.png&diff=21078Файл:Redei kamion 6.png2012-04-23T17:22:58Z<p>Андрей Козлов: загружена новая версия «Файл:Redei kamion 6.png»</p>
<hr />
<div></div>Андрей Козловhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%A4%D0%B0%D0%B9%D0%BB:Redei_kamion_5.png&diff=21077Файл:Redei kamion 5.png2012-04-23T17:20:39Z<p>Андрей Козлов: загружена новая версия «Файл:Redei kamion 5.png»</p>
<hr />
<div></div>Андрей Козловhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%A2%D0%B5%D0%BE%D1%80%D0%B5%D0%BC%D0%B0_%D0%A0%D0%B5%D0%B4%D0%B5%D0%B8-%D0%9A%D0%B0%D0%BC%D0%B8%D0%BE%D0%BD%D0%B0&diff=21076Теорема Редеи-Камиона2012-04-23T17:19:43Z<p>Андрей Козлов: </p>
<hr />
<div>{{Теорема<br />
|about=<br />
Редеи-Камиона (для пути)<br />
|statement=<br />
В любом [[Турниры|турнире]] есть [[Гамильтоновы_графы#.D0.9E.D1.81.D0.BD.D0.BE.D0.B2.D0.BD.D1.8B.D0.B5_.D0.BE.D0.BF.D1.80.D0.B5.D0.B4.D0.B5.D0.BB.D0.B5.D0.BD.D0.B8.D1.8F|гамильтонов путь]].<br />
|proof= <br />
Приведем доказательство по индукции по числу вершин в графе. Пусть <tex> n </tex> {{---}} количество вершин в графе.<br />
<br />
<u> ''База индукции:'' </u><br />
<br />
Очевидно, для <tex> n = 3 </tex> утверждение верно.<br />
<br />
<u> ''Индукционный переход:'' </u><br />
<br />
Пусть предположение верно для всех турниров с количеством вершин не более <tex> n </tex>. Рассмотрим турнир <tex> T </tex> с <tex> n + 1 </tex> вершинами.<br />
<br />
Пусть <tex> u </tex> – произвольная вершина турнира <tex> T </tex>. Тогда турнир <tex> T - u </tex> имеет <tex> n </tex> вершин, значит, в нем есть гамильтонов путь <tex> P: (v_1 \rightarrow v_2 \rightarrow \ldots \rightarrow v_n) </tex>.<br />
[[Файл: Redei_kamion_1.png|250px|thumb|center]]<br />
<br />
Одно из ребер <tex> (u, v_1) </tex> или <tex> (v_1, u) </tex> обязательно содержится в <tex> T </tex>.<br />
Если ребро <tex> (u, v_1) \in ET </tex>, то путь <tex> (u \rightarrow P) </tex> {{---}} гамильтонов.<br />
[[Файл: Redei_kamion_2.png|250px|thumb|center|<font color=#ED1C24>Красным</font> цветом выделен искомый путь]]<br />
<br />
Пусть теперь ребро <tex> (u, v_1) \notin ET, v_i </tex> {{---}} первая вершина пути <tex> P </tex>, для которой ребро <tex> (u, v_i) \in T </tex>.<br />
Если такая вершина существует, то в <tex> T </tex> существует ребро <tex> (v_{i - 1}, u) </tex> и путь <tex> (v_1 \rightarrow \ldots \rightarrow v_{i - 1} \rightarrow u \rightarrow v_i \rightarrow \ldots v_n) </tex> – гамильтонов.<br />
[[Файл: Redei_kamion_3.png|250px|thumb|center|<font color=#ED1C24>Красным</font> цветом выделен искомый путь]]<br />
<br />
Если такой вершины не существует, то путь <tex> (P \rightarrow u) </tex> {{---}} гамильтонов.<br />
[[Файл: Redei_kamion_4.png|250px|thumb|center|<font color=#ED1C24>Красным</font> цветом выделен искомый путь]]<br />
<br />
Значит, в любом случае в турнире существует гамильтонов путь, q.e.d.<br />
}}<br />
<br />
{{Теорема<br />
|about=<br />
Редеи-Камиона (для цикла)<br />
|statement=<br />
В любом [[Отношение_связности,_компоненты_связности#.D0.A1.D0.B8.D0.BB.D1.8C.D0.BD.D0.B0.D1.8F_.D1.81.D0.B2.D1.8F.D0.B7.D0.BD.D0.BE.D1.81.D1.82.D1.8C|сильно связанном]] турнире есть [[Гамильтоновы_графы#.D0.9E.D1.81.D0.BD.D0.BE.D0.B2.D0.BD.D1.8B.D0.B5_.D0.BE.D0.BF.D1.80.D0.B5.D0.B4.D0.B5.D0.BB.D0.B5.D0.BD.D0.B8.D1.8F|гамильтонов цикл]].<br />
|proof= <br />
Приведем доказательство по индукции по числу вершин в цикле. Пусть <tex> n </tex> {{---}} количество вершин в графе.<br />
<br />
<u> ''База индукции:'' </u><br />
<br />
{{Утверждение<br />
|statement=<br />
Cильно связанный турнир <tex> T </tex> из <tex> n \geq 3 </tex> вершин содержит [[Основные_определения_теории_графов#.D0.9E.D1.80.D0.B8.D0.B5.D0.BD.D1.82.D0.B8.D1.80.D0.BE.D0.B2.D0.B0.D0.BD.D0.BD.D1.8B.D0.B5_.D0.B3.D1.80.D0.B0.D1.84.D1.8B|цикл]] длины <tex> 3 </tex>.<br />
|proof=<br />
Пусть <tex> u </tex> {{---}} произвольная вершина турнира <tex> T </tex>. Множество вершин <tex> VT - u </tex> распадается на <tex> 2 </tex> непересекающихся множества:<br />
* <tex> V_1 = \{ v_1 \in VT | (v_1, u) \in ET \} </tex>,<br />
* <tex> V_2 = \{ v_2 \in VT | (u, v_2) \in ET \} </tex>.<br />
[[Файл: Redei_kamion_5.png|250px|thumb|center]]<br />
<br />
<tex> T </tex> сильно связен, следовательно:<br />
# <tex> V_1 \neq \emptyset </tex>, иначе <tex> v </tex> {{---}} исток турнира<br />
# <tex> V_2 \neq \emptyset </tex>, иначе <tex> v </tex> {{---}} сток турнира<br />
# <tex> \exists e = (w_2, w_1) \in ET </tex>, иначе нет пути из <tex> V_2 </tex> в <tex> V_1 </tex>:<br />
#* <tex> w_1 \in V_1 </tex>,<br />
#* <tex> w_2 \in V_2 </tex>.<br />
[[Файл: Redei_kamion_6.png|250px|thumb|center|<font color=#ED1C24>Красным</font> цветом выделен цикл длины <tex> 3 </tex>]]<br />
<br />
Цикл <tex> S_3: (u \rightarrow w_2 \rightarrow w_1 \rightarrow u) </tex> {{---}} искомый цикл длины <tex> 3 </tex>, q.e.d.<br />
}}<br />
<br />
<u> ''Индукционный переход:'' </u><br />
<br />
{{Утверждение<br />
|statement=<br />
Если сильно связанный турнир <tex> T </tex> из <tex> n \geq 3 </tex> вершин содержит цикл <tex> S_k </tex> длины <tex> k, (k < n)</tex>, то он содержит и цикл длины <tex> k + 1 </tex>.<br />
|proof=<br />
Пусть <tex> S_k = (v_1 \rightarrow v_2 \rightarrow \ldots \rightarrow v_k \rightarrow v_1) </tex>.<br />
<br />
Пусть <tex> v_0 : v_0 \notin S_k </tex> и верно, что <tex> \exists u, w \in S_k </tex>:<br />
* <tex> (v_0, u) \in ET </tex>,<br />
* <tex> (w, v_0) \in ET </tex>.<br />
<br />
Рассмотрим два случая:<br />
# существует такая вершина <tex> v_0 </tex>,<br />
# не существует такой вершины <tex> v_0 </tex>.<br />
Заметим, что при <tex> k = n - 1 </tex> такая вершина необходимо существует, так как иначе вершина, не входящая в цикл, будет являться либо стоком, либо истоком.<br />
<br />
<u> Первый случай: </u><br />
<br />
Перенумеруем вершины <tex> S_k </tex> так, чтобы ребро <tex> e = (v_1, v_0) \in ET </tex> для вершины <tex> v_1 \in S_k </tex>. Пусть <tex> v_i </tex> – первая вершина при обходе <tex> S_k </tex> из <tex> v_1 </tex>, для которой ребро <tex> f = (v_0, v_i) \in ET </tex>.<br />
[[Файл: Redei_kamion_7.png|250px|thumb|center]]<br />
<br />
Тогда ребро <tex> g = (v_{i - 1}, v_0) \in ET </tex>.<br />
[[Файл: Redei_kamion_8.png|250px|thumb|center|<font color=#ED1C24>Красным</font> цветом выделен искомый цикл длины <tex> k + 1 </tex> ]]<br />
<br />
Тогда <tex> S_{k + 1} = (v_1 \rightarrow v_2 \rightarrow \ldots \rightarrow v_{i - 1} \rightarrow v_0 \rightarrow v_i \rightarrow \ldots \rightarrow v_k \rightarrow v_1) </tex> – искомый цикл длины <tex> k + 1 </tex>.<br />
<br />
<u> Второй случай: </u><br />
<br />
Пусть:<br />
* <tex> V_1 = \{ u \in VT | u \notin S_k, e = (u, v_i) \in ET, \forall i = \overline{1, n} \} </tex>,<br />
* <tex> V_2 = \{ u \in VT | u \notin S_k, f = (v_i, u) \in ET, \forall i = \overline{1, n} \} </tex>.<br />
Тогда <tex> V_1 \cap V_2 = \emptyset </tex>.<br />
[[Файл: Redei_kamion_9.png|350px|thumb|center]]<br />
<br />
Турнир сильно связен, следовательно:<br />
* <tex> V_1 \neq \emptyset </tex>, иначе <tex> T </tex> не будет сильно связным, так как тогда нет простых путей с началом в <tex> V_2 </tex> и концом в <tex> S_k </tex><br />
* <tex> V_2 \neq \emptyset </tex>, иначе <tex> T </tex> не будет сильно связным, так как тогда нет простых путей с началом в <tex> S_k </tex> и концом в <tex> V_1 </tex><br />
* <tex> \exists g = (w_2, w_1) \in ET </tex>, иначе <tex> T </tex> не будет сильно связным, так как тогда нет простых путей с началом в <tex> V_2 </tex> и концом в <tex> V_1 </tex>):<br />
** <tex> w_1 \in V_1 </tex>,<br />
** <tex> w_2 \in V_2 </tex>.<br />
[[Файл: Redei_kamion_10.png|350px|thumb|center|<font color=#ED1C24>Красным</font> цветом выделен цикл длины <tex> k + 1 </tex>]]<br />
Тогда <tex> S_{k + 1} = (v_1 \rightarrow w_2 \rightarrow w_1 \rightarrow v_3 \rightarrow \ldots \rightarrow v_k \rightarrow v_1) </tex> – искомый цикл длины <tex> k + 1 </tex>.<br />
<br />
В любом случае утверждение верно, q.e.d.<br />
<br />
}}<br />
Таким образом, любой сильно связанный турнир <tex> T </tex> с <tex> n \geq 3 </tex> вершинами содержит цикл длины <tex> n </tex>, то есть гамильтонов цикл, q.e.d.<br />
}}<br />
<br />
{{Теорема<br />
|about=<br />
Следствие<br />
|statement=<br />
Турнир является сильно связанным тогда и только тогда, когда он имеет гамильтонов цикл.<br />
}}<br />
<br />
==См. также==<br />
* [[Гамильтоновы графы]]<br />
* [[Турниры]]<br />
<br />
== Литература ==<br />
* Асанов М., Баранский В., Расин В.: ''Дискретная математика: Графы, матроиды, алгоритмы''<br />
* Ф. Харари: ''Теория графов''<br />
<br />
[[Категория: Алгоритмы и структуры данных]]<br />
[[Категория: Обходы графов]]</div>Андрей Козловhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%A4%D0%B0%D0%B9%D0%BB:Hvatal_4.png&diff=21058Файл:Hvatal 4.png2012-04-23T16:19:17Z<p>Андрей Козлов: загружена новая версия «Файл:Hvatal 4.png»</p>
<hr />
<div></div>Андрей Козловhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%A4%D0%B0%D0%B9%D0%BB:Hvatal_3.png&diff=21057Файл:Hvatal 3.png2012-04-23T16:17:51Z<p>Андрей Козлов: загружена новая версия «Файл:Hvatal 3.png»</p>
<hr />
<div></div>Андрей Козлов