Subgraf și graf parțial

Un subgraf se obține prin eliminarea unor vârfuri împreună cu toate muchiile incidente lor. Un graf parțial păstrează toate vârfurile și elimină unele muchii. În triunghiul cu vârfurile 1, 2, 3 și muchiile [1,2], [2,3], [1,3], eliminarea vârfului 3 lasă subgraful cu vârfurile 1 și 2 și muchia [1,2]. Eliminarea doar a muchiei [1,3] dă un graf parțial cu trei vârfuri și două muchii.

Graful parțial păstrează toate vârfurile și elimină orice submulțime de muchii. Dacă graful inițial are $m$ muchii, are $2^m$ grafuri parțiale, incluzându-l pe el însuși și pe cel fără muchii. Subgraful se obține prin eliminarea unor vârfuri și a tuturor muchiilor incidente lor; pentru $n$ vârfuri există $2^n-1$ alegeri nevide ale vârfurilor rămase. Un subgraf obținut astfel este determinat de mulțimea vârfurilor păstrate, fiindcă rămân toate muchiile dintre ele (se numește și subgraf indus). Definiția generală din manuale permite ca un subgraf să piardă și muchii; în aceasta, un graf parțial este un caz particular de subgraf, iar cel obținut numai prin eliminarea vârfurilor este subgraful indus. În exerciții, citește enunțul: „se elimină vârfurile…” înseamnă subgraf indus, iar „se elimină muchiile…” înseamnă graf parțial.

În triunghiul cu vârfurile 1, 2, 3 și muchiile $[1,2]$, $[2,3]$, $[1,3]$, eliminarea vârfului 3 lasă vârfurile 1, 2 și muchia $[1,2]$; eliminarea numai a muchiei $[1,3]$ produce un graf parțial cu toate cele trei vârfuri și două muchii.

Exemplul 1 — subgrafurile induse ale triunghiului. Fiecare submulțime nevidă de vârfuri se codifică printr-o mască de biți, iar programul numără muchiile care au ambele capete în mască:

#include <iostream>
using namespace std;
int main() {
    int e[3][2] = {{1, 2}, {2, 3}, {1, 3}};
    for (int mask = 1; mask < 8; ++mask) {
        int c = 0;
        for (auto& m : e)
            if ((mask >> (m[0] - 1) & 1) && (mask >> (m[1] - 1) & 1)) ++c;
        cout << c << " ";
    }
}

Se afișează 0 0 1 0 1 1 3. Cele șapte măști sunt cele $2^3-1=7$ alegeri nevide: trei subgrafuri cu un singur vârf (0 muchii), trei cu două vârfuri (câte o muchie) și triunghiul întreg (3 muchii). Subgraful pe două vârfuri are exact o muchie, nu două, pentru că a treia muchie ar avea un capăt eliminat.

Exemplul 2 — grafurile parțiale ale triunghiului. Fiecare submulțime de muchii dă un graf parțial, deci sunt $2^3=8$. Programul numără câte dintre ele rămân conexe pe cele trei vârfuri:

#include <algorithm>
#include <iostream>
using namespace std;
int main() {
    int e[3][2] = {{1, 2}, {2, 3}, {1, 3}}, conexe = 0;
    for (int mask = 0; mask < 8; ++mask) {
        int c[4] = {0, 1, 2, 3};
        for (int rep = 0; rep < 3; ++rep)
            for (int i = 0; i < 3; ++i)
                if (mask >> i & 1) {
                    int mic = min(c[e[i][0]], c[e[i][1]]);
                    c[e[i][0]] = c[e[i][1]] = mic;
                }
        if (c[1] == c[2] && c[2] == c[3]) ++conexe;
    }
    cout << conexe;
}

Se afișează 4. Graful parțial fără muchii și cele trei cu o singură muchie nu sunt conexe, deoarece rămâne cel puțin un vârf izolat. Cele trei grafuri parțiale cu două muchii și triunghiul întreg sunt conexe. Între cele opt grafuri parțiale se află și graful inițial, ceea ce arată că definiția îl include.

Exemplul 3 — ciclul cu 4 vârfuri. Graful are vârfurile 1, 2, 3, 4 și muchiile $[1,2]$, $[2,3]$, $[3,4]$, $[4,1]$. Are $2^4=16$ grafuri parțiale. Dintre ele, 5 sunt conexe: graful întreg și cele patru obținute prin eliminarea câte unei muchii, adică lanțuri cu 3 muchii. Eliminarea vârfului 1 lasă 3 vârfuri și 2 muchii, $[2,3]$ și $[3,4]$. Eliminarea vârfurilor 1 și 3 lasă vârfurile 2 și 4, fără nicio muchie. La eliminarea vârfurilor 1 și 2 dispar trei muchii, $[1,2]$, $[2,3]$ și $[4,1]$, deci $4-3=1$ muchie rămâne, $[3,4]$; muchia $[1,2]$, incidentă cu ambele vârfuri eliminate, se scade o singură dată.

La eliminarea unui vârf, se elimină obligatoriu toate muchiile incidente lui. La eliminarea unei muchii, gradele celor două capete scad cu 1, dar numărul vârfurilor rămâne același. Pentru triunghi, subgraful indus de două vârfuri are exact o muchie. Pentru a număra muchiile unui subgraf indus, scade din $m$ muchiile incidente cu vârfurile eliminate, fără să numeri de două ori muchia dintre două vârfuri eliminate. Pentru a număra grafurile parțiale, ia în calcul doar muchiile: vârfurile rămân aceleași, iar numărul vine din $2^m$. De exemplu, în triunghiul cu vârfurile 1, 2, 3, eliminarea vârfului 1 lasă un subgraf cu 2 vârfuri și 1 muchie, deoarece dispar cele două muchii incidente lui 1, adică $3-2=1$ muchii rămase. Eliminarea muchiei $[2,3]$ lasă un graf parțial cu 3 vârfuri și 2 muchii, în care gradul lui 2 și gradul lui 3 au scăzut de la 2 la 1.

Exemplu în formatul examenului. Un graf neorientat are 4 vârfuri și 5 muchii. Câte grafuri parțiale distincte are, inclusiv el însuși și graful fără nicio muchie?

• a) 5
• b) 16
• c) 31
• d) 32

Răspunsul corect este d). Un graf parțial păstrează toate cele 4 vârfuri și se determină prin alegerea muchiilor păstrate dintre cele 5, deci există $2^5=32$ alegeri. Varianta b), $2^4$, numără submulțimile de vârfuri, nu de muchii. Varianta c), $2^5-1$, ar exclude exact un graf, iar enunțul îl include și pe cel inițial, și pe cel fără muchii. Varianta a) este numărul muchiilor.

Greșeli frecvente

• Greșit: după eliminarea vârfului 3, muchia $[2,3]$ rămâne.
  Corect: dispare odată cu vârful incident.
• Greșit: un graf parțial elimină obligatoriu și vârfuri.
  Corect: păstrează toate vârfurile.
• Greșit: subgraful obținut prin eliminarea vârfului 3 poate omite muchia $[1,2]$ din triunghi.
  Corect: păstrează toate muchiile dintre vârfurile rămase.

Înainte și după