Изменения

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

Турниры

290 байт добавлено, 20:51, 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|теореме]], это означает, что она транзитивна.
}}
Таким образом, даже если турнир не является транзитивным, сильно связанные компоненты турнира могут быть полностью [[Отношение порядка|вполне упорядочены]]. В самом деле, по [[#theorem1|теореме]], в турнире существует гамильтонов путь, значит вершины могут быть упорядочены по своим позициям в этом пути.
===Сильно связные турниры===
64
правки

Навигация