Изменения

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

Теорема Гуйя-Ури

435 байт добавлено, 11:24, 2 января 2016
Нет описания правки
= Теорема Гуйя-Ури =
 
{{Определение
|definition=
Ориентированный сильно связный граф называется '''орсвязаными'''.}}
 
== Лемма о длине цикла в ориентированном графе ==
{{Лемма
Так как <tex>P</tex> {{---}} самый длинный путь в <tex>G</tex>, ни одна вершина которого не принадлежит <tex>C</tex>, каждая вершина, ребро из которой приходит в <tex>v_0</tex>, лежит либо на <tex>P</tex>, либо на <tex>C</tex>. Так как <tex>deg^{in}(v_0) \geqslant n/2</tex>, то <tex>a + l \geqslant n/2</tex>, следовательно <tex>deg^{out}(v_l) \leqslant (n - 1) - (a + l) \leqslant (n - 1) - n/2 = n/2 - 1</tex>. Получаем противоречие с условием. Таким образом, предположение неверно, а значит, теорема доказана.
}}
 
== См. также ==
* [[Теорема Дирака]]
 
== Источники информации ==
* Gary Chartrand, Linda Lesniak, Ping Zhang (2010). ''Graphs & Digraphs, Fifth Edition'', chapter 4. ISBN 9781439895184.
* Д. В. Карпов. ''Теория графов''.
 
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Обходы графов]]
[[Категория: Гамильтоновы графы]]
577
правок

Навигация