Graf parțial

Ce este

Un graf are două ingrediente: nodurile (cine) și muchiile (cine cu cine). Când construiești un graf parțial, atingi un singur ingredient: muchiile.

Formal: fie un graf neorientat G = (V, E), unde V e mulțimea nodurilor și E mulțimea muchiilor. Un graf parțial al lui G este un graf G' = (V, E') în care:

• mulțimea nodurilor este exact aceeași — toate nodurile din V se păstrează;
• mulțimea muchiilor E' este o submulțime a lui E.

Cu alte cuvinte, un graf parțial se obține din G ștergând muchii (eventual niciuna, eventual toate), dar fără să atingi nodurile. Cazurile extreme sunt și ele grafuri parțiale: G însuși (nu ștergi nimic) și graful cu toate nodurile dar zero muchii (ștergi tot).

De aici iese și numărarea: un graf cu m muchii are exact $2^m$ grafuri parțiale, fiindcă pentru fiecare muchie decizi independent dacă o păstrezi sau o ștergi — două variante per muchie, deci $2 \cdot 2 \cdot \ldots \cdot 2$ de $m$ ori. Pentru pătratul de mai jos, cu $m = 4$ muchii, există $2^4 = 16$ grafuri parțiale.

De ce merită reținută noțiunea: cel mai celebru graf parțial este arborele parțial — un graf parțial care e conex și fără cicluri, adică păstrezi exact atâtea muchii cât să legi toate cele n noduri. Pe el se construiește arborele parțial de cost minim (Kruskal, Prim), unul dintre algoritmii-vedetă ai clasei a XI-a. Definiția de azi e fundația lui.

Cum arată

Pornește vizualizarea de la graful complet și urmărește ce se întâmplă când păstrezi doar unele muchii: nodurile stau pe loc, iar legăturile se răresc.

Același lucru, pe un exemplu concret cu liste de muchii. Pornim de la un graf pe 4 noduri, în formă de pătrat:

Construim un graf parțial ștergând muchia 2-3. Nodurile rămân toate patru, dar lista de muchii pierde un element:

Observă că nodul 2 și nodul 3 există în continuare în G' — doar legătura directă dintre ele a dispărut. Asta îl deosebește de un subgraf, unde am fi putut elimina chiar nodul 2 cu totul (și, odată cu el, muchiile 1-2 și 2-3).

Implementare C++

Citim graful întreg și indicii muchiilor pe care le păstrăm. Construim graful parțial copiind doar aceste muchii în matricea de adiacență. Toate cele n noduri rămân prezente — matricea are aceeași dimensiune, doar pornește goală.

#include <iostream>
using namespace std;

int adiacenta[105][105];      // graful partial: 1 daca exista muchie
int x[10005], y[10005];       // capetele celor m muchii din G

int main() {
    int n, m;
    cin >> n >> m;            // n noduri, m muchii in graful G
    for (int i = 0; i < m; i++) {
        cin >> x[i] >> y[i];  // muchia i leaga nodurile x[i] si y[i]
    }

    int k;
    cin >> k;                 // cate muchii pastram in graful partial
    for (int t = 0; t < k; t++) {
        int idx;
        cin >> idx;           // indicele muchiei pastrate (0..m-1)
        // pastram doar aceasta muchie; nodurile raman toate
        adiacenta[x[idx]][y[idx]] = 1;
        adiacenta[y[idx]][x[idx]] = 1;
    }

    // afisam graful partial: toate cele n noduri raman prezente
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cout << adiacenta[i][j] << " ";
        }
        cout << "\n";
    }

    // numarul de grafuri partiale: 2^m (long long, altfel overflow)
    if (m <= 62) {
        cout << "grafuri partiale: " << (1LL << m) << "\n";  // ex: m=4 -> 16
    }
    return 0;
}
// Pentru n=4, muchiile 1-2,2-3,3-4,4-1 si k=3 muchii pastrate (0,2,3),
// graful partial are muchiile 1-2, 3-4, 4-1 (muchia 2-3 lipseste).

Cheia: bucla de afișare merge de la 1 la n indiferent câte muchii am păstrat. Nodurile nu se ating niciodată — doar matricea de muchii pornește goală și primește exact muchiile selectate.