Arbore parțial de cost minim

Un arbore parțial al unui graf neorientat conex păstrează toate vârfurile și exact atâtea muchii cât să le unească fără cicluri. Dintre acești arbori, cel de cost minim are suma ponderilor cea mai mică. Pentru un triunghi cu costuri 1, 2 și 5, alegem muchiile de cost 1 și 2; costul total este 3.

Un arbore parțial al unui graf neorientat conex este un graf parțial care este arbore: păstrează toate cele $n$ vârfuri și exact $n-1$ muchii, astfel încât să rămână conex și fără cicluri. Într-un graf ponderat, costul arborelui este suma ponderilor muchiilor alese, iar arborele parțial de cost minim este cel cu suma cea mai mică. În exemplul cu trei vârfuri, două muchii sunt suficiente; alegerea tuturor celor trei ar crea un ciclu și ar costa 8 în triunghiul cu ponderile 1, 2 și 5. Dacă graful nu este conex, nu există arbore parțial care să acopere toate vârfurile; se poate obține doar o pădure de arbori, câte unul pentru fiecare componentă.

Kruskal ordonează muchiile crescător după cost și le adaugă numai dacă nu creează un ciclu, adică numai dacă extremitățile lor sunt în componente diferite. Prim pornește dintr-un vârf și adaugă de fiecare dată muchia de cost minim care unește arborele construit cu un vârf din afara lui. Pentru triunghiul cu costurile $[1,2]$: 2, $[2,3]$: 3 și $[1,3]$: 7, ambele metode aleg primele două muchii și obțin costul total $2+3=5$.

Exemplul 1 — algoritmul lui Kruskal. Programul sortează muchiile după cost și folosește o structură de mulțimi disjuncte: două vârfuri sunt în aceeași componentă dacă au aceeași rădăcină.

#include <algorithm>
#include <iostream>
using namespace std;
struct Muchie { int x, y, c; };
int t[11];
int radacina(int x) { return t[x] == x ? x : t[x] = radacina(t[x]); }
int main() {
    int n, m;
    Muchie e[50];
    cin >> n >> m;
    for (int i = 0; i < m; ++i) cin >> e[i].x >> e[i].y >> e[i].c;
    stable_sort(e, e + m, [](const Muchie& a, const Muchie& b) { return a.c < b.c; });
    for (int i = 1; i <= n; ++i) t[i] = i;
    int cost = 0;
    for (int i = 0; i < m; ++i) {
        int a = radacina(e[i].x), b = radacina(e[i].y);
        if (a != b) {
            t[a] = b;
            cost += e[i].c;
            cout << e[i].x << "-" << e[i].y << " ";
        }
    }
    cout << "\n" << cost;
}

Graful are 4 vârfuri și muchiile $[1,2]$ cu costul 4, $[1,3]$ cu 1, $[2,3]$ cu 2, $[2,4]$ cu 5 și $[3,4]$ cu 3. Pentru intrarea 4 5 urmată de aceste muchii, programul afișează 1-3 2-3 3-4, apoi 6. Muchia $[1,2]$ de cost 4 este respinsă, fiindcă 1 și 2 sunt deja în aceeași componentă prin 1–3–2, iar muchia $[2,4]$ de cost 5 este respinsă, fiindcă 4 a fost deja legat prin $[3,4]$. Se aleg exact $n-1=3$ muchii. Sortarea cere $O(m\log m)$ timp.

Exemplul 2 — algoritmul lui Prim pe același graf. Se pornește din vârful 1. Dintre muchiile care ies din $\{1\}$, cea mai ieftină este $[1,3]$ cu 1. Din $\{1,3\}$ ies $[1,2]$ cu 4, $[2,3]$ cu 2 și $[3,4]$ cu 3; se alege $[2,3]$. Din $\{1,2,3\}$ ies $[2,4]$ cu 5 și $[3,4]$ cu 3; se alege $[3,4]$. Costul este $1+2+3=6$, ca la Kruskal. Dacă toate ponderile sunt distincte, arborele parțial de cost minim este unic; dacă există ponderi egale, pot exista mai mulți arbori cu același cost minim, dar costul minim este același.

Costul minim se calculează adunând doar muchiile alese, nu toate muchiile. Un arbore parțial are $n-1$ muchii, deci costul unui arbore parțial nu poate fi calculat ca suma celor mai mici $n-1$ costuri fără să verifici ciclurile. Dacă un graf conex are $n=5$ vârfuri, orice arbore parțial al lui are 4 muchii.

Exemplul 3 — în formatul examenului. Un graf ponderat are 5 vârfuri și muchiile $[1,2]$ cu costul 3, $[1,3]$ cu 1, $[2,3]$ cu 2, $[3,4]$ cu 4, $[4,5]$ cu 1, $[2,5]$ cu 6 și $[3,5]$ cu 5. Care este costul unui arbore parțial de cost minim?

• a) 7
• b) 8
• c) 9
• d) 10

Răspunsul corect este b). Kruskal alege, în ordinea costurilor, $[1,3]$ (1), $[4,5]$ (1), $[2,3]$ (2); muchia $[1,2]$ (3) se respinge, fiindcă 1, 2 și 3 sunt deja unite și ar apărea ciclul 1–2–3. Muchia $[3,4]$ (4) unește componentele $\{1,2,3\}$ și $\{4,5\}$ și se alege. Costul este $1+1+2+4=8$, iar arborele are 4 muchii. Varianta a) adună cele mai mici patru costuri, 1, 1, 2 și 3, dar muchia de cost 3 închide un ciclu. Variantele c) și d) sunt costuri ale unor arbori parțiali, dar nu minimi: c) folosește $[3,5]$ (5) în loc de $[3,4]$ (4), iar d) folosește $[2,5]$ (6).

Greșeli frecvente

• Greșit: un arbore parțial minim este un drum de cost minim între două vârfuri.
  Corect: unește toate vârfurile la cost total minim.
• Greșit: un arbore pe $n$ vârfuri are $n$ muchii.
  Corect: are $n-1$.
• Greșit: graful neconex are totuși un arbore parțial care acoperă toate vârfurile.
  Corect: nu există fără legături între componente.

Înainte și după