Arbori. Arbori parțiali de cost minim

Pentru a lega între ele toate casele unui sat printr-o rețea de cablu se folosesc cât mai puține legături: fiecare casă trebuie să fie conectată, iar o legătură care închide un ciclu poate lipsi fără ca vreo casă să rămână izolată. Graful unei asemenea rețele este un arbore. Dacă fiecare legătură posibilă are un cost, rețeaua cea mai ieftină corespunde unui arbore parțial de cost minim al grafului legăturilor posibile.

Lecția prezintă:

• arborele, teorema de caracterizare și proprietățile arborilor;
• arborele parțial și determinarea lui printr-o parcurgere;
• arborele parțial de cost minim și algoritmii lui Kruskal și Prim.

Noțiuni preliminare

Arborii se definesc cu ajutorul următoarelor noțiuni:

• graful neorientat este o pereche G = (X, U), în care X este o mulțime finită și nevidă de noduri, iar U o mulțime de muchii;
• lanțul elementar este un lanț în care nodurile sunt distincte;
• ciclul este un lanț simplu ale cărui extremități coincid;
• graful este conex dacă între oricare două noduri distincte există un lanț;
• graful parțial al lui G are aceleași noduri ca G și o parte dintre muchiile lui.

Terminologia completă este în subcapitolul Grafuri orientate și neorientate. Terminologie, iar conexitatea în subcapitolul Conexitate și tare conexitate.

Arborele

Definiția arborelui

U = {[1,2], [1,3], [2,4],
     [2,5], [3,6], [6,7],
     [6,8]}

Arborele desenat are nodul 1 sus, dar definiția nu privilegiază niciun nod: oricare nod poate fi desenat în partea de sus. Arborele în care se alege un nod numit rădăcină este prezentat în subcapitolul Arbori cu rădăcină și arbori binari.

Contraexemple. Graful din stânga este conex, dar conține ciclul (1, 2, 3, 4, 1). Graful din dreapta nu conține cicluri, dar nu este conex. Niciunul nu este arbore.

Teorema de caracterizare

Teoremă. Fie G un graf neorientat cu n noduri și m muchii. Următoarele afirmații sunt echivalente:

1. G este arbore (definiția: G este conex și nu conține cicluri);
2. G nu conține cicluri și are m = n − 1 muchii;
3. G este conex și are m = n − 1 muchii;
4. G nu conține cicluri și este maximal cu această proprietate: dacă se leagă printr-o muchie nouă două noduri neadiacente, graful obținut are un ciclu;
5. G este conex și este minimal cu această proprietate: prin eliminarea oricărei muchii graful devine neconex;
6. oricare două noduri ale lui G sunt legate printr-un lanț elementar și numai unul.

Oricare dintre afirmații se poate lua ca definiție a arborelui. Justificările de mai jos arată ideile pe care se sprijină echivalențele.

Un arbore cu n noduri are n − 1 muchii. Un arbore cu cel puțin 2 noduri are un nod terminal: altfel, pornind dintr-un nod și mergând de fiecare dată pe o muchie nefolosită, s-ar ajunge a doua oară într-un nod, deci s-ar forma un ciclu. Eliminând un nod terminal și muchia lui, se obține un arbore cu un nod mai puțin. Repetând eliminarea până rămâne un singur nod, se elimină n − 1 noduri și tot atâtea muchii.

Lanțul dintre două noduri este unic. Arborele este conex, deci lanțul există. Dacă între nodurile x și y ar exista două lanțuri elementare diferite, porțiunile prin care ele diferă ar forma împreună un ciclu.

Minimalitate și maximalitate. Dacă se elimină muchia [x, y], singurul lanț dintre x și y dispare, deci graful devine neconex. Dacă se adaugă muchia [x, y], ea formează un ciclu cu lanțul care exista deja între x și y.

Proprietăți ale arborilor

Din teorema de caracterizare rezultă:

• orice arbore cu n ≥ 2 noduri are cel puțin două noduri terminale;
• adăugarea unei muchii la un arbore formează exact un ciclu;
• un graf fără cicluri cu n noduri și p componente conexe are n − p muchii, fiindcă fiecare componentă este un arbore;
• dintr-un graf conex cu n noduri și m muchii trebuie eliminate m − n + 1 muchii pentru a se obține un arbore.

Condiția m = n − 1 singură nu este suficientă: graful cu nodurile {1, 2, 3, 4, 5} și muchiile [1,2], [1,5], [2,5], [3,4] are 4 muchii, dar conține ciclul (1, 2, 5, 1) și nu este conex.

Verificarea unui arbore

Enunț. Se citește un graf neorientat cu n noduri și m muchii. Să se verifice dacă graful este arbore.

Programul folosește afirmația 3 din teorema de caracterizare: graful este arbore dacă are n − 1 muchii și este conex. Conexitatea se verifică printr-o parcurgere în adâncime pornită din nodul 1.

#include <iostream>
using namespace std;

const int MAX = 101;
int a[MAX][MAX], viz[MAX], n, m;

void citire() {
    int x, y;
    cin >> n >> m;
    for (int k = 1; k <= m; k++) {
        cin >> x >> y;
        a[x][y] = a[y][x] = 1;
    }
}

void dfs(int x) {
    viz[x] = 1;
    for (int j = 1; j <= n; j++)
        if (a[x][j] == 1 && viz[j] == 0)
            dfs(j);
}

/* Graful este conex daca parcurgerea din nodul 1 viziteaza toate nodurile. */
int conex() {
    dfs(1);
    for (int i = 1; i <= n; i++)
        if (viz[i] == 0)
            return 0;
    return 1;
}

int main() {
    citire();
    if (m != n - 1)
        cout << "Graful nu este arbore: are " << m << " muchii, nu " << n - 1 << "\n";
    else if (conex() == 0)
        cout << "Graful nu este arbore: nu este conex\n";
    else
        cout << "Graful este arbore\n";
    return 0;
}

Pentru arborele G15 programul afișează Graful este arbore. Pentru graful cu ciclu din contraexemplu afișează Graful nu este arbore: are 4 muchii, nu 3, iar pentru graful cu muchiile [1,2], [1,5], [2,5], [3,4] afișează Graful nu este arbore: nu este conex.

Descrierea soluției. Numărul muchiilor se compară direct cu n − 1. Numai dacă această condiție este îndeplinită se apelează conex, care pornește parcurgerea dfs din nodul 1 și verifică dacă toate nodurile au fost vizitate. Cu matricea de adiacență, timpul este de ordinul O(n²). Rezolvarea subiectului de la Titularizare 2024 folosește aceeași idee.

Arborele parțial

Definiție

Un arbore parțial al grafului G este un graf parțial al lui G care este arbore. Arborele parțial păstrează toate nodurile grafului și n − 1 dintre muchii.

Teoremă. Un graf neorientat conține un arbore parțial dacă și numai dacă este conex.

Dacă graful conține un arbore parțial, el este conex, fiindcă arborele parțial leagă deja oricare două noduri. Invers, dacă graful este conex și conține un ciclu, se elimină o muchie a ciclului; graful rămâne conex, fiindcă nodurile muchiei eliminate sunt legate prin restul ciclului. Eliminarea se repetă până nu mai rămân cicluri, iar graful obținut este un arbore parțial.

Un graf conex are, în general, mai mulți arbori parțiali.

Determinarea unui arbore parțial

Enunț. Se citește un graf neorientat conex. Să se afișeze muchiile unui arbore parțial.

#include <iostream>
using namespace std;

const int MAX = 101;
int a[MAX][MAX], viz[MAX], coada[MAX], n, m;

void citire() {
    int x, y;
    cin >> n >> m;
    for (int k = 1; k <= m; k++) {
        cin >> x >> y;
        a[x][y] = a[y][x] = 1;
    }
}

/* Parcurgerea in latime din nodul pl. Muchia [coada[p], j] pe care
   nodul j intra in coada face parte din arborele partial. */
void BF(int pl) {
    int p = 1, u = 1;
    coada[1] = pl;
    viz[pl] = 1;
    while (p <= u) {
        for (int j = 1; j <= n; j++)
            if (a[coada[p]][j] == 1 && viz[j] == 0) {
                u++;
                coada[u] = j;
                viz[j] = 1;
                cout << "[" << coada[p] << "," << j << "] ";
            }
        p++;
    }
}

int main() {
    citire();
    BF(1);
    cout << "\n";
    return 0;
}

Pentru graful G16 programul afișează [1,2] [1,3] [2,4] [3,5] [4,6] [5,7].

Descrierea soluției. Subprogramul BF este parcurgerea în lățime din subcapitolul Parcurgerea grafurilor, completată cu afișarea muchiei [coada[p], j] în momentul în care nodul j intră în coadă. Parcurgerea în adâncime se folosește la fel: se afișează muchia [x, j] înaintea apelului recursiv pentru j. Arborele parțial obținut depinde de parcurgere și de nodul de pornire.

Arborele parțial de cost minim

Definiții

Teoremă. Dintre grafurile parțiale conexe ale unui graf conex cu costuri pozitive, cel de cost minim este un arbore.

Dacă graful parțial conex de cost minim ar conține un ciclu, prin eliminarea unei muchii a ciclului s-ar obține un graf parțial tot conex, cu costul mai mic, ceea ce nu se poate. Prin urmare, problema legării tuturor nodurilor cu cost minim se reduce la determinarea unui arbore parțial de cost minim.

Arborele parțial de cost minim nu este, în general, unic: dacă mai multe muchii au același cost, pot exista mai mulți arbori parțiali cu același cost minim. Costul minim este însă unic.

Principiul algoritmilor

Algoritmii lui Kruskal și Prim folosesc metoda greedy: construiesc arborele muchie cu muchie și, la fiecare pas, aleg muchia cea mai ieftină care păstrează proprietățile cerute, fără a reveni asupra alegerii. Alegerea se sprijină pe următoarea proprietate.

Proprietate. Dacă nodurile grafului se împart în două mulțimi nevide, o muchie de cost minim dintre cele care au câte o extremitate în fiecare mulțime face parte dintr-un arbore parțial de cost minim.

Dacă un arbore parțial de cost minim T nu conține această muchie [x, y], lanțul din T dintre x și y trece de la o mulțime la cealaltă pe o muchie [p, q], cu costul cel puțin c([x, y]). Înlocuind în T muchia [p, q] cu [x, y], se obține tot un arbore parțial, cu costul cel mult egal cu al lui T, deci tot de cost minim.

Cei doi algoritmi diferă prin felul în care aleg cele două mulțimi:

• Kruskal pornește de la n arbori formați din câte un nod și unește, la fiecare pas, doi arbori prin muchia cea mai ieftină care îi leagă;
• Prim pornește de la un singur nod și adaugă, la fiecare pas, muchia cea mai ieftină care leagă arborele de un nod din afara lui.

Algoritmul lui Kruskal

Descrierea algoritmului

Graful se memorează prin lista muchiilor, ordonată crescător după cost. Pentru a ști în ce arbore se află fiecare nod se folosește vectorul comp, cu comp[i] = numărul arborelui care conține nodul i.

Etapele algoritmului:

1. Muchiile se sortează crescător după cost.
2. Fiecare nod formează un arbore separat: comp[i] = i.
3. Muchiile se examinează în ordinea costurilor. Muchia [x, y] se alege dacă comp[x] ≠ comp[y], adică extremitățile ei sunt în arbori diferiți; altfel ar închide un ciclu și se respinge.
4. După alegerea muchiei, cei doi arbori se unesc: toate nodurile cu comp egal cu comp[y] primesc valoarea comp[x].
5. Algoritmul se oprește după alegerea a n − 1 muchii.

Kruskal():
    sortează muchiile u[1..m] după cost
    pentru j ← 1, n execută
        comp[j] ← j
    sfpentru
    i ← 1; k ← 0; total ← 0
    cât timp k < n − 1 execută
        dacă comp[u[i].x] ≠ comp[u[i].y]
        atunci
            k ← k + 1
            total ← total + u[i].c
            scrie u[i].x, u[i].y
            compY ← comp[u[i].y]
            compX ← comp[u[i].x]
            pentru j ← 1, n execută
                dacă comp[j] = compY atunci
                    comp[j] ← compX
                sfdacă
            sfpentru
        sfdacă
        i ← i + 1
    sfcât timp

struct muchie {
    int x, y, c;
} u[MAXM];

Exemplificarea etapelor

Pentru graful G16, lista muchiilor sortată crescător după cost este:

Inițial comp = (1, 2, 3, 4, 5, 6, 7). Muchiile se examinează astfel:

Etapele se pot urmări pas cu pas în simulatorul algoritmului lui Kruskal, pe un alt graf cu 7 noduri.

Programul

Enunț. Se citește un graf neorientat conex cu n noduri și m muchii, dat prin lista muchiilor, fiecare cu costul ei. Să se afișeze muchiile unui arbore parțial de cost minim și costul lui.

Date de intrare. Pe prima linie n și m, pe fiecare dintre următoarele m linii extremitățile și costul unei muchii. Pentru graful G16:

7 11
1 2 2
1 3 4
2 3 3
2 4 7
3 4 5
3 5 6
4 5 1
4 6 9
5 6 8
5 7 12
6 7 10