Arbore parțial

Ce este

Pornim de la un graf conex cu n noduri și m muchii. Un arbore parțial (în engleză spanning tree) este un graf parțial al lui care este, în plus, arbore. Desfăcut pe bucăți:

• graf parțial — păstrezi toate cele n noduri și alegi doar o submulțime a muchiilor;
• arbore — ce alegi rămâne conex (din orice nod ajungi în oricare altul) și fără cicluri (între oricare două noduri există exact un drum).

Cele două condiții forțează numărul de muchii: un arbore cu n noduri are întotdeauna exact n-1 muchii. Una mai puțin — graful se rupe în două bucăți; una mai mult — apare garantat un ciclu. Deci dintr-un graf conex cu m muchii arunci exact m - (n-1) muchii, indiferent pe care le alegi.

De aici și condiția de existență: un graf are arbore parțial dacă și numai dacă este conex. Dacă graful e rupt în bucăți, nicio alegere de muchii nu mai poate lega totul — muchiile lipsă nu le poți inventa, doar selecta dintre cele existente.

Cum arată

Fie un graf conex cu 4 noduri (1, 2, 3, 4) și 5 muchii. Observă ciclul format de nodurile 1 - 2 - 3 - 1:

Avem n = 4 noduri, deci un arbore parțial are exact 4 - 1 = 3 muchii — și aruncăm 5 - 3 = 2. O alegere validă:

Am renunțat la muchia 1-3 (ar fi închis ciclul 1-2-3-1) și la 2-4 (al doilea drum spre nodul 4, deci alt ciclu). Dar puteam la fel de bine să păstrăm 1-3 și să aruncăm 1-2 — obțineam un alt arbore parțial, tot cu 3 muchii. Alegerea nu e unică; numărul de muchii, da.

Urmărește același proces în mișcare: muchiile sunt examinate una câte una, iar fiecare este păstrată sau respinsă. Fii atent la momentul respingerii — se întâmplă exact atunci când ambele capete ale muchiei sunt deja legate prin muchiile păstrate, deci adăugarea ei ar închide un ciclu.

Implementare C++

Cel mai simplu mod de a construi un arbore parțial este cu o parcurgere DFS: plecăm dintr-un nod și, de fiecare dată când DFS ajunge prima dată la un nod nou, păstrăm muchia pe care a venit. Aceste „muchii de descoperire" formează exact un arbore parțial: fiecare dintre celelalte n-1 noduri e descoperit o singură dată (deci n-1 muchii, fără ciclu), iar DFS-ul atinge toate nodurile grafului conex (deci rămâne conex).

#include <iostream>
#include <vector>
using namespace std;

int n, m;
vector<int> adiacenta[105];     // liste de adiacenta
bool vizitat[105];

// construieste arborele partial: afiseaza muchiile de descoperire
void dfs(int nod) {
    vizitat[nod] = true;
    for (int vecin : adiacenta[nod]) {
        if (!vizitat[vecin]) {
            // prima data cand ajungem la vecin: pastram muchia nod-vecin
            cout << nod << " - " << vecin << "\n";
            dfs(vecin);
        }
    }
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int x, y;
        cin >> x >> y;
        adiacenta[x].push_back(y);
        adiacenta[y].push_back(x);
    }

    // graful e conex: un singur DFS atinge toate nodurile
    dfs(1);
    // afiseaza exact n-1 muchii (aici 3 pentru n=4)
    return 0;
}

Pentru intrarea n=4, m=5 cu muchiile 1-2 2-3 1-3 3-4 2-4, DFS pornit din 1 descoperă 2 (păstrează 1-2), apoi din 2 descoperă 3 (păstrează 2-3), apoi din 3 descoperă 4 (păstrează 3-4) — exact n-1 = 3 muchii. Muchiile 1-3 și 2-4 duc spre noduri deja vizitate și sunt ignorate: ele ar fi închis un ciclu. Bonus de diagnostic: dacă graful nu era conex, DFS-ul ar fi afișat mai puțin de n-1 muchii — semn sigur că arborele parțial nu există.