Изменения

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

Турниры

722 байта добавлено, 20:16, 8 января 2017
Конденсация
===Конденсация===
{{Утверждение|statement = Конденсация любого турнира является транзитивным турниром. |proof = Рассмотрим <tex>2</tex> компоненты сильной связности <tex>U, V</tex>, найдутся <tex>u \in U, v \in V: (u, v) \in E</tex>, либо <tex>(v, u) \in E </tex>, значит в конденсации есть либо ребро <tex>(U,V)</tex>, либо <tex>(V,U)</tex>. Т.к. мы рассмотрели произвольную пару вершин конденсации турнира, она является турниром. Конденсация любого орграфа ациклична, а по доказанной [[theorem1|теореме]], это означает, что она транзитивна. }}Таким образом, даже если турнир не является транзитивным, сильно связанные компоненты турнира могут быть полностью упорядочены. 
===Сильно связные турниры===
{{Определение|definition = Турнир называется [[Отношение связности, компоненты связности#sc_def |сильно связным]], если из любой вершины существуют пути до всех других.}}
64
правки

Навигация