Завдання до лабораторної роботи

Сума елементів будь-якого рядка та стовпця дорівнює 0.

Число кістяків у зв'язному графі

порядку,дорівнює алгебраїчному доповненню будь-якого елемента матриці Кірхгофа.

У зв'язковому позначеному графі всі алгебраїчні доповнення матриці Кірхгофа рівні між собою і визначають загальну кількість позначених кістяків цього графа.

При

 кількість вершин) число кістяків повного

графа

рівно.

Теорема А. Келі(1897 р.)

Число помічених дерев порядку

дорівнює.

Алгоритми пошуку кістяків найкоротших маршрутів

Є граф, заданий матрицею терезів, тобто. існує

,, де- кількість вершин графа,- вага ребра, якщо воно існує. Потрібно знайти кістяк з мінімальною сумарною вагою ребер.

1. Упорядковуємо ребра графа

у порядку невтрати їх ваг.

2. Будуємо порожній граф

, де- кількість вершин вихідного графа

3. На кожному кроці до сформованого поточного графа, додається ребро зі списку ребер вихідного графа з мінімальною вагою. Ребро, що додається, не повинно призводити до утворення циклу.

4. Алгоритм закінчує роботу, якщо кількість ребер у графі, що формується, стане рівною

.

Приклад:алгоритм Фарбала

Список ребер

Остів найкоротших маршрутів:

Загальна сумарна вага

= 7.

---