Introduction à la théorie des graphes

Pr. EL HADIQ Zouhair

CPGE 2ᵉ année — MP / PSI · Informatique

1 / 16

Qu'est-ce qu'un graphe ?DÉFINITION

Un graphe $G = (S, A)$ modélise des objets et leurs liens :

$S$ : ensemble fini de sommets ;
$A$ : ensemble de liens — arêtes (non orienté) ou arcs (orienté).

Exemples : réseaux routiers, réseaux sociaux, pages web, labyrinthes…

Graphes simples. Au programme : ni boucle, ni multi-arête.

2 / 16

Orienté ou non orienté ?VOCABULAIRE

Notion	Non orienté	Orienté
Lien	arête {u, v}	arc (u, v)
Sens	aucun (symétrique)	de u vers v
Suite de sommets	chaîne	chemin
Boucle fermée	cycle	circuit

Ordre du graphe : nombre de sommets $n = |S|$.
$m = |A|$ : nombre d'arêtes / d'arcs.

3 / 16

Degré d'un sommetVOCABULAIRE

Non orienté : $\deg(u)$ = nombre d'arêtes incidentes à $u$ (= nombre de voisins).
Orienté : degré entrant $d^{-}(u)$ et degré sortant $d^{+}(u)$.

Lemme des poignées de main. $\displaystyle\sum_{u\in S}\deg(u) = 2m$ : chaque arête compte 1 pour chacune de ses deux extrémités.

4 / 16

Chemins, cycles, connexitéVOCABULAIRE

Une chaîne/chemin $s_0, s_1, \dots, s_k$ : sommets consécutifs reliés. Longueur = $k$.
Cycle/circuit : revient au départ ($s_0 = s_k$) sans réutiliser de lien.
Connexe : il existe une chaîne entre toute paire de sommets.

Test. Un graphe non orienté est connexe ⟺ un parcours depuis un seul sommet atteint tous les sommets.

5 / 16

Matrice d'adjacenceREPRÉSENTATION

$M[i][j] = 1$ s'il existe un arc/arête $i \to j$, sinon $0$.

Non orienté ⟹ matrice symétrique.
Test d'arc en $O(1)$, voisins en $O(n)$.
Mémoire $O(n^2)$ — bon pour graphes denses.

0 1 2 3 0 [ 0 1 1 0 ] 1 [ 1 0 1 0 ] 2 [ 1 1 0 1 ] 3 [ 0 0 1 0 ]

6 / 16

Listes d'adjacenceREPRÉSENTATION

# liste de listes # dictionnaire G = [[1, 2], G = {'A': ['B','C'], [0, 2], 'B': ['A','C'], [0, 1, 3], 'C': ['A','B','D'], [2]] 'D': ['C']}

Mémoire $O(n + m)$ — idéal pour graphes creux.
Voisins en $O(\deg u)$, test d'arc en $O(\deg u)$.

7 / 16

Manipulations de basePYTHON

def ajouter_arete(G, u, v): if v not in G[u]: G[u].append(v) G[v].append(u) # non orienté def voisins_depuis_matrice(M, u): return [j for j in range(len(M)) if M[u][j] == 1]

Opérations clés : ajout / suppression / test d'un arc, liste des voisins.

8 / 16

Parcours en largeur — BFSALGORITHME

Explore par cercles concentriques : départ, puis voisins, puis voisins des voisins… avec une file (FIFO).

deque ! list.pop(0) est en $O(n)$. On utilise collections.deque ($O(1)$).

Complexité $O(n + m)$. Donne le plus court chemin non pondéré.

from collections import deque def bfs(G, s): vus = {s} f = deque([s]) while f: u = f.popleft() for v in G[u]: if v not in vus: vus.add(v) f.append(v)

9 / 16

Parcours en profondeur — DFSALGORITHME

Explore le plus loin possible avant de revenir en arrière (backtracking). Naturellement récursif, ou itératif avec une pile (LIFO).

Complexité $O(n + m)$. Diffère du BFS par l'ordre de visite.

def dfs(G, u, vus=None): if vus is None: vus = set() vus.add(u) for v in G[u]: if v not in vus: dfs(G, v, vus)

10 / 16

Application : connexité & cycleAPPLICATION

def est_connexe(G): depart = next(iter(G)) return len(set(bfs(G, depart))) == len(G)

Cycle (non orienté). En DFS, un voisin déjà vu différent du père ⟹ il existe un cycle. (Cas orienté : sommet « en cours » ⟹ circuit.)

11 / 16

Graphes pondérésPONDÉRATION

Chaque arc/arête porte une étiquette numérique (poids) : distance, temps, prix…

G = {'A': [('B', 4), ('C', 1)], 'B': [('D', 1)], 'C': [('B', 2), ('D', 5)], 'D': []}

Problème du plus court chemin : minimiser la somme des poids.

12 / 16

Algorithme de DijkstraALGORITHME

Plus courts chemins depuis une source, poids positifs. À chaque étape : figer le sommet de plus petite distance, puis relâcher ses arcs.

File de priorité (heapq) ⟹ $O((n+m)\log n)$.

Poids négatifs : échoue ! Un sommet figé pourrait encore être amélioré.

import heapq def dijkstra(G, src): d = {u:float('inf') for u in G} d[src] = 0 t = [(0, src)] while t: du,u = heapq.heappop(t) for v,w in G[u]: if d[u]+w < d[v]: d[v] = d[u]+w heapq.heappush(t,(d[v],v)) return d

13 / 16

A* et Floyd-WarshallAPPLICATIONS

A* : variante heuristique de Dijkstra. Priorité $f(v) = g(v) + h(v)$ avec $h$ = estimation du reste. Heuristique admissible ⟹ optimal, moins de sommets explorés.
Floyd-Warshall : plus courts chemins toutes paires par programmation dynamique, $O(n^3)$.
Coloration de graphe : deux voisins jamais de la même couleur.

14 / 16

Complexités à retenirSYNTHÈSE

Opération / algo	Matrice	Listes d'adj.
Mémoire	$O(n^2)$	$O(n+m)$
Test d'arc	$O(1)$	$O(\deg u)$
Voisins	$O(n)$	$O(\deg u)$
BFS / DFS	$O(n^2)$	$O(n+m)$
Dijkstra (tas)	$O((n+m)\log n)$
Floyd-Warshall	$O(n^3)$

15 / 16

RécapitulatifBILAN

Graphe $G=(S,A)$ : arêtes (non orienté) ou arcs (orienté), simples.
Vocabulaire : ordre, degré, chaîne/chemin, cycle/circuit, connexité.
Représentations : matrice ($O(n^2)$) vs listes d'adjacence ($O(n+m)$).
BFS (file) & DFS (pile) en $O(n+m)$ ⟹ connexité, cycle.
Dijkstra pour le plus court chemin pondéré positif ; A*, Floyd-Warshall.

16 / 16