Synthèse

Cette synthèse suit les grands chapitres des notes du professeur, mais ne développe que la matière effectivement vue au cours ou nécessaire pour les TP déjà actifs. L’objectif est d’avoir une structure stable pendant tout le quadrimestre, sans ajouter des blocs isolés séance après séance.

Architecture du cours

Chapitre	Thème	État
1	Graphes connexes, eulériens et bipartis	Actif
2	Plus courts chemins	Actif
3	Arbres et connectivité	Actif — CM3
4	Graphes hamiltoniens	À venir
5	Couplages et couvertures	À venir
6	Colorations, indépendants, cliques et Ramsey	À venir
7	Graphes planaires	À venir
8	Flots et coupes	À venir
9	Algèbre linéaire en théorie des graphes	À venir
10	Complexité algorithmique : P, NP et NP-complétude	À venir

Les chapitres 4 à 10 seront remplis lorsque la matière correspondante aura réellement été vue.

---

1. Graphes connexes, eulériens et bipartis

1.1 Graphe, sommets, arêtes et degré

Un graphe est un triplet

$$G=(V,E,\varphi),$$

où :

• $V$ est l’ensemble fini des sommets ;
• $E$ est l’ensemble fini des arêtes ;
• $\varphi$ est la fonction d’incidence qui associe à chaque arête son ou ses sommets incidents.

Deux sommets incidents à une même arête sont adjacents.

Une boucle est une arête incidente deux fois au même sommet. Deux arêtes sont multiples si elles relient les mêmes sommets.

Le degré d’un sommet $v$, noté $\deg(v)$, est le nombre d’incidences d’arêtes en $v$. Une boucle compte donc pour deux.

Un graphe est simple s’il ne possède ni boucle ni arêtes multiples. Dans un graphe simple à $n$ sommets,

$$0\le \deg(v)\le n-1.$$

Un sous-graphe de $G$ est obtenu en ne gardant qu’une partie des sommets et/ou des arêtes. Le sous-graphe induit par $V'\subseteq V$ conserve les sommets de $V'$ et toutes les arêtes de $G$ dont les deux extrémités sont dans $V'$.

Isomorphisme

Deux graphes sont isomorphes s’ils ne diffèrent que par le nom donné aux sommets et aux arêtes : il existe des bijections qui préservent l’incidence, donc l’adjacence.

Conséquence pratique : toute propriété intrinsèque du graphe est conservée par isomorphisme. Par exemple, deux graphes ayant un nombre différent de triangles ne peuvent pas être isomorphes.

La réciproque est fausse pour beaucoup d’invariants : avoir la même liste de degrés ne suffit pas à garantir l’isomorphisme.

1.2 Théorème des poignées de main et degrés

Théorème des poignées de main

Pour tout graphe non orienté fini,

$$\sum_{v\in V}\deg(v)=2|E|.$$

Chaque arête contribue exactement deux incidences à la somme des degrés.

Deux conséquences immédiates :

$$\bar d = \frac{1}{|V|}\sum_{v\in V}\deg(v) = \frac{2|E|}{|V|}$$

pour le degré moyen, et le nombre de sommets de degré impair est toujours pair.

Dans un graphe simple à $n$ sommets,

$$|E|\le \binom n2=\frac{n(n-1)}2.$$

Réflexes sur une liste de degrés

Pour une liste $d_1,\ldots,d_n$, commencer par vérifier

$$0\le d_i\le n-1 \qquad\text{et}\qquad \sum_i d_i \text{ est pair}.$$

Ce sont des conditions nécessaires, pas suffisantes.

Autre raisonnement utile : si un sommet est de degré $n-1$, il est relié à tous les autres. On peut alors le retirer et diminuer de $1$ les degrés restants.

Enfin, dans un graphe simple à $n\ge2$ sommets, les degrés $0$ et $n-1$ ne peuvent pas apparaître simultanément. Il n’y a donc qu’au plus $n-1$ valeurs de degré possibles pour $n$ sommets : deux sommets ont nécessairement le même degré.

1.3 Parcours, chemins, cycles et distance

Un parcours est une suite alternée

$$v_0,e_0,v_1,e_1,\ldots,e_{k-1},v_k$$

telle que chaque arête $e_i$ relie $v_i$ à $v_{i+1}$.

Sa longueur est son nombre d’arêtes, ici $k$.

Un parcours est fermé si

$$v_0=v_k.$$

Un chemin est un parcours dont les sommets sont distincts, sauf éventuellement les deux extrémités dans le cas fermé. Un cycle est un chemin fermé.

Le support actuel emploie surtout les termes parcours fermé et cycle. Le terme circuit n’est pas défini séparément dans les slides vues : s’il apparaît dans un énoncé, il faut vérifier la convention utilisée.

La distance entre deux sommets dans un graphe non pondéré est

$$d(u,v) = \min\{\text{nombre d'arêtes d'un parcours de }u\text{ à }v\}.$$

Un parcours de longueur minimale est toujours un chemin : si un sommet était répété, on pourrait supprimer le détour entre deux occurrences.

1.4 Connexité et composantes connexes

Un graphe non orienté est connexe si toute paire de sommets peut être reliée par un parcours.

Une composante connexe est un sous-graphe connexe maximal.

Pour un graphe simple connexe à $n$ sommets,

$$n-1\le |E|\le \binom n2.$$

La borne inférieure exprime qu’il faut au moins $n-1$ arêtes pour relier $n$ sommets. La borne supérieure correspond au graphe complet.

Plus généralement, si un graphe possède $n$ sommets, $m$ arêtes et $c$ composantes connexes,

$$m\ge n-c \qquad\Longleftrightarrow\qquad c\ge n-m.$$

Pour maximiser le nombre d’arêtes tout en gardant un graphe simple non connexe, on prend un graphe complet sur $n-1$ sommets et un sommet isolé. Ainsi,

$$|E| \le \binom{n-1}{2} = \frac{(n-1)(n-2)}2.$$

Donc un graphe simple possédant strictement plus de

$$\frac{(n-1)(n-2)}2$$

arêtes est nécessairement connexe.

1.5 Parcours eulériens

Un parcours eulérien utilise chaque arête du graphe exactement une fois.

Un graphe est eulérien s’il possède un parcours eulérien fermé.

Théorème d'Euler

Un graphe connexe est eulérien si et seulement si tous ses sommets sont de degré pair :

$$G\text{ connexe et eulérien} \quad\Longleftrightarrow\quad \deg(v)\text{ pair pour tout }v\in V.$$

Pourquoi la condition est nécessaire

Dans un parcours eulérien fermé, chaque fois que l’on arrive en un sommet par une arête, on doit en repartir par une autre. Les arêtes incidentes au sommet se mettent donc par paires : son degré est pair.

Sens difficile : construction de Hierholzer

Preuve constructive vue au tableau

Supposons le graphe connexe et tous ses degrés pairs.

1. Partir d’un sommet arbitraire $u_0$.
2. Avancer en utilisant uniquement des arêtes encore non visitées.
3. On ne peut pas rester bloqué dans un sommet différent de $u_0$ : si l’on vient d’y entrer, un nombre impair d’arêtes incidentes a été utilisé ; le degré total étant pair, il reste au moins une arête pour en ressortir.
4. Le parcours finit donc par revenir en $u_0$. On obtient un parcours fermé $P$.
5. Si toutes les arêtes ont été utilisées, $P$ est eulérien.
6. Sinon, la connexité garantit qu’il existe un sommet $u_1$ de $P$ incident à une arête non encore utilisée.
7. Depuis $u_1$, construire de la même manière un nouveau parcours fermé $P'$ avec les arêtes restantes.
8. Insérer $P'$ dans $P$ au sommet $u_1$ et recommencer.

La parité garantit que chaque parcours partiel se referme. La connexité garantit qu’on peut continuer tant qu’il reste des arêtes.

Cette preuve donne directement l’algorithme de Hierholzer. Sa complexité annoncée au cours est

$$O(|E|).$$

Parcours eulérien ouvert

Existence d'un parcours eulérien

Un graphe connexe possède un parcours eulérien si et seulement si le nombre de sommets de degré impair vaut 0 ou 2.

• $0$ sommet impair : le parcours peut être fermé ;
• $2$ sommets impairs : ils sont les deux extrémités du parcours ouvert.

Dans le cas de deux sommets impairs $u$ et $v$, on peut ajouter artificiellement l’arête $uv$, appliquer Euler au graphe obtenu puis supprimer cette arête du parcours fermé.

Algorithme de Fleury

Fleury construit directement un parcours eulérien. À chaque étape, il choisit une arête non encore visitée qui n’est pas un pont du graphe restant, sauf si aucun autre choix n’est possible.

Un pont est une arête dont la suppression augmente le nombre de composantes connexes.

L’intuition est simple : ne pas couper trop tôt l’accès à une partie du graphe contenant encore des arêtes à visiter.

Dans la version présentée au cours,

$$\text{Hierholzer : }O(|E|) \qquad\text{et}\qquad \text{Fleury : }O(|E|^2).$$

Reconnaître un problème eulérien

Penser immédiatement à Euler lorsque l’énoncé demande de :

• parcourir chaque arête exactement une fois ;
• tracer une figure sans lever le crayon et sans repasser sur un segment ;
• construire un parcours couvrant toutes les arêtes.

Le premier contrôle est alors : connexité + nombre de sommets de degré impair.

1.6 Représentations matricielles

Pour des sommets $v_1,\ldots,v_n$, la matrice d’adjacence $A$ est la matrice carrée dont l’entrée $A_{ij}$ est le nombre d’arêtes entre $v_i$ et $v_j$.

Pour des arêtes $e_1,\ldots,e_m$, la matrice d’incidence $M$ est la matrice $n\times m$ dont l’entrée $M_{ij}$ vaut le nombre de fois que $v_i$ est incident à $e_j$.

Dans la matrice d’incidence :

• la somme d’une ligne donne le degré du sommet correspondant ;
• la somme d’une colonne vaut $2$.

C’est une manière matricielle de retrouver le théorème des poignées de main.

Matrice d'adjacence et nombre de parcours

Pour tout entier $k\ge0$,

$$(A^k)_{ij} = \text{nombre de parcours de longueur }k \text{ de }v_i\text{ vers }v_j.$$

Ce résultat servira de modèle au chapitre 2 pour calculer les plus courts chemins avec le semi-anneau $(\min,+)$.

1.7 Graphes orientés et forte connexité

Dans un graphe orienté, une arête est un couple ordonné $(u,v)$ : son sens compte.

On distingue :

• $d^+(v)$ : degré sortant ;
• $d^-(v)$ : degré entrant.

Pour tout graphe orienté fini,

$$\sum_{v\in V} d^+(v) = \sum_{v\in V} d^-(v) = |E|.$$

Un graphe orienté est fortement connexe lorsqu’il existe un parcours dirigé de tout sommet vers tout autre.

Deux sommets sont dans la même composante fortement connexe s’ils sont mutuellement atteignables.

Pour tester la forte connexité à partir d’un sommet $s$, il suffit de vérifier :

1. que tous les sommets sont atteignables depuis $s$ ;
2. que $s$ est atteignable depuis tous les sommets.

La deuxième condition peut se tester en inversant toutes les arêtes puis en explorant à nouveau depuis $s$.

Dans un graphe orienté fortement connexe, la version dirigée du critère d’Euler est

$$d^+(v)=d^-(v) \qquad \text{pour tout }v.$$

1.8 Graphes bipartis

Un graphe est biparti s’il existe une partition

$$V=V_0\cup V_1, \qquad V_0\cap V_1=\varnothing,$$

telle que toute arête relie un sommet de $V_0$ à un sommet de $V_1$.

Caractérisation des graphes bipartis

Un graphe est biparti si et seulement si tous ses cycles sont de longueur paire.

Équivalemment :

$$G\text{ biparti} \quad\Longleftrightarrow\quad G\text{ ne contient aucun cycle impair}.$$

L’idée constructive de la réciproque est de choisir un sommet $v_0$ et de séparer les sommets selon la parité de leur distance à $v_0$ :

$$V_0=\{v:d(v,v_0)\text{ pair}\}, \qquad V_1=\{v:d(v,v_0)\text{ impair}\}.$$

Hypercube $Q_k$

Les sommets de $Q_k$ sont les $k$-uplets de $0$ et de $1$. Deux sommets sont adjacents s’ils diffèrent en exactement une coordonnée.

Chaque sommet possède exactement $k$ voisins :

$$\deg(v)=k.$$

Il y a $2^k$ sommets, donc

$$|E(Q_k)| = \frac{k2^k}{2} = k2^{k-1}.$$

Une bipartition naturelle sépare les sommets ayant un nombre pair de $1$ de ceux ayant un nombre impair de $1$.

1.9 Repères complémentaires déjà rencontrés

Tournois et rois

Un tournoi est une orientation du graphe complet $K_n$ : pour toute paire de sommets distincts $u,v$, exactement une des deux arêtes $u\to v$ ou $v\to u$ existe.

Un sommet $u$ est un roi si tout autre sommet est atteignable depuis $u$ en au plus deux arêtes dirigées.

Le résultat utilisé au TP est : un sommet de degré sortant maximum est un roi. La preuve se fait par contradiction : si un sommet $v$ n’était pas atteignable en au plus deux étapes depuis $u$, alors $v$ battrait $u$ et tous les voisins sortants de $u$, ce qui donnerait $d^+(v)>d^+(u)$.

Eulérien versus hamiltonien

Pour éviter une confusion fréquente :

Notion	Objet visité exactement une fois
Eulérien	les arêtes
Hamiltonien	les sommets

Un chemin hamiltonien passe par chaque sommet exactement une fois. Un cycle hamiltonien fait de même en revenant à son sommet de départ. Les théorèmes hamiltoniens appartiennent au chapitre 4 et ne sont pas encore matière active.

---

2. Les plus courts chemins

2.1 Graphes pondérés

Une fonction de poids

$$w:E\to\mathbb R$$

associe un poids à chaque arête. Un graphe muni d’une telle fonction est un graphe pondéré.

Le poids d’un parcours est la somme des poids de ses arêtes.

La distance pondérée entre $u$ et $v$ est

$$d(u,v) = \min\{\text{poids d'un chemin de }u\text{ à }v\}.$$

Dans un graphe dirigé, il faut garder en tête que

$$d(u,v) \neq d(v,u)$$

en général.

Plus court parcours et plus court chemin

Si tous les poids sont non négatifs, le plus court parcours et le plus court chemin entre deux sommets ont la même longueur.

Idée de preuve. Si un parcours minimal répète un sommet, il contient un cycle. Ce cycle a un poids $\ge0$, donc le supprimer ne peut pas augmenter le poids. En répétant l’opération, on obtient un chemin de même longueur minimale.

L’hypothèse

$$w(e)\ge0$$

est donc centrale.

2.2 Algorithme de Dijkstra

Problème

À partir d’une source $u_0$, calculer les distances minimales vers les autres sommets d’un graphe pondéré dont les poids sont non négatifs.

Idée

Dijkstra détermine progressivement les distances exactes. Il maintient un ensemble $S$ des sommets dont la distance est déjà définitivement connue et un label $\ell(v)$ pour les autres.

Initialisation

$$S=\{u_0\}, \qquad \ell(u_0)=0, \qquad \ell(v)=+\infty \text{ pour }v\ne u_0.$$

Relaxation

Quand $u'$ vient d’être ajouté à $S$, pour chaque $v\notin S$ :

$$\ell(v) \leftarrow \min\bigl( \ell(v), \ell(u')+w(u'v) \bigr).$$

Ensuite, choisir hors de $S$ un sommet $v_{\min}$ de label minimal et l’ajouter à $S$.

Invariant de Dijkstra

Après chaque mise à jour :

• pour $v\in S$,

$$\ell(v)=d(u_0,v),$$

et un plus court chemin vers $v$ reste dans $S$ ;

• pour $v\notin S$, $\ell(v)$ est la longueur du plus court chemin connu dont tous les sommets internes sont déjà dans $S$, donc

$$\ell(v)\ge d(u_0,v).$$

Cet invariant est le cœur de la preuve de correction : lorsqu’on choisit le sommet de label minimal hors de $S$, les poids non négatifs empêchent un détour futur par des sommets encore hors de $S$ d’améliorer sa distance.

Conditions, sortie et arrêt

Dijkstra fonctionne pour :

• un graphe dirigé ou non ;
• des poids

$$w(e)\ge0.$$

Il fournit les distances depuis une source. En mémorisant un prédécesseur lors des relaxations, on peut aussi reconstruire les chemins.

Si seule une cible $t$ nous intéresse, on peut arrêter lorsque $t$ entre dans $S$.

Si toutes les arêtes ont le même poids strictement positif, Dijkstra se réduit essentiellement à une recherche en largeur (BFS).

Complexité annoncée au cours

Les slides présentent un temps de l’ordre de

$$|E|,$$

ce qui est de l’ordre de

$$|V|^2$$

pour un graphe dense.

2.3 Graphe dirigé pondéré

Dijkstra ne dépend pas de la symétrie des arêtes. Il s’applique donc également aux graphes dirigés, à condition de respecter le sens des arêtes et de conserver l’hypothèse de poids non négatifs.

C’est le cadre naturel pour modéliser, par exemple, des routes à sens unique.

2.4 Plus courts chemins par calcul matriciel

On note $d_k(u,v)$ la longueur du plus court parcours de exactement $k$ arêtes de $u$ vers $v$.

On obtient la récurrence

$$d_{k+1}(u,v) = \min_x \bigl( d_k(u,x)+w(x,v) \bigr).$$

À comparer avec le comptage des parcours :

$$a_{k+1}(u,v) = \sum_x a_k(u,x)a(x,v).$$

La structure est la même, mais les deux opérations changent :

$$\sum \longrightarrow \min, \qquad \times \longrightarrow +.$$

2.5 Semi-anneau $(\min,+)$

Sur

$$\mathbb R_+\cup\{+\infty\},$$

on définit

$$a\oplus b=\min(a,b), \qquad a\otimes b=a+b.$$

Les éléments neutres sont :

$$+\infty \quad\text{pour }\oplus,$$

et

$$0 \quad\text{pour }\otimes.$$

Le produit matriciel associé devient

$$(A\otimes B)_{ij} = \min_k (A_{ik}+B_{kj}).$$

La matrice identité pour ce produit contient $0$ sur la diagonale et $+\infty$ ailleurs.

2.6 Puissances $(\min,+)$ et distances

Soit $A$ la matrice d’adjacence pondérée, avec

$$A_{ij}=+\infty$$

s’il n’existe pas d’arête de $i$ vers $j$.

Alors

$$A^{\otimes k}$$

contient les longueurs des plus courts parcours de exactement $k$ arêtes.

En introduisant l’identité $I$,

$$D_k=(I\oplus A)^{\otimes k}$$

contient les plus courts parcours de au plus $k$ arêtes.

Pour un graphe à $n$ sommets, les slides donnent

$$D_n=(I\oplus A)^{\otimes n}$$

comme matrice des plus courts chemins.

Par mises au carré successives, la complexité indiquée au cours est

$$O(n^3\log_2 n).$$

Le point conceptuel à retenir est l’analogie :

la multiplication matricielle classique compte les parcours ; la multiplication matricielle dans le semi-anneau $(\min,+)$ minimise leur poids.

---

3. Arbres et connectivité

Ce chapitre reprend les notions travaillées au CM3 : explorer un réseau, conserver la connexité avec le moins d’arêtes possible, optimiser le coût d’un arbre couvrant, puis mesurer sa résistance aux défaillances. Les derniers résultats (Menger et Harary) complètent la partie « connectivité » du support thématique.

3.1 Exploration : BFS et DFS

Problème. Depuis un sommet de départ $s$, découvrir les sommets accessibles et les arêtes permettant de les atteindre. Dans un graphe non connexe, un seul lancement n’explore que la composante de $s$.

On marque les sommets au moment de leur découverte pour éviter de les visiter plusieurs fois. Le choix de la structure de données détermine l’ordre d’exploration :

Exploration	Structure	Règle	Propriété utile
BFS (largeur)	File FIFO	Premier entré, premier sorti	Découvre les sommets par distance croissante en nombre d’arêtes
DFS (profondeur)	Pile LIFO ou récursion	Dernier entré, premier sorti	Explore une branche aussi loin que possible, puis revient en arrière

BFS donne les plus courts chemins d’un graphe non pondéré (ou dont les arêtes ont toutes un poids identique strictement positif). DFS ne garantit pas cela.

Invariant commun. Chaque sommet marqué est atteignable depuis $s$ ; un sommet n’est marqué qu’une fois. Tant qu’il reste un sommet accessible non marqué, une arête relie une partie déjà découverte à une partie non découverte et l’exploration peut progresser. À la fin, tous les sommets atteignables depuis $s$ ont été marqués.

Avec des listes d’adjacence, chaque sommet et chaque arête sont traités un nombre constant de fois :

$\boxed{O(|V|+|E|)}$

Pour calculer toutes les composantes connexes, on relance BFS ou DFS depuis un sommet non marqué jusqu’à ce que tous les sommets soient marqués.

Graphes orientés : forte connexité

Une exploration dirigée respecte le sens des arcs. Un graphe orienté est fortement connexe si, pour toute paire ordonnée de sommets $(u,v)$, il existe un chemin dirigé de $u$ vers $v$.

Pour tester la forte connexité, choisir $s$, puis :

1. Explorer depuis $s$ dans $G$ : tous les sommets doivent être atteignables depuis $s$.
2. Inverser tous les arcs pour obtenir le graphe transposé $G^\mathsf T$ et explorer depuis $s$ : tous les sommets doivent pouvoir atteindre $s$ dans $G$.

Si les deux tests réussissent, pour tous $u,v$, on peut suivre $u\to s\to v$. Coût total : $O(|V|+|E|)$.

Attention. Être fortement connexe ne veut pas dire que deux sommets sont reliés par une seule arête, ni même par deux. Il suffit qu’un chemin dirigé existe dans chaque sens.

3.2 Arbres, forêts et caractérisations

Un arbre est un graphe non orienté connexe et sans cycle. Une forêt est un graphe sans cycle ; chacune de ses composantes est un arbre.

Intuition : un arbre relie tout le monde sans redondance. Une arête supprimée coupe la connexion ; une arête supplémentaire entre deux sommets non adjacents crée un cycle.

Caractérisations équivalentes des arbres

Pour un graphe non orienté $G$ à $n$ sommets et $m$ arêtes, les conditions suivantes sont équivalentes :

1. $G$ est connexe et sans cycle ;
2. $G$ est sans cycle et $m=n-1$ ;
3. $G$ est connexe et $m=n-1$ ;
4. $G$ est connexe et supprimer n’importe quelle arête le déconnecte ;
5. $G$ est sans cycle et ajouter n’importe quelle nouvelle arête entre sommets distincts non adjacents crée exactement un cycle ;
6. Il existe un unique chemin simple entre chaque paire de sommets distincts.

Réflexe en exercice. Le seul comptage $m=n-1$ ne suffit pas : vérifier en plus la connexité ou l’absence de cycle. Un arbre peut avoir un sommet de degré supérieur à $2$ (par exemple une étoile).

Idée de preuve à reconstruire. Dans un arbre, supprimer une arête sépare ses extrémités, sinon il existerait un autre chemin et donc un cycle. Ajouter une arête $uv$ referme l’unique chemin préexistant entre $u$ et $v$. Le nombre d’arêtes $n-1$ peut se démontrer par suppression successive des feuilles (ou induction).

3.3 Arbres sous-tendants et poids minimum

Arbre sous-tendant (ou couvrant) : arbre qui conserve tous les sommets de $G$, mais seulement certaines arêtes.

Existence

Tout graphe non orienté connexe possède un arbre sous-tendant.

Construction. Tant qu’il reste un cycle, enlever une de ses arêtes : le graphe reste connexe. Sans cycle, il devient un arbre couvrant.

Objectif : minimiser le coût total (MST)

Si chaque arête a un coût $w(e)$, le poids d’un arbre est :

$$w(T)=\sum_{e\in E(T)}w(e).$$

On cherche l’arbre sous-tendant $T$ pour lequel $w(T)$ est minimal.

MST ≠ plus court chemin :

• MST : minimiser la somme des coûts de toutes les arêtes retenues pour relier tous les sommets.
• Plus court chemin : minimiser le coût du trajet entre deux sommets.

3.4 Kruskal et Prim : deux algorithmes gloutons

Même objectif : construire un arbre sous-tendant de poids minimum d’un graphe connexe pondéré. Deux façons de grandir :

Kruskal — fusionner des morceaux

Idée : considérer les arêtes de la moins chère à la plus chère, sans jamais former de cycle.

1. Trier toutes les arêtes par poids croissant.
2. Ajouter l’arête suivante si elle ne crée pas de cycle ; sinon l’ignorer.
3. Arrêter lorsqu’on a $n-1$ arêtes.

Image mentale : plusieurs petits arbres se rejoignent en une seule structure.

• Choix : poids minimal parmi les arêtes encore examinables, à l’échelle du graphe.
• Contrôle : éviter les cycles, avec union-find (composantes disjointes).
• Complexité : $O(m\log m)$ avec $m=|E|$ (tri dominant).

Prim — étendre un seul arbre

Idée : partir d’un sommet et toujours relier un nouveau sommet au réseau déjà construit.

1. Choisir un sommet $s$ et poser $S=\{s\}$.
2. Choisir l’arête la moins chère entre $S$ et $V\setminus S$.
3. Ajouter cette arête et le sommet atteint ; répéter jusqu’à $S=V$.

Image mentale : un seul arbre s’étend étape par étape.

• Choix : poids minimal parmi les arêtes sortant de l’arbre courant, pas parmi toutes les arêtes du graphe.
• Contrôle : une extrémité dans $S$, l’autre en dehors.
• Structure : file de priorité.
• Complexité : $O(m+n\log n)$ avec une implémentation adaptée (par exemple un tas de Fibonacci), $n=|V|$.

Différence à mémoriser

• Kruskal : plusieurs composantes qui fusionnent ; aucun cycle.
• Prim : un arbre unique qui grandit ; toujours vers un nouveau sommet.

Point commun : si $G$ est connexe, les deux algorithmes produisent un MST. En cas de poids égaux, plusieurs MST distincts peuvent exister.

3.5 Coupes et preuve d’optimalité par échange

Une coupe sépare les sommets en deux ensembles non vides, $S$ et $V\setminus S$. Ses arêtes traversent cette séparation :

$$\delta(S)=\{uv\in E:u\in S,\ v\notin S\}.$$

Observation : tout arbre sous-tendant doit contenir au moins une arête de chaque coupe, sinon les deux côtés ne seraient pas reliés.

Arête légère d'une coupe

Si une coupe ne traverse aucune arête déjà choisie, sélectionner une arête de poids minimum de cette coupe est un choix sûr : il existe un MST compatible avec ce choix et tous les précédents.

Preuve en quatre étapes — argument d’échange

Soit $T^*$ un MST contenant les arêtes déjà retenues, mais pas la nouvelle arête $e$.

1. Ajouter $e$ à $T^*$ crée exactement un cycle.
2. Le cycle franchit la coupe au moins deux fois ; il possède donc une autre arête $f$ qui la traverse. $f$ n’appartient pas aux arêtes déjà retenues.
3. Comparer les coûts : comme $e$ est de poids minimum sur la coupe, $w(e)\le w(f)$.
4. Échanger : supprimer $f$ et garder $e$. On obtient encore un arbre sous-tendant et

$$w(T^*-f+e)\le w(T^*).$$

Le nouvel arbre est donc lui aussi optimal, et il contient $e$.

Piège : les arêtes d’un cycle n’ont pas forcément le même poids. L’inégalité provient de la coupe, pas du cycle.

Application : Prim utilise la coupe entre l’arbre courant et les autres sommets ; Kruskal utilise une coupe séparant une composante de sa forêt des autres.

3.6 Cayley : compter les arbres sous-tendants

$T(G)$ désigne le nombre d’arbres sous-tendants du graphe $G$.

Graphe complet

Théorème de Cayley

Pour le graphe complet $K_n$ à sommets étiquetés :

$$T(K_n)=n^{n-2}.$$

Exemple : $T(K_4)=4^2=16$. Ne pas confondre arbres étiquetés et formes d’arbres à isomorphisme près.

Suppression-contraction

Compter par deux cas

Pour une arête $e$ qui n’est pas une boucle :

$$T(G)=T(G-e)+T(G/e).$$

Pourquoi additionner ? Chaque arbre sous-tendant :

• exclut $e$ : on le compte dans $G-e$ (suppression) ;
• contient $e$ : on le compte dans $G/e$ (contraction, fusion des extrémités).

Conserver les arêtes parallèles éventuelles après contraction : ce sont des choix distincts.

Cas de base : arbre → $T(G)=1$ ; graphe non connexe → $T(G)=0$ ; cycle $C_n$ → $T(C_n)=n$.

3.7 Connectivité : combien de pannes un réseau supporte-t-il ?

Un arbre est économique mais fragile : une seule arête supprimée suffit à le déconnecter.

Deux mesures différentes :

• $\kappa(G)$, connectivité : taille minimale d’une coupe de sommets qui déconnecte $G$ (convention : $\kappa(K_n)=n-1$).
• $\lambda(G)$, arête-connectivité : taille minimale d’une coupe d’arêtes qui déconnecte $G$.

Interprétation immédiate :

• $k$-connexe → reste connexe après suppression arbitraire de $k-1$ sommets au plus.
• $k$-arête-connexe → reste connexe après suppression arbitraire de $k-1$ arêtes au plus.

Lien entre les connectivités

En notant $\delta(G)$ le degré minimum :

$$\kappa(G)\le\lambda(G)\le\delta(G).$$

Pourquoi $\lambda(G)\le\delta(G)$ ? Supprimer toutes les arêtes d’un sommet de degré minimum l’isole.

Piège d’examen : résister à la suppression de deux arêtes exige une 3-arête-connexité, et non une 2-arête-connexité.

3.8 Menger : plusieurs chemins indépendants

Intuition : si plusieurs chemins indépendants relient deux sommets, une seule panne ne suffit pas à tous les détruire.

Théorème de Menger — sommets

Pour un graphe non orienté d’au moins $k+1$ sommets : $G$ est $k$-connexe si et seulement si toute paire de sommets distincts possède au moins $k$ chemins intérieurement disjoints.

« Intérieurement disjoints » : les chemins peuvent partager leurs deux extrémités, pas leurs sommets intermédiaires.

Cas $k=2$ (Whitney) : deux sommets distincts d’un graphe 2-connexe appartiennent à un même cycle.

Version arêtes : $G$ est $k$-arête-connexe si et seulement si toute paire de sommets distincts est reliée par au moins $k$ chemins sans arête commune. Ils peuvent partager des sommets intérieurs.

Réflexe : quand l’énoncé exige plusieurs itinéraires indépendants, déterminer si l’indépendance concerne les sommets ou les arêtes.

3.9 Harary : robustesse avec un minimum d’arêtes

Problème : construire un graphe $k$-connexe à $n$ sommets avec le moins d’arêtes possible.

Comme chaque sommet doit avoir un degré au moins $k$, les poignées de main donnent :

$$2|E|=\sum_{v\in V}\deg(v)\ge kn.$$

D’où la borne :

$$|E|\ge\left\lceil\frac{kn}{2}\right\rceil.$$

Graphes de Harary $H_{k,n}$ : ils atteignent cette borne et sont $k$-connexes.

• Si $k$ est pair : placer les sommets sur un cercle et relier chacun aux $k/2$ voisins précédents et aux $k/2$ suivants (modulo $n$).
• Exemple : $H_{2,6}=C_6$ a 6 sommets, 6 arêtes et est 2-connexe.
• Si $k$ est impair : construction légèrement différente ; même borne optimale.

Limite : trouver un MST est efficace avec Kruskal/Prim ; rechercher un sous-graphe $k$-connexe de poids minimum dans un graphe pondéré général est un problème nettement plus difficile.

3.10 Identifier la bonne méthode dans un énoncé

Signal dans l’énoncé	Outil ou résultat pertinent
Explorer des sommets accessibles	BFS / DFS
Trouver une distance en nombre d’arêtes	BFS
Vérifier la forte connexité orientée	Deux explorations : graphe puis transposé
Graphe connexe, sans cycle, $n-1$ arêtes	Caractérisations des arbres
Relier tous les sommets au coût total minimal	MST : Kruskal ou Prim
Justifier un choix glouton	Coupe + échange d’arêtes
Compter les arbres couvrants de $K_n$	Cayley : $n^{n-2}$
Compter des arbres couvrants d’un graphe quelconque	Suppression-contraction
Maintenir un réseau après des pannes	$\kappa(G)$ / $\lambda(G)$, coupes
Exiger plusieurs chemins indépendants	Menger
Réseau $k$-connexe avec très peu d’arêtes	Borne $\lceil kn/2\rceil$, Harary

---

Repères de reconnaissance — chapitres 1 et 2

Si l’énoncé parle de…	Penser à…
somme des degrés, nombre d’arêtes	poignées de main
même liste de degrés	invariant utile, mais pas preuve d’isomorphisme
relier tous les sommets, nombre de composantes	connexité
chaque arête exactement une fois	Euler / Hierholzer / Fleury
0 ou 2 sommets de degré impair	parcours eulérien
absence de cycle impair	graphe biparti
chaque sommet exactement une fois	hamiltonien — chapitre ultérieur
poids non négatifs, source, distance minimale	Dijkstra
mise à jour $\min(\ell(v),\ell(u)+w(uv))$	relaxation de Dijkstra
toutes les arêtes de même poids	BFS
$\min$ à la place de $+$ et $+$ à la place de $\times$	semi-anneau $(\min,+)$