Розглянутий приклад дозволяє відзначити наступні дві особливості:
1 У списку s (G) вершини можуть повторюватися.
2. При відновленні дерева останнє ребро з'єднує вершину yp-2 і залишилася в списку 1, 2, ..., p вершину не дорівнює yp-2.
Отже, існує взаємно однозначна відповідність між безліччю помічених дерев з p вершинами і безліччю послідовностей вершин s (G). Число таких послідовностей одно, очевидно, pp-2, що й треба було довести.
Відзначимо, що серед pp-2 помічених дерев з p вершинами можуть бути і ізоморфні.
Визначення 3. Подграф G1 (X1, E1) неорієнтованого графа G (X, E) називається каркасом, або остовне деревом графа G, якщо G1 - дерево і X = X1.
Теорема 4. Граф G (X, E) тоді і тільки тоді має каркасом, коли він зв'язний.
Доведення. Необхідність цього очевидна. Доведемо достатність. Нехай G (X, E) - зв'язний граф. З'ясуємо, чи є в графі G таке ребро, видалення якого не порушує зв'язності графа G. Якщо таких ребер немає, то граф є дерево відповідно до теореми 1. Якщо ж таке ребро, наприклад e, існує, то викинемо його і прийдемо до графу G1 (X, E \). Потім зазначену процедуру проробляємо з графом G1 і т.д. Через кінцеве число кроків буде побудований, очевидно, каркас графа G. Теорема доведена.
Доказ теореми дає алгоритм побудови деякого каркаса в зв'язковому графі. Однак зв'язний граф може мати кілька каркасів, тому природно поставити задачу вибору каркаса, який задовольняє додатковим умовам.
Визначення 4. Графом з навантаженими ребрами (навантаженим графом) називається неорієнтовані граф G (X, E), кожному ребру eÎE якого поставлено у відповідність число m (e) ³ 0, зване вагою або довжиною ребра e.
Аналогічно можна визначити навантажений орграф.
Поставимо задачу знаходження такого каркаса G1 (X, E1) в навантаженому графі G (X, E), для якого сума
мінімальна. Каркас з такою властивістю називається мінімальним каркасом. Відповідно до теореми 4 кожен навантажений зв'язний граф має мінімальну каркасом. Це завдання виникає при проектуванні ліній зв'язку та електропередач, доріг, трубопроводів і т.п. коли потрібно з'єднати системою каналів зв'язку задані вузли так, щоб будь-які два вузла були пов'язані (можливо, через інші вузли), а загальна довжина каналів зв'язку була мінімальною; при цьому вузли можна вважати вершинами навантаженого графа, ваг ребер якого відповідає довжина можливого каналу зв'язку між відповідними вузлами. Тоді шукана мережу каналів буде мінімальним каркасом цього графа.
Алгоритм побудови мінімального каркасу
Нехай G (X, E) - зв'язний навантажений граф з p вершинами.
Крок 1. В якості першого ребра шуканого мінімального каркасу вибираємо ребро e1 з найменшою вагою m (e1). Якщо таких ребер кілька, то беремо будь-який з них.
Крок 2. В якості другого ребра беремо ребро e2 з безлічі E \, має найменшу вагу m (e2), і таке, що безліч не містить простих циклів. Якщо таких ребер кілька, то беремо будь-який з них.
Крок 3. У якості третьої ребра вибираємо таке ребро e3 з безлічі E \, яке має найменшу вагу m (e2) і для якого безліч не містить простих циклів. Якщо таких ребер кілька, беремо будь-який з них.
Зазначений процес повторюється і через деякий число k кроків дає безліч E =, до якого не можна додати ребро без появи циклу. Подграф G1 (X, E1) і є мінімальним каркасом графа G (X, E).
обгрунтування алгоритму
В силу властивості 6 з теореми 1 побудований підграф G1 (X, E1) є деревом, тому k = p -1. Доказ мінімальності каркаса G1 (X, E1) розіб'ємо на два етапи. Нехай спочатку G (X, E) - повний граф, у якого ваги всіх ребер різні, і нехай G2 (X, E2) - мінімальний каркас графа G. Якщо E2 ¹E1, то розглянемо el - перше з ребер безлічі E1, що не належить E2 . В графі
в силу властивості 6 теореми 1 існує єдиний простий цикл m. Цикл m містить ребро e0ÏE1. Граф G3 (X, E3), де
, не містить циклів і має n - 1 ребро, тому він є деревом. Безліч міститься в E2 і тому не містить циклів. Тоді в силу розглянутого вище алгоритму m (e0)> m (el). Звідси випливає, що сумарна вага дерева G3 (X, E3) менше ваги дерева G2 (X, E2). Це суперечить мінімальності каркаса G2, тому E2 = E1 і G1 (X, E1) - єдиний мінімальний каркас графа G.
Нехай тепер G (X, E) - довільний навантажений зв'язний граф. Якщо m (e1) = m (e2), то зробимо заміну
m (e1) ®m '(e1) = m (e1) + e,
m (e2) ®m '(e2) = m (e2) + 2 e,
взявши таке e, щоб збереглися співвідношення ваг m (e1) і m (e2) з іншими вагами. Зробимо граф G повним, додавши такі ребра di, що
. В отриманому графі єдиним мінімальним каркасом буде каркас, отриманий за допомогою розглянутого алгоритму. Легко бачити, що цей каркас буде мінімальним і в вихідному графі G (X, E).
На рис.4 зображені навантажений граф G і його мінімальний каркас G1.
