сті максимальне рішення. Для доказу нам знадобиться дуже просте твердження:
Якщо до дерева додати ребро, то в дереві з'явиться цикл, що містить це ребро.
Дійсно, нехай додано ребро (u, v) - "додано" означає, що ребро - нове, що раніше його в дереві не було. Оскільки дерево є пов'язаною графом, то існує ланцюг C (u, ..., v) з декількох ребер, що з'єднує вершини u і v. Додавання ребра (u, v) замикає ланцюг, перетворюючи її в цикл.
Теорема . Алгоритм Прима-Краскала отримує максимальне остовне дерево .
Доказ . Результатом роботи алгоритму є набір з n-1 ребер. Вони не утворюють циклу, бо на кожному з n-1 кроків з'єднувалися вершини різного кольору, тобто раніше не пов'язані. Цей граф зв'язний, тому що після проведення 1-го ребра залишилося n-1 різних кольорів, ..., після проведення (n-1) - го ребра залишився один колір, тобто одна компонента зв'язності. Отже, отриманий набір ребер утворює зв'язний граф без циклів, що містить n-1 ребер і n вершин. Отже, граф є остовне дерево. Залишилося довести, що воно має мінімальну довжину. Нехай {,, ...,} ребра остовного дерева в тому порядку як їх вибирав алгоритм, тобто ≥. Припустимо для простоти докази, що всі ребра мережі мають різну довжину, тобто
>> ...> (1)
Якщо отримане дерево не максимально, то існує інше дерево, заданий набором з n-1 ребер {,, ...,}, таке що сума довжин більше суми довжин . З точністю до позначень
>> ...> (2)
Можливо =, = і т.д., але оскільки дерева різні, то в послідовностях (1) і (2) знайдеться місце, де ребра відрізняються. Нехай саме ліве таке місце - k, так, що В№. Оскільки вибиралося по алгоритму найбільшим з не утворюють циклу з ребрами,, ...,, то>. Тепер додамо до дерева (2) ребро . У ньому з'явиться цикл, що містить ребро і, може бути, якісь (або всі) ребра,, ...,, але вони самі не утворюють циклу, тому в циклі буде обов'язково ребро d з набору, ...,, причому d>. Викинемо з отриманого графа з одним циклом ребро d. Ми знову отримаємо дерево, але воно буде на d-коротше мінімального, що неможливо. Отримане протиріччя доводить теорему для мережі з усіма різними ребрами.
4. Приклад роботи алгоритму Краскала
Малюнок 1. Початковий граф
Малюнок 2. Максимальне остовне дерево.
В алгоритмі Краскала ми не зберігаємо масив used [N]. Замість цього ми будемо на кожній ітерації алгоритму перевіряти, чи належать кінці розглянутого ребра до різних компонентів зв'язності (і додавати ребро до каркаса, якщо це так).
Введемо лічильник int counter = 0. Нехай N - кількість вершин графа.
Впорядкуємо список ребер по зростанню ваги.
Якщо counter == N - 1, закінчимо виконання алгоритму.
Проходячи по списку ребер, знайдемо ребро (i, j) таке, що i та j належать різним компонентам зв'язності. Так як список впорядкований по зростанню ваги ребер, ми будемо вибирати ребро з максимальною вагою, що задовольняє умові.
Додамо це ребро в каркас, збільшимо на одиницю лічильник counter.
Перейдемо до кроку 2.
При реалізації алгоритму можна використати систему непересічних множин для перевірки того, чи входять дві вершини в одну компоненту зв'язності (спочатку кожна вершина входить у своє безліч, при додаванні ребра в каркас два відповідних безлічі об'єднуються). Також для перевірки зв'язності двох вершин можна використовувати будь-який відомий алгоритм: пошук в ширину, пошук в глибину або що-небудь інше.
5. Код програми
// ---------------------------------------------
# include
# include
# include
// -------------------------------------------
typedef int * tint;// Покажчик на int
void main ()
{//int max = 100;// Максимальний вага ребра
int n;// кількість вершин
tint * G;// вихідний граф
tint * H;// матриця списку ребер з вагою
tint * K;/* матриця, яка зазначає належність
вершини компоненті */
tint * T;// матриця остовного дерева
tint * L;// список ребер з цінами мінімального дерева
// ----- введення графа
int max;
cout <<" Maximalno dopustimoe zna4enie vesa rebra = ";
cin>> max;
cout <<" n Vvedite 4ilo vershin: n ";
cin>> n;
G = new tint [n];
for (int i = 0; i
G [i] = new int [N];
cout <<" Vvedite nignij treugolnik matrici stoimosti: n ";
for (int i = 1; i
for (int j = 0; j
cin>> G [i] [J];
}
for (int i = 1; i
for (int j = 0; j
G [j] [i] = G [i] [j];
// --- виділення пам'яті для списку ребер ---
int kolreb = 0;
for (int i = 1; i
for (int j = 0; j
if (G [i] [j]
kolreb + +;
H = new tint [kolreb];
for (int i = 0; i
H [i] = new int [3];
// -------------------------------------------
int a = 0;
for (int i = 1; i
for (int j = 0; j
if (G [i] [j]
H [a] [0] = i +1;
H [a] [1] = j +1;
H [a] [2] = G [i] [J];
a + +;
}
cout <
// ---- сортування ребер по зростанню ваги
int f, d, s; ​​
for (int i = 0; i
for (int j = 0; j
if (H [j] [2]
f = H [j] [2];
H [j] [2] = H [j +1] [2];
H [j +1] [2] = f;
d = H [j] [0];
H [j] [0] = H [j +1] [0];
H [j +1] [0] = d;
s = H [j] [1];
H [j] [1] = H [j +1] [1];
H [j +1] [1] = s;
}
// вивід ребер відсортованих по зростання ваги
cout <<"Matrica dostigimosni otsortirovannoe po ubivaniuy: n ";
for (int i = 0; i
cout <";
cout <
cout <
cout <<" ";
}
for (int i = 0; i
H [i] [0] -;
H [i] [1] -;
}
// матриця для визначення компоненти
K = new tint [n];
for (int i = 0; i
K [i] = new int [2];
for (int i = 0; i
K [i] [0] = i;
K [i] [1] = 0;
}
// ---- матриця остовного дерева
T = new tint [n];
for (int i = 0; i
T [i] = new int [N];
for (int i = 0; i
for (int j = 0; j
T [i] [j] = 0;
//-приєднання першого ребра
T [H [0] [0]] [H [0] [1]] = H [0] [2];
T [H [0] [1]] [H [0] [0]] = H [0] [2];
K [H [0] [0]] [1] = 1;
K [H [0] [1]] [1] = 1;
// алгоритми з'єднання ребер без створення циклу:
int m = 2;// номер компоненти
for (int i = 1; i
if (K [H [i] [0]] [1]! = K [H [i] [1]] [1])
// якщо 2 вершини не з однієї компоненти
{
if (K [H [i] [0]] [1]> 0 && K [H [i] [1]] [1]> 0)
// якщо обидві вершини належать різним компоненті
{
for (int j = 0; j
if (K [H [i] [1]] [1] == K [j] [1])
K [j] [1] = K [H [I] [0]] [1];
K [H [i] [1]] [1] = K [H [i] [0]] [1];
T [H [i] [0]] [H [I] [1]] = H [i] [2];
T [H [i] [1]] [H [I] [0]] = H [i] [2];
}
if ((K [H [i] [0]] [1]> 0 && K [H [i] [1]] [1] == 0)
| | (K [H [i] [0]] [1] == 0 && K [H [i] [1]] [1]> 0))
// якщо одна вершина має компоненту а ін немає
{
if (K [H [i] [0]] [1]! = 0)
K [H [i] [1]] [1] = K [H [i] [0]] [1];...
