Изменения

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

53 байта добавлено, 22:51, 1 декабря 2010

м

фикс

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

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

База:

пустое дерево. Строим дерево <tex>T'</tex> по лемме о безопасном ребре.

143

правки