Notion de graphes (partie 1/2)

## Objectifs et prérequis **Objectifs** : à la fin de ce chapitre l’élève pourra - définir précisément un graphe, distinguer les différents types (simple, orienté, valué, etc.) ; - manipuler le vocabulaire de base (degré, chemin, cycle, arbre, sous‑graphe, graphe complet, bipartite) ; - représenter un graphe par une matrice d’adjacence ou d’incidence et interpréter les puissances de cette matrice ; - appliquer les algorithmes de parcours en largeur (BFS) et en profondeur (DFS) pour tester la connexité, détecter des cycles ou déterminer le plus court chemin en nombre d’arêtes ; - construire un arbre couvrant minimal avec l’algorithme de Kruskal (et comprendre sa démonstration via la propriété de coupe) ; - reconnaître les propriétés de connexité (faible, forte) dans un digraphe et mettre en œuvre une procédure de vérification (ex. deux DFS ou Kosaraju). **Prérequis** : notions de ensembles, de fonctions, de logique propositionnelle, de base du calcul matriciel (addition, multiplication) et de raisonnement par récurrence. --- ## Introduction contextualisée Les graphes apparaissent partout dans la vie quotidienne : réseaux routiers, réseaux sociaux, dépendances entre tâches d’un projet, circuits électroniques, chaînes de transmission d’informations, etc. Modéliser ces situations par un graphe permet de raisonner sur leur structure (connexité, présence de cycles, optimalité de certaines connexions) et d’appliquer des algorithmes efficaces pour résoudre des problèmes concrets (itinéraire le plus court, déploiement minimal de câbles, ordonnancement de tâches). Ce chapitre introduit le langage et les outils de base qui seront utilisés tout au long de l’année en mathématiques de spécialité et en sciences de l’ingénieur. --- ## I. Leçon 27 : Quelques vocabulaires ### 1. Définition d’un graphe Un **graphe non orienté** est un couple $G=(V,E)$ où - $V$ est un ensemble fini d’éléments appelés **sommets** (ou nœuds) ; - $E$ est un ensemble d’arêtes non ordonnées, chaque arête étant un sous‑ensemble de $V$ de cardinalité $2$ (on note $\{u,v\}$ l’arête reliant les sommets $u$ et $v$). Un **graphe orienté** (ou **digraphe**) remplace les arêtes par des **arcs** ordonnés $(u,v)$ ; l’arc part de $u$ (queue) vers $v$ (tête). Un **multigraphe** autorise plusieurs arêtes entre le même paire de sommets ; un **pseudographe** autorise aussi des boucles (arête $\{u,u\}$). Un **graphe simple** est à la fois sans boucles et sans arêtes multiples. > **> Définition** : Le **degré** d’un sommet $v$ dans un graphe non orienté, noté $\deg(v)$, est le nombre d’arêtes incidentes à $v$. Dans un digraphe on distingue le degré sortant $\deg^{+}(v)$ (nombre d’arcs sortant de $v$) et le degré entrant $\deg^{-}(v)$ (nombre d’arcs entrant dans $v$). ### 2. Vocabulaire de base | Terme | Définition | |-------|------------| | **Chemin** | suite alternée de sommets et d’arêtes $v_0,e_1,v_1,\dots,e_k,v_k$ où chaque $e_i=\{v_{i-1},v_i\}$ (ou $(v_{i-1},v_i)$ pour un digraphe). | | **Chemin élémentaire** | chemin ne passant jamais deux fois par le même sommet. | | **Cycle** | chemin fermé ($v_0=v_k$) de longueur au moins $3$ (dans un graphe simple) où tous les sommets intermédiaires sont distincts. | | **Circuit** | dans un digraphe, un cycle dirigé (les arcs suivent le même sens). | | **Sous‑graphe** | graphe $H=(V',E')$ avec $V'\subseteq V$ et $E'\subseteq E$ (les arêtes de $E'$ ayant leurs extrémités dans $V'$). | | **Graphe induit** | sous‑graphe où $E'$ contient **toutes** les arêtes de $E$ ayant leurs deux extrémités dans $V'$. | | **Graphe complet** $K_n$ | graphe simple où chaque paire distincte de sommets est reliée par une arête. | | **Graphe bipartite** | graphe dont l’ensemble des sommets peut être partitionné en deux parties $X,Y$ telles que toute arête relie un sommet de $X$ à un sommet de $Y$. | | **Arbre** | graphe connexe et acyclique (équivalentement : $n$ sommets et $n-1$ arêtes). | | **Forêt** | graphe acyclique (union d’arbres). | ### 3. Propriété fondamentale : somme des degrés **Théorème (lemme de la main‑poignée)** : Dans tout graphe non orienté $G=(V,E)$, $$\sum_{v\in V}\deg(v)=2|E|.$$ *Preuve* : Chaque arête $\{u,v\}$ contribue exactement $1$ au degré de $u$ et $1$ au degré de $v$. En sommant sur toutes les arêtes, chaque arête est comptée deux fois, d’où le facteur $2$. ### 4. Exemples entièrement résolus **Exemple 1** (degrés simples). Considérons le graphe $G$ avec $V=\{a,b,c,d\}$ et $E=\{\{a,b\},\{a,c\},\{b,c\},\{c,d\}\}$. - $\deg(a)=2$ (arêtes $\{a,b\},\{a,c\}$) - $\deg(b)=2$ ($\{a,b\},\{b,c\}$) - $\deg(c)=3$ ($\{a,c\},\{b,c\},\{c,d\}$) - $\deg(d)=1$ ($\{c,d\}$) Vérifions le lemme : $2+2+3+1=8=2|E|$ car $|E|=4$. **Exemple 2** (détection d’un graphe eulérien). Un graphe connexe possède un **circuit eulérien** (parcours qui utilise chaque arête exactement une fois) si et seulement si tout sommet est de degré pair. Prenons le graphe précédent : les degrés sont $2,2,3,1$. Comme $c$ et $d$ ont un degré impair, le graphe n’est pas eulérien. Si on ajoute l’arête $\{b,d\}$, les degrés deviennent $2,3,3,2$ ; toujours deux sommets impairs → pas eulérien. En ajoutant aussi $\{a,d\}$ on obtient $3,3,3,3$ : tous pairs, le graphe devient eulérien (on peut vérifier l’existence d’un circuit). --- ## II. Leçon 28 : Quelques propriétés et algorithmes ### 1. Connexité - Un graphe **non orienté** est **connexe** si tout couple de sommets est relié par au moins un chemin. - Ses **composantes connexes** sont les sous‑graphes induits maximaux qui sont connexes. - Dans un **digraphe** on distingue : *faiblement connexe* si le graphe sous‑jacent (en ignorant l’orientation) est connexe ; *fortement connexe* si pour tout couple $(u,v)$ il existe un chemin dirigé de $u$ vers $v$ et un chemin dirigé de $v$ vers $u$. ### 2. Parcours en largeur (BFS) et en profondeur (DFS) **BFS** (Breadth‑First Search) explore les sommets par niveaux : on part d’une racine $s$, on visite tous ses voisins, puis les voisins de ceux‑ci, etc. **DFS** (Depth‑First Search) suit un chemin autant que possible avant de revenir en arrière. Les deux algorithmes s’exécutent en temps $\mathcal{O}(|V|+|E|)$ lorsqu’on utilise des listes d’adjacence. > **> Règle** : BFS fournit le plus court chemin (en nombre d’arêtes) entre la racine et tout autre sommet dans un graphe non pondéré. **Preuve esquissée** : BFS visite les sommets dans l’ordre croissant de leur distance à $s$ ; lorsqu’un sommet $v$ est découvert pour la première fois, le chemin suivi depuis $s$ a exactement cette distance, sinon un chemin plus court aurait déjà été découvert. #### Exemple BFS Graphe non orienté $V=\{1,2,3,4,5\}$, $E=\{\{1,2\},\{1,3\},\{2,4\},\{3,5\},\{4,5\}\}$. Partons de $s=1$. | Étape | File (FIFO) | Sommet visité | Distance depuis 1 | |-------|-------------|---------------|-------------------| | Init | [1] | – | 0 | | 1 | [2,3] | 1 | 0 | | 2 | [3,4] | 2 | 1 | | 3 | [4,5] | 3 | 1 | | 4 | [5] | 4 | 2 (via 2) | | 5 | [] | 5 | 2 (via 3 ou 4) | Le plus court chemin de $1$ à $5$ a longueur $2$ (ex. $1\!-\!3\!-\!5$). #### Exemple DFS (détection de cycle) Dans le même graphe, en lançant un DFS depuis $1$ on rencontre l’arête $\{4,5\}$ alors que $4$ et $5$ sont déjà visités et ne sont pas parent‑enfant dans l’arbre de recherche → on détecte un cycle $2\!-\!4\!-\!5\!-\!3\!-\!1\!-\!2$. ### 3. Arbre couvrant minimal (ACM) – Algorithme de Kruskal Soit $G=(V,E,w)$ un graphe connexe, non orienté, pondéré par une fonction $w:E\to\mathbb{R}_{+}$. Un **arbre couvrant** est un sous‑graphe qui est un arbre et contient tous les sommets de $V$. Parmi eux, celui de poids total minimal est l’**ACM**. **Algorithme de Kruskal** 1. Trier les arêtes par poids croissant : $e_1,e_2,\dots,e_{|E|}$ avec $w(e_1)\le w(e_2)\le\dots$. 2. Partir avec une forêt $F$ contenant chaque sommet comme arbre isolé. 3. Pour chaque arête $e_i$ dans l’ordre : - Si ses extrémités appartiennent à deux arbres différents de $F$, ajouter $e_i$ à $F$ (union des deux arbres). - Sinon, la rejeter (elle créerait un cycle). 4. Arrêter lorsque $F$ contient exactement $|V|-1$ arêtes. **Démonstration de correction (propriété de coupe)** *Lemma de coupe* : Soit $S\subset V$ une partie propre non vide. Parmi toutes les arêtes qui ont une extrémité dans $S$ et l’autre dans $V\setminus S$, celle de poids minimal appartient à tout ACM. *Preuve* : Supposons un ACM $T$ qui ne contient pas cette arête $e_{\min}$. Ajouter $e_{\min}$ à $T$ crée un unique cycle ; ce cycle doit contenir une autre arête $f$ traversant la même coupe (sinon le graphe resterait connexe après suppression de $f$). Comme $w(e_{\min})\le w(f)$, en échangeant $f$ par $e_{\min}$ on obtient un autre arbre couvrant de poids pas supérieur, contredisant la minimalité de $T$ si l’inégalité était stricte. Donc $e_{\min}$ doit appartenir à tout ACM. Kruskal ajoute exactement les arêtes de poids minimal qui ne forment pas de cycle, donc par récurrence sur les coupes considérées, l’ensemble construit est un ACM. > **> Propriété** : Dans un graphe pondéré, l’algorithme de Kruskal produit un arbre couvrant minimal. #### Exemple Kruskal Graphe pondéré : $V=\{A,B,C,D,E\}$ Arêtes avec poids : $\{A,B\}:4$, $\{A,C\}:2$, $\{B,C\}:1$, $\{B,D\}:5$, $\{C,D\}:3$, $\{C,E\}:6$, $\{D,E\}:2$. Tri : $\{B,C\}(1)$, $\{A,C\}(2)$, $\{D,E\}(2)$, $\{C,D\}(3)$, $\{A,B\}(4)$, $\{B,D\}(5)$, $\{C,E\}(6)$. État de la forêt (initial : chaque sommet seul) : | Arête considérée | Extrémités dans mêmes arbres ? | Action | Forêt résultante | |------------------|--------------------------------|--------|------------------| | $\{B,C\}$ (1) | non | ajouter| $\{B,C\}$ + isolés A,D,E | | $\{A,C\}$ (2) | non (A seul, C dans {B,C}) | ajouter| $\{A,B,C\}$ + D,E | | $\{D,E\}$ (2) | non | ajouter| $\{A,B,C\}$, $\{D,E\}$ | | $\{C,D\}$ (3) | non (C dans premier, D dans second) | ajouter | $\{A,B,C,D,E\}$ (un seul arbre) | | On a maintenant $4=\vert V\vert -1$ arêtes → arrêt. L’ACM comporte les arêtes $\{B,C\},\{A,C\},\{D,E\},\{C,D\}$ avec poids total $1+2+2+3=8$. ### 4. Vérification de la forte connexité dans un digraphe Un digraphe est fortement connexe si et seulement si, en choisissant un sommet arbitraire $s$, - le DFS depuis $s$ atteint tous les sommets, et - le DFS dans le graphe **transposé** (tous les arcs inversés) depuis $s$ atteint aussi tous les sommets. Cette double visite constitue l’algorithme de Kosaraju (en deux passes). #### Exemple de forte connexité Digraphe $V=\{1,2,3,4\}$, arcs : $(1,2),(2,3),(3,1),(3,4),(4,2)$. - DFS depuis $1$ dans le graphe original : on visite $1\to2\to3\to4$ (tous atteints). - Graphe transposé : arcs $(2,1),(3,2),(1,3),(4,3),(2,4)$. - DFS depuis $1$ dans le transposé : on visite $1\to3\to2\to4$ (tous atteints). Donc le digraphe est fortement connexe. --- ## III. Leçon 15 : Quelques vocabulaires (matrices d’adjacence et d’incidence) ### 1. Matrice d’adjacence Pour un graphe (simple ou orienté) $G=(V,E)$ avec $V=\{v_1,\dots,v_n\}$, on définit la **matrice d’adjacence** $A=(a_{ij})$ de taille $n\times n$ par $$ a_{ij}= \begin{cases} \text{nombre d’arêtes de }v_i\text{ vers }v_j &\text{(graphe orienté)}\\[2mm] \text{nombre d’arêtes non orientées entre }v_i\text{ et }v_j &\text{(graphe non orienté)}\\ 0 &\text{sinon.} \end{cases} $$ Dans un graphe simple non orienté, $a_{ij}\in\{0,1\}$ et $A$ est symétrique ($A^{\mathsf T}=A$). **Propriété** : Le degré du sommet $v_i$ (dans le cas non orienté) vaut la somme de la $i$‑ième ligne (ou colonne) de $A$ : $$ \deg(v_i)=\sum_{j=1}^{n}a_{ij}. $$ Dans un digraphe, la somme de la ligne $i$ donne le degré sortant $\deg^{+}(v_i)$ et la somme de la colonne $i$ le degré entrant $\deg^{-}(v_i)$. > **> Définition** : La **trace** de $A$, $\operatorname{tr}(A)=\sum_i a_{ii}$, vaut deux fois le nombre de boucles (car chaque boucle contribue $2$ à la somme des degrés). ### 2. Matrice d’incidence Soit $E=\{e_1,\dots,e_m\}$ l’ensemble des arêtes (ou arcs). La **matrice d’incidence** $B$ est de taille $n\times m$ ; pour une arête non orientée $e_k=\{u,v\}$ on pose $$ b_{ik}= \begin{cases} 1 &\text{si }v_i=u\text{ ou }v_i=v,\\ 0 &\text{sinon.} \end{cases} $$ Dans un digraphe, on oriente la colonne : $$ b_{ik}= \begin{cases} +1 &\text{si }v_i\text{ est la tête de l’arc }e_k,\\ -1 &\text{si }v_i\text{ est la queue de l’arc }e_k,\\ 0 &\text{sinon.} \end{cases} $$ **Relation degré‑incidence** : Pour un graphe non orienté, $$ B\,B^{\mathsf T}=D+A, $$ où $D$ est la matrice diagonale des degrés ($D_{ii}=\deg(v_i)$) et $A$ la matrice d’adjacence. ### 3. Puissances de la matrice d’adjacence **Théorème** : Pour tout entier $k\ge 1$, l’entrée $(i,j)$ de $A^{k}$ égale le nombre de chemins de longueur exactement $k$ allant du sommet $v_i$ au sommet $v_j$ (dans le cas orienté, on compte les chemins dirigés). *Preuve par récurrence* : - Pour $k=1$, $A^{1}=A$ donne le nombre d’arêtes directes, donc le nombre de chemins de longueur $1$. - Supposons vrai pour $k$. Alors $(A^{k+1})_{ij}=\sum_{\ell} (A^{k})_{i\ell}a_{\ell j}$. Chaque terme compte les chemins de longueur $k$ de $i$ à $\ell$ suivis d’une arête $\ell\to j$, donc tous les chemins de longueur $k+1$ de $i$ à $j$. > **> Règle** : $A^{2}$ compte les chemins de longueur $2$ ; son entrée diagonale $(A^{2})_{ii}$ égale le degré du sommet $v_i$ dans un graphe simple non orienté (car chaque chemin de longueur $2$ qui revient à $i$ passe par un voisin). #### Exemple de matrice d’adjacence Graphe non orienté $V=\{1,2,3,4\}$, $E=\{\{1,2\},\{2,3\},\{3,4\},\{4,1\}\}$ (un cycle $C_4$). $$ A= \begin{pmatrix} 0&1&0&1\\ 1&0&1&0\\ 0&1&0&1\\ 1&0&1&0 \end{pmatrix}. $$ Calcul de $A^{2}$ : $$ A^{2}= \begin{pmatrix} 2&0&2&0\\ 0&2&0&2\\ 2&0&2&0\\ 0&2&0&2 \end{pmatrix}. $$ Interprétation : - $(A^{2})_{13}=2$ signifie qu’il existe deux chemins de longueur $2$ de $1$ à $3$ : $1\!-\!2\!-\!3$ et $1\!-\!4\!-\!3$. - $(A^{2})_{11}=2$ égale le degré du sommet $1$ (qui est $2$). #### Exemple de matrice d’incidence Même graphe $C_4$. On ordonne les arêtes comme $e_1=\{1,2\}, e_2=\{2,3\}, e_3=\{3,4\}, e_4=\{4,1\}$. $$ B= \begin{pmatrix} 1&0&0&1\\ 1&1&0&0\\ 0&1&1&0\\ 0&0&1&1 \end{pmatrix}. $$ Vérifions $BB^{\mathsf T}$ : $$ BB^{\mathsf T}= \begin{pmatrix} 2&1&0&1\\ 1&2&1&0\\ 0&1&2&1\\ 1&0&1&2 \end{pmatrix} = \begin{pmatrix} \deg(1)&1&0&1\\ 1&\deg(2)&1&0\\ 0&1&\deg(3)&1\\ 1&0&1&\deg(4) \end{pmatrix} + A, $$ car la matrice diagonale obtenue est $D=\operatorname{diag}(2,2,2,2)$ et $A$ est celle ci‑dessus. --- ## Synthèse du chapitre - **Graphe** : couple $(V,E)$ ; notions de degré, chemin, cycle, arbre, graphe complet, bipartite. - **Lemme de la main‑poignée** : $\sum\deg(v)=2|E|$. - **Représentations** : matrice d’adjacence $A$ (comptage des arêtes/arcs) ; matrice d’incidence $B$ (relation sommet‑arête). - **Puissances de $A$** : $(A^{k})_{ij}$ = nombre de chemins de longueur $k$ de $i$ à $j$. - **Connexité** : composantes connexes ; digraphe fortement connexe ⇔ deux DFS (original et transposé) atteignent tous les sommets. - **Parcours** : BFS donne le plus court chemin en nombre d’arêtes (non pondéré) ; DFS détecte les cycles. - **Arbre couvrant minimal** : algorithme de Kruskal (tri des arêtes, union‑find) correct grâce à la propriété de coupe. - **Formules clés** : - $\deg(v_i)=\sum_j a_{ij}$ (non orienté). - $BB^{\mathsf T}=D+A$. - $(A^{k})_{ij}$ = # chemins de longueur $k$. --- ## Glossaire | Terme | Définition | |-------|------------| | Sommet | Élément de l’ensemble $V$ d’un graphe. | | Degré | Nombre d’arêtes incidentes à un sommet (ou degré sortant/entrant dans un digraphe). | | Chemin | Suite alternée de sommets et d’arêtes reliant deux sommets. | | Cycle | Chemin fermé de longueur ≥ 3 sans répétition de sommets (sauf l’extrémité). | | Arbre | Graphe connexe et acyclique ($\vert E\vert =\vert V\vert -1$). | | Graphe complet $K_n$ | Chaque paire de sommets distincts est reliée par une arête. | | Graphe bipartite | Sommes partitionnables en deux parties telles que toute arête relie une partie à l’autre. | | Matrice d’adjacence $A$ | $a_{ij}$ = nombre d’arêtes/arcs de $i$ vers $j$. | | Matrice d’incidence $B$ | Colonne d’une arête indique ses extrémités (+1,‑1 pour orienté, 1,1 pour non orienté). | | Arbre couvrant minimal (ACM) | Arbre couvrant de poids total minimal dans un graphe pondéré. | | Algorithme de Kruskal | Procédure gloutonne qui construit un ACM en triant les arêtes et en évitant les cycles. | | BFS (Breadth‑First Search) | Parcours en niveaux, donne le plus court chemin en nombre d’arêtes. | | DFS (Depth‑First Search) | Parcours en profondeur, utile pour détecter des cycles ou tester la connexité. | | Forte connexité (digraphe) | Existence d’un chemin dirigé dans les deux sens entre chaque paire de sommets. | | Lemme de la main‑poignée | $\sum_{v\in V}\deg(v)=2\vert E\vert $. | --- ## Exercices d'application corrigés ### Exercice 1 (vocabulaire de base) Soit le graphe non orienté $G$ avec $V=\{a,b,c,d,e\}$ et $E=\{\{a,b\},\{a,c\},\{b,c\},\{b,d\},\{c,d\},\{d,e\}\}$. 1. Donner le degré de chaque sommet. 2. Déterminer si $G$ est eulérien (expliquer). 3. Trouver un arbre couvrant de $G$ comportant exactement $4$ arêtes. **Corrigé** 1. Degrés : - $\deg(a)=2$ ($\{a,b\},\{a,c\}$) - $\deg(b)=3$ ($\{a,b\},\{b,c\},\{b,d\}$) - $\deg(c)=3$ ($\{a,c\},\{b,c\},\{c,d\}$) - $\deg(d)=3$ ($\{b,d\},\{c,d\},\{d,e\}$) - $\deg(e)=1$ ($\{d,e\}$) 2. Un graphe connexe possède un circuit eulérien si et seulement si tous les degrés sont pairs. Ici $b,c,d$ ont un degré impair ($3$) et $e$ a degré $1$ (impair). Donc $G$ **n’est pas** eulérien. 3. Un arbre couvrant doit avoir $|V|-1=4$ arêtes et être connexe sans cycle. On peut choisir par exemple : $\{a,b\},\{a,c\},\{c,d\},\{d,e\}$. Vérification : les sommets sont tous reliés, aucune boucle n’apparaît (on a bien $4$ arêtes). --- ### Exercice 2 (matrice d’adjacence et chemins) Considérons le digraphe $D$ avec $V=\{1,2,3,4\}$ et arcs : $(1,2),(2,3),(3,1),(3,4),(4,2)$. 1. Écrire la matrice d’adjacence $A$. 2. Calculer $A^{2}$ et interpréter les entrées non nulles. 3. Déterminer le nombre de chemins de longueur exactement $3$ de $1$ vers $4$. **Corrigé** 1. $$ A= \begin{pmatrix} 0&1&0&0\\ 0&0&1&0\\ 1&0&0&1\\ 0&1&0&0 \end{pmatrix}. $$ 2. Multiplication : $$ A^{2}=A\cdot A= \begin{pmatrix} 0&0&1&0\\ 1&0&0&1\\ 0&2&0&0\\ 0&0&1&0 \end{pmatrix}. $$ Interprétation : $(A^{2})_{ij}$ compte les chemins de longueur $2$ de $i$ à $j$. Par exemple, $(A^{2})_{31}=0$ signifie qu’il n’y a aucun chemin de longueur $2$ de $3$ à $1$ (en effet, le seul chemin de longueur $2$ partant de $3$ est $3\to1\to2$ ou $3\to4\to2$). 3. Le nombre de chemins de longueur $3$ de $1$ à $4$ vaut $(A^{3})_{14}$. On peut calculer $A^{3}=A^{2}\cdot A$ : $$ A^{3}= \begin{pmatrix} 0&0&1&0\\ 1&0&0&1\\ 0&2&0&0\\ 0&0&1&0 \end{pmatrix} \!\! \begin{pmatrix} 0&1&0&0\\ 0&0&1&0\\ 1&0&0&1\\ 0&1&0&0 \end{pmatrix} = \begin{pmatrix} 1&0&0&1\\ 0&2&0&0\\ 0&0&2&0\\ 0&0&0&1 \end{pmatrix}. $$ Donc $(A^{3})_{14}=1$ : il existe exactement un chemin de longueur $3$ de $1$ à $4$, à savoir $1\to2\to3\to4$. --- ### Exercice 3 (BFS et plus court chemin) Dans le graphe non orienté suivant : $V=\{A,B,C,D,E,F\}$, $E=\{\{A,B\},\{A,C\},\{B,D\},\{C,D\},\{D,E\},\{E,F\},\{C,F\}\}$. En utilisant le BFS partiant du sommet $A$, donner : 1. L’ordre de visite des sommets. 2. La distance (en nombre d’arêtes) de $A$ à chaque sommet. 3. Un plus court chemin de $A$ à $F$. **Corrigé** On effectue le BFS avec une file FIFO. | Étape | File (début) | Sommet visité | Nouveaux voisins ajoutés | |-------|--------------|---------------|--------------------------| | 0 | [A] | – | – | | 1 | [B,C] | A | B, C | | 2 | [C,D] | B | D (A déjà visité) | | 3 | [D,F] | C | D (déjà en file), F | | 4 | [F,E] | D | E | | 5 | [E] | F | – | | 6 | [] | E | – | **Ordre de visite** : $A, B, C, D, F, E$. **Distances** (nombre d’arêtes depuis $A$) : - $d(A,A)=0$ - $d(A,B)=1$ (arête $A\!-\!B$) - $d(A,C)=1$ - $d(A,D)=2$ (ex. $A\!-\!B\!-\!D$ ou $A\!-\!C\!-\!D$) - $d(A,F)=2$ (ex. $A\!-\!C\!-\!F$) - $d(A,E)=3$ (ex. $A\!-\!B\!-\!D\!-\!E$) **Plus court chemin $A\to F$** : on peut prendre $A\!-\!C\!-\!F$ (longueur $2$). --- ### Exercice 4 (Kruskal) Soit le graphe pondéré $G$ avec $V=\{1,2,3,4,5\}$ et les arêtes suivantes (poids indiqué) : - $\{1,2\}:4$ - $\{1,3\}:2$ - $\{2,3\}:1$ - $\{2,4\}:5$ - $\{3,4\}:3$ - $\{3,5\}:6$ - $\{4,5\}:2$ Appliquer l’algorithme de Kruskal pour obtenir un arbre couvrant minimal et donner son poids total. **Corrigé** Tri des arêtes par poids croissant : 1. $\{2,3\}:1$ 2. $\{1,3\}:2$ 3. $\{4,5\}:2$ 4. $\{3,4\}:3$ 5. $\{1,2\}:4$ 6. $\{2,4\}:5$ 7. $\{3,5\}:6$ Évolution de la forêt (initial : chaque sommet seul) : | Arête considérée | Même arbre ? | Action | Forêt après | |------------------|--------------|--------|-------------| | $\{2,3\}:1$ | non | ajouter| $\{2,3\}$ + $\{1\},\{4\},\{5\}$ | | $\{1,3\}:2$ | non (1 seul, 3 dans $\{2,3\}$) | ajouter | $\{1,2,3\}$ + $\{4\},\{5\}$ | | $\{4,5\}:2$ | non | ajouter| $\{1,2,3\}$, $\{4,5\}$ | | $\{3,4\}:3$ | non (3 dans premier, 4 dans second) | ajouter | $\{1,2,3,4,5\}$ (un seul arbre) | | On a maintenant $4=\vert V\vert -1$ arêtes → arrêt. L’ACM contient les arêtes : $\{2,3\},\{1,3\},\{4,5\},\{3,4\}$. Poids total = $1+2+2+3 = 8$. --- ### Exercice 5 (forte connexité) Soit le digraphe $D$ avec $V=\{a,b,c,d\}$ et arcs : $(a,b),(b,c),(c,a),(c,d),(d,b)$. 1. Vérifier si $D$ est fortement connexe en utilisant la méthode du double DFS. 2. Si ce n’est pas le cas, proposer l’ajout d’un arc minimal qui rendrait le digraphe fortement connexe. **Corrigé** **Étape 1** : DFS depuis $a$ dans le graphe original. - De $a$ on va à $b$, puis $c$, puis de $c$ on peut retourner à $a$ (déjà visité) ou aller à $d$, puis de $d$ on revient à $b$ (déjà visité). Tous les sommets $\{a,b,c,d\}$ sont atteints. **Étape 2** : Construire le graphe transposé $D^{T}$ (inverser chaque arc) : $(b,a),(c,b),(a,c),(d,c),(b,d)$. DFS depuis $a$ dans $D^{T}$ : - De $a$ on peut aller à $c$ (arc $(a,c)$), puis de $c$ à $b$ ($(c,b)$), puis de $b$ à $d$ ($(b,d)$), puis de $d$ à $c$ ($(d,c)$) déjà visité. On atteint bien tous les sommets $\{a,b,c,d\}$. Comme les deux DFS atteignent tous les sommets, **$D$ est fortement connexe**. **Étape 3** (non nécessaire ici) : si l’un des DFS avait échoué, il aurait suffi d’ajouter un arc allant d’une composante non atteinte vers la racine du DFS pour rétablir la forte connexité. --- ### Exercice 6 (matrice d’incidence et degré) Soit le graphe non orienté $G$ avec $V=\{v_1,v_2,v_3,v_4\}$ et $E=\{e_1=\{v_1,v_2\},e_2=\{v_2,v_3\},e_3=\{v_3,v_4\},e_4=\{v_4,v_1\}\}$ (un $C_4$). 1. Construire la matrice d’incidence $B$. 2. Vérifier l’identité $BB^{\mathsf T}=D+A$ où $D$ est la matrice diagonale des degrés et $A$ la matrice d’adjacence. 3. En déduire le degré de chaque sommet à partir de $B$. **Corrigé** 1. Ordre des colonnes : $e_1,e_2,e_3,e_4$. $$ B= \begin{pmatrix} 1&0&0&1\\ 1&1&0&0\\ 0&1&1&0\\ 0&0&1&1 \end{pmatrix}. $$ 2. Calcul de $BB^{\mathsf T}$ : $$ BB^{\mathsf T}= \begin{pmatrix} 2&1&0&1\\ 1&2&1&0\\ 0&1&2&1\\ 1&0&1&2 \end{pmatrix}. $$ Matrice d’adjacence $A$ du $C_4$ : $$ A= \begin{pmatrix} 0&1&0&1\\ 1&0&1&0\\ 0&1&0&1\\ 1&0&1&0 \end{pmatrix}. $$ Matrice diagonale des degrés $D$ (chaque sommet de degré $2$) : $$ D= \begin{pmatrix} 2&0&0&0\\ 0&2&0&0\\ 0&0&2&0\\ 0&0&0&2 \end{pmatrix}. $$ Alors $D+A=$ $$ \begin{pmatrix} 2&1&0&1\\ 1&2&1&0\\ 0&1&2&1\\ 1&0&1&2 \end{pmatrix}=BB^{\mathsf T}. $$ L’identité est vérifiée. 3. Le degré d’un sommet $v_i$ est la somme de la $i$‑ième ligne de $B$ (ou de $BB^{\mathsf T}$ en diagonale). En lisant les lignes de $B$ : - Ligne $v_1$ : $1+0+0+1=2$ → $\deg(v_1)=2$ - Ligne $v_2$ : $1+1+0+0=2$ - Ligne $v_3$ : $0+1+1+0=2$ - Ligne $v_4$ : $0+0+1+1=2$ Tous les degrés valent $2$, conforme au graphe $C_4$. --- ## Erreurs fréquentes | Erreur fréquente | Pourquoi elle se produit | Comment l’éviter | |------------------|--------------------------|------------------| | **Confondre degré sortant et degré entrant** dans un digraphe. | On oublie que la matrice d’adjacence donne les arcs sortants en ligne et les entrants en colonne. | Toujours vérifier : somme d’une ligne = $\deg^{+}$, somme d’une colonne = $\deg^{-}$. | | **Penser que BFS donne le plus court chemin en poids** dans un graphe pondéré. | BFS ne tient pas compte des poids, il minimise seulement le nombre d’arêtes. | Rappeler que pour les poids non négatifs, c’est l’algorithme de Dijkstra qui donne le plus court chemin pondéré. | | **Oublier de tester l’absence de cycle lors de l’ajout d’une arête dans Kruskal**. | On se contente de regarder le poids sans vérifier la création d’un cycle. | Utiliser une structure union‑find (ou vérifier l’appartenance à la même composante) avant d’ajouter chaque arête. | | **Interpréter mal $A^{2}$** : croire qu’il compte les chemins de longueur *au plus* $2$. | On confond la puissance avec la somme des puissances. | Rappeler la propriété : $(A^{k})_{ij}$ compte exactement les chemins de longueur *égale* à $k$. | | **Dire qu’un graphe eulérien nécessite seulement que tous les degrés soient pairs**, en omettant la condition de connexité. | On oublie que le graphe peut être décomposé en plusieurs composantes eulériennes séparées. | Toujours vérifier la connexité (ou au moins que toutes les arêtes appartiennent à une même composante non triviale). | | **Utiliser la matrice d’incidence pour un digraphe comme si elle était non orientée** (mettre des $1$ partout). | On oublie l’orientation des arcs qui impose $+1$ et $-1$. | Dans un digraphe, une colonne d’incidence contient exactement un $+1$ (tête) et un $-1$ (queue). | --- *Fin du cours.*