Modul 03 — Grafuri neorientate · Clasa a XI-a Fable

Graful viu — atinge un nod

6 elevi, 6 prietenii. Click pe orice nod: vecinii se aprind albastru, iar gradul se calculează sub ochii tăi.

click pe un nod 👆 — de exemplu, nodul 6…

Definiția formală

G = (V, E): V = mulțimea NODURILOR (vârfurilor), E = mulțimea MUCHIILOR — perechi neordonate [x, y]. Muchia [1,2] și [2,1] sunt UNA singură: prietenia nu are sens de mers. Fără bucle ([x,x]) și fără muchii duplicate — convenția de liceu.

Vocabularul de bază

Adiacente = două noduri unite de o muchie · incidentă = muchia „se atinge" de nod · gradul d(x) = câte muchii pleacă din x · nod izolat = grad 0 (nodul 6!) · nod terminal = grad 1.

Teorema mâinilor date: suma TUTUROR gradelor = 2·m (fiecare muchie numără la ambele capete). În graful nostru: 2+3+3+2+2+0 = 12 = 2·6 ✔. Consecință de BAC: numărul nodurilor de grad impar e mereu PAR.

Lanțuri și cicluri — plimbări prin graf

Un lanț e o plimbare pe muchii. Scrie un șir de noduri (ex: 1 2 4 5) și verificatorul îl judecă — cu desen.

șir =

Dicționarul plimbărilor: lanț = șir de noduri cu muchie între oricare două consecutive · elementar = nu repetă NODURI · simplu = nu repetă MUCHII (noduri poate) · ciclu = lanț simplu care se întoarce de unde a plecat · ciclu elementar = doar capetele coincid. La orientate (Modulul 04) aceleași idei se vor numi drum și circuit.

Cum ține calculatorul graful minte

Același graf, trei haine. Comută între ele — toate sunt generate din aceeași listă de muchii.

1// C++: citirea matricei de adiacență

2int a[101][101], n, m;

3cin >> n >> m;

4for (int i = 1; i <= m; i++) {

5 int x, y; cin >> x >> y;

6 a[x][y] = a[y][x] = 1; // SIMETRIC!

8// gradul lui x: suma liniei x

1# Python: liste de adiacență cu dict (X·M08!)

2g = {i: [] for i in range(1, n + 1)}

3for x, y in muchii:

4 g[x].append(y)

5 g[y].append(x)

7grad = len(g[x]) # gradul, gratis

Care, când? Matricea: răspunde INSTANT la „există muchia [x,y]?", dar ocupă n² celule — bună la grafuri dese. Listele: parcurgi DOAR vecinii reali — bune la grafuri rare (rețeaua aeriană din programă: mii de aeroporturi, puține rute). Alegerea reprezentării E o decizie de eficiență — o vei argumenta la evaluări.

Fișa de sinteză

Graful neorientat, condensat.

G = (V, E): noduri + muchii neordonate [x,y]; fără bucle, fără duplicate (convenția de liceu).

Gradul d(x) = muchiile incidente; Σd(x) = 2m → numărul nodurilor de grad impar e PAR.

Plimbări: lanț (muchii consecutive) · elementar (noduri unice) · simplu (muchii unice) · ciclu (simplu, închis).

Matricea de adiacență: a[x][y] = a[y][x] = 1 — SIMETRICĂ; gradul = suma liniei; diagonala = 0.

Listele de adiacență: pentru fiecare nod, vecinii lui; grad = lungimea listei; ideale la grafuri rare.

Numărul maxim de muchii: n·(n−1)/2 — când TOATE perechile sunt unite (graf complet, revelat în M06).

Exersează: pe pbinfo.ro, categoria „Grafuri neorientate" — grade, verificări de lanț, construirea matricei din muchii.