Un graphe formalise des objets et les relations pertinentes pour une question. Dans les conventions de ce chapitre, un graphe simple non orienté est fini, sans boucle ni arêtes multiples. Le dessin peut changer sans changer le graphe : seuls les sommets et les arêtes comptent.
Repères & formules
Définitions · règles · complexité
01
G = (V, E) · n = |V| (ordre) · m = |E| (taille)
02
G simple non orienté : E ⊆ {{u, v} : u, v ∈ V, u ≠ v}
03
u et v adjacents ⇔ uv ∈ E
04
N(v) = {u ∈ V : uv ∈ E} · N[v] = N(v) ∪ {v}
05
H = (W, F) ⊆ G ⇔ W ⊆ V et F ⊆ E
06
G[W] : sous-graphe induit qui conserve toutes les arêtes entre les sommets de W
02
Notion 1.2
Représentations et complexité
Une liste d’arêtes, des listes de voisins ou une matrice décrivent le même objet. Le choix dépend de la mémoire disponible et des opérations fréquentes.
Listes de voisins : espace Θ(n + m) · tester uv : O(d(u)) · lister N(u) : Θ(d(u))
03
Matrice A : espace Θ(n²) · tester uv : O(1) · lister N(u) : Θ(n) · lister E : Θ(n²)
04
G simple non orienté : A[u,v] = A[v,u] et A[u,u] = 0
05
Graphe simple : m ≤ n(n − 1)/2
06
f=O(g) ⇔ ∃C,n₀>0, ∀n≥n₀ : f(n)≤Cg(n)
07
f=Ω(g) ⇔ ∃c,n₀>0, ∀n≥n₀ : cg(n)≤f(n)
08
f=Θ(g) ⇔ ∃c,C,n₀>0, ∀n≥n₀ : cg(n)≤f(n)≤Cg(n)
03
Notion 1.3
Degrés et double comptage
Le degré d’un sommet est son nombre de voisins. Le lemme des poignées de main compte les incidences sommet-arête de deux façons : par sommet, puis par arête.
Graphe complet Kₙ : d(v) = n − 1 et m = n(n − 1)/2
04
Notion 1.4
Connexité et algorithme Composantes
Un graphe est connexe si chaque paire de sommets est reliée par un chemin. Les composantes connexes sont les sous-ensembles connexes maximaux et forment une partition des sommets.
Repères & formules
Définitions · règles · complexité
01
V = C₁ ⊎ C₂ ⊎ … ⊎ Cₖ
02
Avec exactement k composantes : m ≤ (n − k + 1)(n − k)/2
03
comp[x] = comp[y] ⇔ x et y sont dans la même composante
04
Composantes : initialiser comp[x] ← x ; pour chaque xy, fusionner les étiquettes si elles diffèrent
05
Temps : O(m + n²) · espace auxiliaire : Θ(n) · au plus n − 1 fusions
