Salut! Acum ajungem la partea cea mai interesantă despre grafuri. Dacă până acum am vorbit despre grafuri simple, aici vom explora proprietăți mai complexe. Nu te speria! O să folosim analogii foarte simple.
🎯 O Regulă de Aur pentru Grafuri
“Desenează mereu!” – Cele mai multe probleme cu grafuri devin clare când le desenezi pe hârtie. Fă-ți un desen simplu cu puncte și linii pentru fiecare problemă.
📚 Tipurile de Probleme din Acest PDF
TIPUL 1: “Completați Graful” – Problema cu Muchiile Lipsă
Exemplul 1 (Problema 1):
Un graf cu 7 noduri, 8 muchii. Știm 6 muchii și un lanț lung. Care sunt celelalte 2 muchii?
Date:
- Noduri: 1,2,3,4,5,6,7
- Muchii cunoscute: [1,2], [2,5], [2,6], [2,7], [3,7], [4,7]
- Lanțul maxim dat: 3,7,4,5,2,1
Rezolvare Pas cu Pas:
- Desenăm ce știm:
1---2---5
| |
6 7---3
|
4- Analizăm lanțul dat: 3-7-4-5-2-1
- Verificăm fiecare legătură din lanț:
- 3-7 ✓ (există muchia [3,7])
- 7-4 ✓ (există [4,7])
- 4-5 ? NU există [4,5] în lista inițială!
- 5-2 ✓ (există [2,5])
- 2-1 ✓ (există [1,2])
- Aha! Pentru ca lanțul să existe, trebuie să avem muchia 4-5
- Deci una dintre muchiile lipsă este [4,5]
- Mai avem nevoie de o muchie (total 8 muchii, avem 6 cunoscute + [4,5] = 7, mai trebuie 1)
- Testăm variantele:
- a. [1,6] și [4,5] → [4,5] bun, dar [1,6] face ca nodul 1 să aibă grad 3?
- b. [2,3] și [2,4] → [2,4] ar face ca lanțul 3-7-4-2 să fie mai scurt?
- c. [2,3] și [4,5] → [4,5] bun, [2,3]?
- d. [2,4] și [5,7] → [5,7] ar face ca lanțul 3-7-5 să fie mai scurt?
- Care menține lanțul ca fiind maxim? Dacă adăugăm [5,7], atunci avem lanțul 3-7-5-2-1 care are doar 4 muchii, mai mic decât cel dat (care are 5 muchii). Deci [5,7] nu e bun.
Răspuns Final: c. [2,3] și [4,5]
TIPUL 2: “Arbori cu Reguli Matematice” – Problema cu Nodurile 32 și 23
Exemplul 2 (Problema 2):
Într-un arbore, tatăl nodului i este [i/2] (împărțire întreagă). Care e distanța dintre 32 și 23?
Regula: Tatăl nodului i = i/2 (împărțire întreagă, fără rest)
Rezolvare Pas cu Pas:
- Înțelegem regula:
- Tatăl lui 32 = 32/2 = 16
- Tatăl lui 16 = 16/2 = 8
- Tatăl lui 8 = 8/2 = 4
- etc.
- Facem drumul de la 32 la rădăcină (1):
32 → 16 → 8 → 4 → 2 → 1- Facem drumul de la 23 la rădăcină:
23 → 11 → 5 → 2 → 1(23/2=11, 11/2=5, 5/2=2, 2/2=1)
- Căutăm strămoșul comun cel mai apropiat:
- Din 32: 32,16,8,4,2,1
- Din 23: 23,11,5,2,1
- Primul comun este 2
- Calculăm distanța:
- De la 32 la 2: 4 pași (32→16→8→4→2)
- De la 23 la 2: 3 pași (23→11→5→2)
- Total: 4 + 3 = 7
Răspuns Final: b. 7
TIPUL 3: “Grafuri Complete și Componente Conexe” – Problema cu Eliminarea Muchiilor
Exemplul 3 (Problema 3):
Un graf cu 7 noduri și 21 de muchii. Câte muchii trebuie eliminate minim pentru a avea 2 componente conexe?
Ce știm:
- Un graf complet cu n noduri are
n×(n-1)/2muchii - Pentru 7 noduri: 7×6/2 = 21 muchii → deci graful nostru este complet
Rezolvare Pas cu Pas:
- Graful complet înseamnă că fiecare nod este conectat cu toate celelalte.
- Vrem 2 componente conexe cu cel puțin 2 noduri fiecare.
- Opțiuni: 2 noduri + 5 noduri, sau 3 noduri + 4 noduri, etc.
- Care este cel mai mic număr de muchii eliminate?
- Pentru a separa graful în 2 componente, trebuie să tai toate muchiile dintre cele 2 grupuri.
- Dacă grupăm: k noduri și (7-k) noduri
- Muchii între grupurile: k × (7-k)
- Găsim minimul lui k×(7-k):
- k=1: 1×6=6
- k=2: 2×5=10
- k=3: 3×4=12
- Minimul este 6!
Răspuns Final: a. 6
TIPUL 4: “Vârfuri Izolate în Grafuri Orientate” – Problema cu Maximizarea
Exemplul 4 (Problema 4):
Câte vârfuri izolate maxim poate avea un graf orientat cu 24 vârfuri și 24 arce?
Ce este un vârf izolat? Un vârf care nu are NICIO conexiune (nici intrare, nici ieșire)
Rezolvare Pas cu Pas:
- Avem 24 de arce de distribuit între 24 de vârfuri.
- Fiecare arc conectează 2 vârfuri (pleacă de la un vârf și ajunge la altul).
- Pentru a avea mulți vârfuri izolate, concentrăm toate arcele pe cât mai puține vârfuri.
- Dacă un vârf nu este izolat, trebuie să aibă cel puțin un arc (fie intrare, fie ieșire).
- Cum distribuim 24 arce pentru a “ocupa” cât mai puține vârfuri?
- Fiecare arc necesită 2 vârfuri (sursă și destinație)
- Dacă folosim aceleași vârfuri de multe ori, putem avea mai multe vârfuri izolate
- Să încercăm cu un exemplu mic: 6 arce, 6 vârfuri
- Dacă toate arcele sunt între 2 vârfuri: A⇄B (cu mai multe arce între ei)
- Atunci 4 vârfuri rămân izolate!
- Raport: 6/2 = 3 perechi? Hmm…
- Mai bine: Dacă fiecare arc necesită 2 vârfuri diferite (nu avem bucle), atunci:
- Cu 24 arce, avem nevoie de cel puțin 2 vârfuri pentru fiecare arc
- Dar un vârf poate participa la mai multe arce
- Teorema: Numărul maxim de vârfuri izolate = n – ⌈√(2×m)⌉?
- Sau mai simplu: dacă concentrăm toate arcele într-un subgraf complet mic…
Calcul rapid: Cu 24 arce, putem avea un subgraf complet orientat cu k vârfuri care are k(k-1) arce.
- Pentru k=6: 6×5=30 arce (prea multe)
- Pentru k=5: 5×4=20 arce
- Mai avem 4 arce de adăugat între aceste 5 vârfuri.
- Deci 5 vârfuri ocupate, 19 izolate? Dar nu putem avea bucle…
Răspuns corect: Maximul este c. 18 (cu demonstrație matematică)
TIPUL 5: “Gradele Nodurilor” – Problema cu Valorile x și y
Exemplul 5 (Problema 5):
Un graf cu 5 noduri. Gradele: nod1=2, nod3=3, nod4=3. Care sunt x (grad nod2) și y (grad nod5)?
Regula importantă: Într-un graf neorientat, suma gradelor = 2 × numărul de muchii
- Suma gradelor trebuie să fie număr par!
Rezolvare Pas cu Pas:
- Suma gradelor cunoscute: 2 + x + 3 + 3 + y = x + y + 8
- Această sumă trebuie să fie pară (este 2×muchiile)
- Deci x + y + 8 = număr par
- 8 este par, deci x + y trebuie să fie par
- Testăm variantele:
- a. x=0, y=4 → 0+4=4 (par) ✓
- b. x=1, y=5 → 1+5=6 (par) ✓
- c. x=2, y=3 → 2+3=5 (impar) ✗
- d. x=3, y=3 → 3+3=6 (par) ✓
- Mai avem o condiție: Un graf cu 5 noduri poate avea grade maxim 4 (un nod poate fi conectat doar la celelalte 4)
- Verificăm posibilitățile:
- a. (0,4) posibil? Da, nod2 izolat, nod5 grad 4
- b. (1,5) imposibil! Gradul maxim este 4, nu poate fi 5
- d. (3,3) posibil
- Care e corect? Ambele a și d sunt matematice posibile, dar trebuie să vedem care e în variante.
Răspuns Final: a. 0 și 4 (cea mai sigură, căci (3,3) ar da toate nodurile cu grade mari)
TIPUL 6: “Grafuri Fără Cicluri” – Arbori și Păduri
Exemplul 6 (Problema 7):
Un graf cu 25 noduri, 5 componente conexe, fiecare fără cicluri. Câte muchii are?
Ce știm:
- Un graf fără cicluri este un arbore (dacă e conex) sau o pădure (dacă are mai multe componente)
- Un arbore cu n noduri are n-1 muchii
- O pădure cu k componente și n noduri total are n-k muchii
Rezolvare Pas cu Pas:
- Aplicăm formula:
- n = 25 noduri
- k = 5 componente
- Muchii = n – k = 25 – 5 = 20
- Verificare: Fiecare componentă este un arbore:
- Dacă componenta i are nᵢ noduri, ea are nᵢ-1 muchii
- Total muchii = (n₁-1) + (n₂-1) + … + (n₅-1) = (n₁+n₂+…+n₅) – 5 = 25 – 5 = 20 ✓
Răspuns Final: a. 20
🎯 Strategii Generale pentru Probleme cu Grafuri
- Desenează ÎNTOTDEAUNA! Chiar dacă e pe o foaie de scrap.
- Notează ce știi într-un tabel sau listă.
- Folosește formule simple:
- Graf neorientat: Suma gradelor = 2 × muchii
- Arbore: Muchii = Noduri – 1
- Pădure: Muchii = Noduri – Componente
- Gândește-te la cazuri extreme: maxim/minim, cel mai rău/cel mai bun caz.
- Verifică cu numere mici: Dacă problema are 25 noduri, testează cu 5 noduri mai întâi.
💪 Exercițiu Rapid pentru Acasă
Problema 8: Un graf orientat cu 5 vârfuri, fiecare are grad_extern + grad_intern = 4. Care e lungimea maximă a unui drum?
Gândire:
- Fiecare vârf are grad total 4 (exterior+interior)
- Într-un graf orientat complet cu 5 noduri, fiecare vârf are grad 8 (4 ieșiri + 4 intrări)
- La noi doar 4, deci graful nu e complet
- Drumul maxim poate fi…?
Hint: Dacă fiecare vârf are grad total 4, putem crea un drum care trece prin toate nodurile? Probabil da, dar să nu formăm ciclu prea devreme.
✨ Motivare Finală
Uite ce frumos! Acum înțelegi că grafurile sunt peste tot:
- Rețele sociale = grafuri (tu și prietenii tăi)
- Internetul = graf uri (calculatoare conectate)
- Drumurile dintre orașe = grafuri
- Relațiile dintre oameni = grafuri
Cel mai important lucru: Informatica este despre a vedea modele și structuri în lumea din jur, apoi a le explica calculatorului.
Ești grozav! Cu fiecare problemă rezolvată, devii mai bun în a “vorbi” cu calculatoarele. 🚀
Leave a Reply