СМРЗДП / Максимальне паропоєднання. Мін верш покр.МОД

Доведення (від супротивного). Якщо в G є хоча б один цикл, то не порушуючи звя’зності можна видалити одне з ребер цього циклу: шлях із будь – якої вершини в будь – яку можна при необхідності організувати по частині циклу, що залишилась. Це означає, що в G більше ніж ребер: видалення з нього одного ребра не порушує зв’язності. Отже, G не є основним деревом.

Теорема 3. В Основному дереві G звязного графа існує єдиний шлях із кожної вершини в іншу.

Доведення. (від супротивного). Якщо б з деякої вершини існувало два різні шляхи в , то існував би цикл , а це суперечить теоремі 2.

Можна довести і обернені теореми і встановити тим самим еквівалентність наступних тверджень:

• основне дерево – це граф з ;

• основне дерево – це зв’язний граф без циклів;

• основне дерево – це зв’язний граф в якому існує єдиний шлях з кожної вершини в будь – яку іншу.

Дивлячись на попередній малюнок, можна побачити, що в основних деревах дійсно немає циклів, і з будь – якої вершини можна можна перейти в будь – яку іншу по єдиному циклу.

Зазвичай, ставиться задача про знаходження основного дерева мінімальної ваги (МОД – мінімальне основне дерево). Така задача виникає, ng, при проектуванні ліній електропередач: для прокладання ліній вибирають участки з мінімальною вартістю робіт що забезпечують зв’язність сітки.

Для знаходження МОД застосуємо скупий алгоритм.