De ce contează?
Ai o rețea întreagă de prieteni: zeci de oameni și relațiile dintre ei. Vrei să studiezi doar grupul de la clasa ta. Iei deoparte exact acei oameni și păstrezi doar prieteniile DINTRE ei — pe cele către restul școlii le lași afară, fiindcă au un capăt în afara grupului. Ce-ți rămâne în mână e tot o rețea, dar mai mică: acesta este un subgraf.
Ce este
Pleci de la un graf mare și alegi o parte din noduri. Un subgraf nu inventează nimic nou: ia o submulțime de noduri și păstrează doar muchiile care leagă două noduri rămase. O muchie cu un singur capăt în grupul ales pică automat — n-ar avea unde să se sprijine. Gândește-te la el ca la un „decupaj": tai din graf o zonă de noduri și vezi ce relații supraviețuiesc complet în interiorul ei.
Formal: fie un graf G = (V, E), cu mulțimea de noduri V și mulțimea de
muchii E. Un subgraf al lui G se construiește astfel:
- alegi o submulțime de noduri
V'inclusă înV; - păstrezi o muchie din
Edoar dacă ambele ei capete sunt înV'.
Forma cea mai des folosită — și cea pe care o cere implicit majoritatea
problemelor — este subgraful indus de V': păstrezi toate muchiile lui G
care au ambele capete în V', niciuna în plus, niciuna în minus. Practic, „ce
spune G despre nodurile din V'".
Ține minte într-o singură propoziție: la subgraf scoți noduri (și muchiile lor pleacă odată cu ele), la graf parțial scoți muchii (nodurile rămân toate pe loc). Dacă numărul de noduri scade, e subgraf; dacă scad doar muchiile, e parțial.
Subgraf sau graf parțial?
Distincția e greșeala clasică de bacalaureat, așa că merită pusă față în față:
| Subgraf | Graf parțial | |
|---|---|---|
| Ce alegi | o submulțime de noduri V' | o submulțime de muchii E' |
| Noduri | doar cele din V' — numărul lor scade | toate cele n — neatinse |
| Muchii | vin obligatoriu: toate cele cu ambele capete în V' | doar cele alese din E |
| Câte există | (o submulțime nevidă de noduri) | (fiecare muchie: da/nu) |
| Test rapid | a scăzut numărul de noduri? | nodurile sunt toate pe loc? |
De ce ? Pentru că fiecare submulțime nevidă de noduri induce exact
un subgraf — muchiile nu se aleg, vin singure. Observă și că G însuși este
propriul lui subgraf (alegi V' = V), la fel cum este și propriul graf parțial.
Cum arată
Pornește animația de mai jos. Plecăm de la graful întreg cu 6 noduri și scoatem
pe rând nodurile 5 și 0. Urmărește două lucruri: nodul scos se stinge, iar
odată cu el se sting toate muchiile care îl atingeau — întâi 4-5 și 3-5,
apoi 0-1 și 0-2. Nimeni nu le șterge separat; dispar pentru că le-a dispărut
un capăt.
Folosește ← și → ca să pășești scoatere cu scoatere, sau Redă pentru animația completă. Urmărește contorul de jos: când scoți un nod, vezi cum scade și numărul de muchii — pleacă toate muchiile lui dintr-o dată.
Graful din animație are nodurile {0, 1, 2, 3, 4, 5} și muchiile:
0-1, 0-2, 1-2, 1-3, 2-4, 3-4, 4-5, 3-5.
După ce scoatem nodurile 0 și 5 rămâne submulțimea V' = {1, 2, 3, 4}.
Verificăm fiecare muchie: o ținem doar dacă ambele capete sunt în V'.
| Muchie | Capete în V'? | Rămâne? |
|---|---|---|
0-1 | nodul 0 lipsește | nu |
0-2 | nodul 0 lipsește | nu |
1-2 | ambele în V' | da |
1-3 | ambele în V' | da |
2-4 | ambele în V' | da |
3-4 | ambele în V' | da |
4-5 | nodul 5 lipsește | nu |
3-5 | nodul 5 lipsește | nu |
Subgraful indus de {1, 2, 3, 4} are deci 4 noduri și 4 muchii:
1-2 | 1-3 | 2-4 | 3-4 |
0 | 1 | 2 | 3 |
Implementare C++
Citim graful, marcăm nodurile din V' și tipărim subgraful indus: toate muchiile
cu ambele capete marcate. Pe graful de mai sus, cu V' = {1, 2, 3, 4}, rezultatul
este exact tabelul de mai sus.
#include <iostream>
using namespace std;
int main() {
int n, m;
cin >> n >> m; // n noduri, m muchii
int U[1005], V[1005]; // capetele fiecarei muchii
for (int i = 0; i < m; i++)
cin >> U[i] >> V[i];
// marcam nodurile din submultimea V'
bool inSub[1005] = {false};
int k;
cin >> k; // cate noduri pastram
for (int i = 0; i < k; i++) {
int x;
cin >> x;
inSub[x] = true;
}
// pastram doar muchiile cu AMBELE capete in V'
for (int i = 0; i < m; i++) {
if (inSub[U[i]] && inSub[V[i]])
cout << U[i] << " - " << V[i] << "\n";
}
// pentru V' = {1,2,3,4} tipareste: 1-2, 1-3, 2-4, 3-4
return 0;
}Cheia este condiția inSub[U[i]] && inSub[V[i]]: cu && (ȘI) ceri ca ambele
capete să fie în submulțime. O singură verificare nu ar fi de ajuns.
Două capcane care pică an de an la bac și la lucrări:
1. Confunzi subgraful cu graful parțial. Ți se cere un subgraf și tu ștergi
doar muchii, lăsând toate nodurile pe foaie — ai desenat un graf parțial.
Testul rapid: la subgraf numărul de noduri scade (sau măcar poate scădea);
la parțial rămâne exact n.
2. În cod, păstrezi muchia dacă măcar un capăt e în submulțime — adică
folosești || (SAU) în loc de && (ȘI), sau verifici doar U[i] și uiți de
V[i]. Atunci ții o muchie precum 0-1 (cu V' = {1,2,3,4}), care iese din
grupul ales: capătul 0 nu mai există în subgraf, deci muchia ar atârna în gol.
Un subgraf corect nu are nicio muchie cu vreun capăt în afara lui V'.