Изменения

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

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

Нет изменений в размере, 11:28, 24 сентября 2011

Нет описания правки

Теперь докажем, что дерево, удовлетворяющее условию, минимально:

Обозначим дерево <tex>T</tex> и покажем, что его можно построить алгоритмом ~~Крускала~~Краскала.

Индукция по количеству ребер в дереве:

322

правки

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