Modul 04 — Grafuri orientate · Clasa a XI-a Fable

Arce și cele două grade — orașul cu sensuri unice

5 intersecții, 7 străzi cu sens unic. Click pe un nod: verde = arcele care INTRĂ, auriu = cele care IES.

click pe un nod 👆 — încearcă și nodul 5…

Arcul (x, y)

Pereche ORDONATĂ: x = extremitatea inițială, y = extremitatea finală. (1,2) ≠ (2,1) — pot exista amândouă (stradă cu două sensuri = două arce). y e SUCCESOR al lui x; x e PREDECESOR al lui y.

Gradele

d⁺(x) = gradul exterior — arcele care IES · d⁻(x) = gradul interior — arcele care INTRĂ. Σd⁺ = Σd⁻ = m (fiecare arc iese o dată și intră o dată). d⁺ = 0 → „fundătură" a rețelei; d⁻ = 0 → nimeni nu ajunge la el.

Drumuri și circuite — plimbări pe sens

Același verificator ca la lanțuri (M03), dar acum săgețile trebuie respectate. Încearcă și șirul invers!

șir =

Traducerea completă: lanț → drum · ciclu → circuit · aceleași adjective (elementar = noduri unice, simplu = arce unice). Diferența unică: fiecare pas merge PE SENSUL arcului. De-asta 1→2→4→5 merge, dar 5→4→2→1 nu!

Reprezentările — simetria a dispărut

Aceleași trei haine ca la M03, plus una nouă: listele de predecesori.

1// C++: citirea — a[x][y] = 1 DOAR pe sens

2cin >> x >> y; a[x][y] = 1; // FĂRĂ a[y][x]!

3// d+(i) = suma LINIEI i · d-(i) = suma COLOANEI i

Subgraf vs graf parțial — două feluri de a tăia

Valabile la ORICE graf (și neorientat!). Apasă și privește ce dispare:

alege o tăietură 👆

Regula de memorat: SUBgraf = scoți NODURI (și, obligatoriu, toate arcele lor — un arc fără capăt nu există!) · graf PARȚIAL = păstrezi TOATE nodurile, scoți doar arce/muchii. La BAC: subgraful „moștenește" arcele rămase între nodurile păstrate.

Neorientat vs orientat — tabelul-oglindă

Tot modulul 03 și 04, într-o singură privire.

Concept	Neorientat (M03)	Orientat (M04)
legătura	muchie [x,y] — neordonată	arc (x,y) — ordonată
gradul	d(x), Σd = 2m	d⁺(x) și d⁻(x), Σd⁺ = Σd⁻ = m
plimbarea	lanț / ciclu	drum / circuit
matricea	simetrică	NEsimetrică, în general
vecinii	liste de adiacență	liste de succesori / predecesori
nr. maxim de legături	n·(n−1)/2	n·(n−1)

Fișa de sinteză

Graful orientat, condensat.

Arcul (x, y) e ordonat: x inițial → y final; (x,y) ≠ (y,x). y = succesor, x = predecesor.

Gradele: d⁺ = ies, d⁻ = intră; Σd⁺ = Σd⁻ = m; d⁺ = 0 → fundătură.

Drum / circuit = lanț / ciclu care respectă sensurile; aceleași adjective (elementar, simplu).

Matricea: a[x][y] = 1 doar pe sens → d⁺(i) = suma liniei, d⁻(i) = suma coloanei.

Subgraf = tai noduri (cu arcele lor) · graf parțial = tai doar arce, nodurile rămân toate.

Maxim n·(n−1) arce — dublul neorientatului, căci fiecare pereche are două sensuri posibile.

Urmează motorul întregii Faze 2: parcurgerile BFS (cu coada!) și DFS (cu stiva!) — cum vizitezi sistematic o rețea întreagă, pornind dintr-un singur nod.

Când sensul contează