InfoBook.ro ← Harta anului
Modul 06 · Matricea drumurilor & grafurile speciale
Modul 06 · Conținuturi 1.1 + 2.2 · ★ BAC

Cine poate ajunge la cine?

Matricea de adiacență spune „există arc DIRECT". Întrebarea mai adâncă e: există DRUM — pe oricâte arce? Algoritmul Roy-Floyd o completează sistematic, iar din răspuns se citesc tare conexitatea și marile familii de grafuri speciale.

🎯 Obiectiv 1Construiești matricea drumurilor cu Roy-Floyd, nod intermediar cu nod intermediar.
🎯 Obiectiv 2Verifici tare conexitatea și găsești componentele tare conexe.
🎯 Obiectiv 3Recunoști graful complet, hamiltonian și eulerian — cu teoremele lor.
1

Roy-Floyd — matricea drumurilor, pas cu pas

Ideea genială: dai voie, pe rând, câte unui nod k să fie „escală". Dacă ajung la k și de la k mai departe — am drum. Auriu = celulă nou-descoperită.

1for (int k = 1; k <= n; k++) // escala!
2 for (int i = 1; i <= n; i++)
3 for (int j = 1; j <= n; j++)
4 if (d[i][k] && d[k][j])
5 d[i][j] = 1;
pornim de la matricea de adiacență — apasă Pas 👆
Ordinea buclelor e sfântă: k (escala) e bucla EXTERIOARĂ. La BAC se dă des inversată — atunci rezultatul e greșit! Notă din programă: în cărți algoritmul apare și ca Floyd-Warshall.
Citirea diagonalei: d[i][i] devine 1 doar dacă există un CIRCUIT care trece prin i — la noi, 1→2→3→1 aprinde d[1][1], d[2][2], d[3][3]. Nodul 4 rămâne cu linia goală: din el nu pleacă nimic.
2

Tare conexitatea — dus ȘI întors

Un graf orientat e tare conex dacă între ORICARE două noduri există drum în ambele sensuri. Matricea drumurilor răspunde instant.

i și j sunt în aceeași componentă tare conexă ⇔ d[i][j] = 1 ȘI d[j][i] = 1 👆
Diagrama de proces din programă: etapele unei activități cu dependențe = graf orientat; dacă apare o componentă tare conexă cu peste un nod, ai un CIRCUIT de dependențe — activitatea se blochează în cerc. Validarea diagramei = exact acest test.
3

Galeria grafurilor speciale

Trei familii care apar obsesiv la BAC — fiecare cu „legitimația" ei.

Graful COMPLET — Kn

Oricare două noduri sunt adiacente: exact n·(n−1)/2 muchii, toate gradele n−1. Grupul în care toți sunt prieteni cu toți. K₄ are 6 muchii, K₁₀₀ are 4950.

Graful HAMILTONIAN

Are un ciclu hamiltonian: trece prin fiecare NOD exact o dată și revine. Croaziera / comis-voiajorul din M02 — acum cu nume! Condiție suficientă: dacă toate gradele ≥ n/2, graful e hamiltonian. Găsirea ciclului? Backtracking — nu există formulă rapidă.

Graful EULERIAN — testul podurilor

Are un ciclu eulerian: trece prin fiecare MUCHIE exact o dată și revine. Problema care a inventat teoria grafurilor: podurile din Königsberg (1736). Teorema lui Euler: un graf conex e eulerian ⇔ TOATE gradele sunt PARE. Testează:

alege un graf — gradele apar lângă noduri: verde = par, roșu = impar 👆
Cum găsești efectiv ciclul? Cu un DFS adaptat (programa o cere ca „repere"): te plimbi ștergând muchiile folosite; când te blochezi, nodul se închide și se adaugă în ciclu. Memorezi: eulerian = muchiile, hamiltonian = nodurile!
4

Verificare rapidă

Cinci întrebări — în stil BAC.

5

Fișa de sinteză

Drumurile și grafurile speciale, condensate.

Matricea drumurilor: d[i][j] = 1 ⇔ există drum i→j; se obține din adiacență cu Roy-Floyd (Floyd-Warshall).
Roy-Floyd: trei bucle, k (escala) NEAPĂRAT exterioară — d[i][j] |= d[i][k] && d[k][j]; O(n³).
d[i][i] = 1 ⇔ există circuit prin i — diagonala nu se pune din oficiu!
Tare conex: d[i][j] = d[j][i] = 1 pentru orice pereche; componentele = clasele „dus-întors".
Complet: n(n−1)/2 muchii, grade n−1 · Hamiltonian: ciclu prin toate NODURILE (Backtracking; suficient: grade ≥ n/2).
Eulerian: ciclu prin toate MUCHIILE ⇔ conex + toate gradele PARE (Euler, 1736); găsit cu DFS adaptat.
Urmează: punem NUMERE pe arce — graful ponderat și matricea costurilor — și îl lăsăm pe Dijkstra să găsească drumul cel mai ieftin.
← anteriorModul 05 · BFS & DFS urmează →Modul 07 · Dijkstra — drumul de cost minim