De ce contează?
Un orar de zboruri, harta unui metrou, lista de prietenii dintr-o rețea socială și un joc de tip „puzzle cu mutări" par patru lucruri complet diferite. Și totuși, un informatician le vede pe toate la fel: niște puncte legate prin săgeți. Cele mai multe probleme care par diferite sunt, de fapt, aceeași problemă de graf deghizată — iar trucul nu e să știi un algoritm nou, ci să dezbraci deghizarea.
Ideea-cheie
Un graf nu e un subiect aparte din enunț — e o lentilă prin care privești problema. Cheia e că nu cauți cuvântul „graf" în text (n-o să-l găsești aproape niciodată). Cauți două lucruri: niște entități și relații între ele. În clipa în care le-ai identificat, ai graful: entitățile devin noduri, iar relațiile devin muchii (sau arce, dacă au sens).
Toată dificultatea unei probleme de graf se mută atunci în prima decizie: ce aleg drept nod și ce aleg drept muchie?. După ce ai răspuns corect la asta, algoritmii pe care îi știi deja (parcurgere, drum minim, componente conexe) se aplică direct.
Reflexul de antrenat: când într-un enunț vezi „entități + relații între ele", modelează imediat ca graf. Entitățile = nodurile. Relațiile dintre ele = muchiile sau arcele. Restul enunțului (numere, condiții, întrebarea finală) îți spune doar ce fel de graf e și ce algoritm rulezi pe el.
Cum alegi
Mai întâi, semnalele din enunț care strigă „graf", chiar dacă textul nu pomenește cuvântul:
- relații binare — „X e legat de Y", „A cunoaște pe B", „din P se poate ajunge în Q";
- transformări pas cu pas — dintr-o configurație obții alta printr-o operație permisă (mutări, schimbări de o literă, turnări dintr-un vas în altul);
- rețele și hărți — orașe și drumuri, calculatoare și cabluri, stații și linii;
- întrebări-tip: „numărul minim de pași", „se poate ajunge din... în...?", „câte grupuri separate?".
Ai văzut un semnal? Atunci pune-ți patru întrebări, mereu în aceeași ordine: ce e nodul? ce e muchia? e orientat sau nu? e ponderat sau nu?. Hai să le aplicăm pe trei enunțuri care sună diferit, dar se modelează la fel.
Exemplul 1: orașe + drumuri
„Sunt
norașe, legate prin șosele cu două sensuri. Vrei drumul cel mai scurt de la orașulAla orașulB."
- Nodul = un oraș. (Entitatea.)
- Muchia = o șosea între două orașe. (Relația.)
- Orientat? Nu. Șoseaua are două sensuri, deci poți merge
A→BșiB→A. E un graf neorientat: muchia merge în ambele direcții. - Ponderat? Da. „Cel mai scurt" înseamnă că fiecare șosea are o lungime — o pondere pe muchie. (Dacă întrebarea ar fi „număr minim de orașe traversate", ar fi neponderat și ar ajunge un BFS.)
Exemplul 2: stările unui joc + mutări
„Ai un puzzle. Dintr-o configurație poți ajunge în altele printr-o mutare permisă. Câte mutări minim duc de la configurația de start la cea finală?"
Aici nu există „orașe" — și totuși e tot un graf. Trucul: o stare a jocului este un nod.
- Nodul = o configurație posibilă a jocului (o stare).
- Arcul = o mutare permisă care duce dintr-o stare în alta.
- Orientat? Da, de regulă. O mutare poate fi ireversibilă: din starea
Xajungi înY, dar dinYs-ar putea să nu te poți întoarce înX. De aceea relația are sens și folosim arce (săgeți), nu muchii. - Ponderat? Nu, dacă fiecare mutare costă „1". „Număr minim de mutări" = drumul cel mai scurt în muchii → un BFS din starea de start.
Observă saltul: nodurile nu mai sunt obiecte fizice, ci situații. Acesta e pasul de modelare care derutează cel mai des — și care deblochează cele mai multe probleme de olimpiadă.
Exemplul 3: oameni + prietenii
„Într-o rețea sunt
npersoane. Unele perechi sunt prietene. Vrei să afli din câte grupuri separate de prieteni e formată rețeaua."
- Nodul = o persoană.
- Muchia = o prietenie între două persoane.
- Orientat? Nu. Prietenia e reciprocă: dacă
Anae prietenă cuBogdan, atunci șiBogdane prieten cuAna. Relație simetrică → graf neorientat. - Ponderat? Nu. Întrebarea e doar „cine e legat de cine", nu „cât de tare". Iar „câte grupuri separate" = câte componente conexe are graful.
Trei enunțuri, trei domenii (geografie, jocuri, social) — și aceeași schemă în patru întrebări. Pune-le mereu, în ordine, și graful apare singur.
Trei greșeli de modelare strică tot, înainte să rulezi vreun algoritm:
1. Pui muchie unde relația are sens unic. Dacă din starea X ajungi în Y
dar nu și invers (o mutare ireversibilă, o stradă cu sens unic, „pagina A
linkează către B"), o muchie spune din greșeală că drumul merge în ambele
direcții. Trebuie arc (graf orientat). Întreabă-te mereu: relația e
reciprocă? Dacă nu, e arc.
2. Inversezi ce e nod și ce e muchie. La un orar de zboruri, e tentant să faci
„zborul" nod. De obicei e greșit: orașele sunt nodurile, iar zborurile
sunt muchiile dintre ele — căci întrebarea e „cum ajung din orașul A în B",
iar drumul se construiește înlănțuind zboruri prin orașe. Regula practică: nodul e
locul în care te afli, muchia e trecerea dintr-un loc în altul. Dacă nu ești
sigur, scrie-ți întrebarea finală: subiectul ei („din ce ajung în ce") sunt
nodurile.
3. Îndeși în stare mai mult decât trebuie — și explodează numărul de noduri. La grafurile de stări, fiecare informație pe care o bagi în nod înmulțește numărul de noduri. Dacă starea reține și lucruri care nu influențează mutările viitoare (de exemplu tot istoricul mutărilor, nu doar configurația curentă), graful devine uriaș și nu mai încape nici în memorie, nici în timp. Regula: starea = minimul de informație de care depinde ce poți face în continuare — nimic în plus.