Изменения

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

Критерий Тарьяна минимальности остовного дерева

3 байта добавлено, 20:40, 15 января 2011

фикс

Переход:

Строим дерево <tex>T'</tex> по лемме о безопасном ребре. Рассмотрим минимальное ребро <tex>uv \in T, uv \notin T'</tex>.

Рассмотрим разрез <tex>(U,V): u \in U, v \in V</tex>.

143

правки

Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Служебная:Сравнение_версий/6851»