Exercices corrigés — Recherche opérationnelle & graphes

La matrice d'adjacence $A$ est symétrique : $A_{ij}=1$ si $i$ et $j$ sont reliés.

Le degré d'un sommet est la somme de sa ligne dans $A$.

Lemme des poignées : $\sum_v\deg(v)=2\lvert E\rvert$.

$A=\begin{pmatrix}0&1&1&0&0\\1&0&1&0&0\\1&1&0&1&0\\0&0&1&0&1\\0&0&0&1&0\end{pmatrix}$ (symétrique, diagonale nulle car pas de boucle).

Sommes des lignes : $\deg=(2,2,3,2,1)$.

$\sum_v\deg(v)=2+2+3+2+1=10=2\times 5=2\lvert E\rvert$ ($\lvert E\rvert=5$ arêtes). Le nombre de sommets de degré impair ($2$ et $4$) est pair, comme attendu.

BFS : file d'attente, on visite tous les voisins avant d'aller plus loin.

DFS : pile (ou récursion), on plonge le plus loin possible.

Voisins de $0$ : $\{1,2\}$ ; de $2$ : $\{0,1,3\}$ ; etc.

File : $0$ ; on enfile ses voisins $1,2$ ; puis voisins de $1$ (rien de neuf), de $2$ : $3$ ; puis voisin de $3$ : $4$. Ordre : $0,1,2,3,4$.

On part en $0\to1\to2\to3\to4$ (à chaque étape le plus petit voisin non visité). Ordre : $0,1,2,3,4$ (identique ici).

Une composante connexe est un groupe maximal de sommets reliés entre eux.

Lancer un parcours depuis un sommet : il découvre toute sa composante.

Recommencer depuis un sommet non encore visité.

$0$ atteint $1$ et $2$ (et $1\sim2$) : première composante $\{0,1,2\}$.

$3$ n'est relié qu'à $4$ : seconde composante $\{3,4\}$. Tous les sommets sont couverts.

$2$ composantes connexes : $\{0,1,2\}$ et $\{3,4\}$. Le graphe n'est donc pas connexe.

Critère d'Euler : un chemin eulérien existe ssi le graphe connexe a $0$ ou $2$ sommets de degré impair.

Compter les sommets de degré impair de Königsberg.

Un circuit fermé exige $0$ sommet impair.

Les $4$ degrés $3,3,3,5$ sont tous impairs : $4$ sommets impairs. Or $4>2$.

Comme le nombre de sommets impairs ($4$) dépasse $2$, aucun chemin eulérien n'existe : la promenade est impossible (résultat d'Euler, $1736$, acte de naissance de la théorie des graphes).

Le cycle $C_4$ a tous ses degrés égaux à $2$ (pairs) : $0$ sommet impair $\Rightarrow$ un circuit eulérien existe (on en fait le tour).

Biparti $\iff$ $2$-coloriable $\iff$ aucun cycle de longueur impaire.

Tenter une $2$-coloration en alternant les couleurs le long du cycle.

Sur un cycle impair, l'alternance se contredit au bouclage.

Sommets $0,1,2,3$ en cycle. Colorier $0,2$ en A et $1,3$ en B : chaque arête relie A à B. Biparti : groupes $\{0,2\}$ et $\{1,3\}$.

Cycle $0-1-2-0$. On colorie $0$=A, $1$=B, puis $2$ doit différer de $1$ (donc A) et de $0$ (donc B) : contradiction. Le triangle (cycle de longueur $3$, impaire) n'est pas $2$-coloriable, donc pas biparti ($\chi(C_3)=3$).

Algorithme de Kahn : retirer un sommet de degré entrant nul, recommencer.

Degrés entrants : $0\!:\!0$, $1\!:\!0$, $2\!:\!2$, $3\!:\!1$, $4\!:\!1$.

Un cycle empêche tout sommet d'avoir un degré entrant nul à un moment.

Sommets sans prédécesseur : $0$ et $1$ — on les sort, ce qui libère $2$ ; puis $2$ libère $3$ et $4$. Ordre valide : $0,1,2,3,4$ (chaque arc $u\to v$ a $u$ avant $v$).

On crée le cycle $1\to2\to3\to1$. Plus aucun sommet de ce cycle n'atteint un degré entrant nul : l'algorithme bloque $\Rightarrow$ ce n'est plus un DAG, aucun tri topologique n'existe (le cycle est détecté).

Dijkstra fixe à chaque étape le sommet non traité de plus petite distance, puis relâche ses arcs.

Initialiser $d_0=0$, les autres $=+\infty$.

Relâcher $u\to v$ : si $d_u+w<d_v$, mettre à jour $d_v$ et le prédécesseur.

Fixe $0$ ($d=0$) : $d_1=4$, $d_2=1$. Fixe $2$ ($d=1$, le plus petit) : $d_1=\min(4,1+2)=3$, $d_3=1+5=6$. Fixe $1$ ($d=3$) : $d_3=\min(6,3+1)=4$. Fixe $3$ ($d=4$) : $d_4=4+3=7$. Fixe $4$.

$d=(0,3,1,4,7)$. Noter que passer par $2$ ($d_2=1$) bat l'arc direct $0\to1$ ($4$).

En remontant les prédécesseurs : $0\to2\to1\to3\to4$, coût $1+2+1+3=7$.

Dijkstra est exclu : il y a un poids négatif.

Bellman-Ford relâche toutes les arêtes $\lvert V\rvert-1=3$ fois.

Comparer le chemin $0\to2$ direct et $0\to1\to2$.

$d_0=0$. $d_1=4$, $d_2=\min(2,\;4-3)=1$ (via $0\to1\to2$), $d_3=1+2=3$.

L'arc $1\to2$ de poids $-3$ rend le détour $0\to1\to2$ ($4-3=1$) meilleur que l'arc direct $0\to2$ ($2$) — ce qu'un algorithme glouton positif ne verrait pas.

Floyd-Warshall calcule toutes les paires en $O(\lvert V\rvert^3)$ par programmation dynamique sur les sommets intermédiaires.

Pour $d(2,4)$ : chercher le meilleur trajet de $2$ à $4$.

Les arcs utiles : $2\to1\,(2)$, $1\to3\,(1)$, $3\to4\,(3)$.

Floyd-Warshall : $d(i,j)\leftarrow\min(d(i,j),\,d(i,k)+d(k,j))$ pour chaque sommet pivot $k$. Il fournit la matrice complète des distances.

Meilleur trajet $2\to1\to3\to4$ de coût $2+1+3=6$ (l'arc direct $2\to3\,(5)$ puis $3\to4\,(3)$ donnerait $8$).

Le tableau des prédécesseurs donne, pour chaque sommet, par où on l'a atteint au mieux.

Partir de la destination et remonter de prédécesseur en prédécesseur.

Inverser la liste obtenue.

$\text{pred}(4)=3$, $\text{pred}(3)=1$, $\text{pred}(1)=2$, $\text{pred}(2)=0$. On remonte $4\leftarrow3\leftarrow1\leftarrow2\leftarrow0$.

En inversant : $0\to2\to1\to3\to4$ (coût $7$).

Repérer le cycle entre $1$ et $2$ et calculer son poids total.

Si on peut tourner indéfiniment en diminuant le coût, la notion de plus court chemin s'effondre.

Bellman-Ford détecte une amélioration au $\lvert V\rvert$-ième tour.

Le cycle $1\to2\to1$ a pour poids $1+(-3)=-2<0$ : c'est un cycle de poids négatif, accessible depuis $0$.

En le parcourant encore et encore, on diminue le coût sans borne : il n'existe pas de plus court chemin (coût $\to-\infty$).

Une distance encore améliorée après $\lvert V\rvert-1$ tours signale ce cycle négatif : l'algorithme renvoie une erreur plutôt qu'un résultat faux.

Dijkstra « fixe » définitivement un sommet dès qu'il a la plus petite distance provisoire.

Cette décision suppose qu'aucun chemin futur ne pourra faire mieux.

Un arc négatif viole cette hypothèse.

Quand Dijkstra fixe un sommet $u$ de distance minimale $d_u$, il suppose qu'on ne pourra plus l'améliorer — vrai si tous les poids sont $\geq 0$ (tout détour ne fait qu'ajouter du poids positif).

Avec un arc négatif, un chemin plus long en arcs peut être moins cher et arriver après que $u$ a été fixé : la distance retenue est alors fausse. D'où l'usage de Bellman-Ford (qui n'exige pas $\geq 0$).

Trier les arêtes par poids croissant.

Ajouter chaque arête si elle ne crée pas de cycle (union-find).

S'arrêter à $\lvert V\rvert-1=4$ arêtes.

$01\,(2)$, $12\,(3)$, $14\,(5)$, $03\,(6)$, $24\,(7)$, $13\,(8)$, $34\,(9)$.

$01\,(2)$ ✓ ; $12\,(3)$ ✓ ; $14\,(5)$ ✓ ; $03\,(6)$ ✓ ($4$ arêtes, tous les sommets reliés). $24\,(7)$ créerait un cycle ($2\!-\!1\!-\!4$) — rejetée, etc.

$2+3+5+6=16$, avec $\lvert V\rvert-1=4$ arêtes.

Prim fait croître un arbre depuis un sommet de départ.

À chaque étape, ajouter l'arête la moins chère sortant de l'arbre courant.

Continuer jusqu'à couvrir tous les sommets.

Arbre $\{0\}$ : arête min sortante $01\,(2)$ $\Rightarrow\{0,1\}$. Min sortante $12\,(3)$ $\Rightarrow\{0,1,2\}$. Min sortante $14\,(5)$ $\Rightarrow\{0,1,2,4\}$. Min sortante $03\,(6)$ $\Rightarrow\{0,1,2,3,4\}$.

Poids $2+3+5+6=16$, identique à Kruskal : ici l'ACM est unique. Prim (glouton « par sommet ») et Kruskal (glouton « par arête ») sont tous deux optimaux.

Un arbre est connexe et sans cycle.

Un graphe connexe à $n$ sommets a au moins $n-1$ arêtes.

Ajouter une arête à un arbre crée un cycle.

Un arbre sur $n$ sommets a exactement $n-1$ arêtes : ici $5-1=4$. C'est le minimum d'arêtes pour rester connexe.

Toute arête supplémentaire relie deux sommets déjà connectés par l'arbre $\Rightarrow$ elle crée un cycle, et ce n'est plus un arbre.

Les dépendances forment un DAG ; on calcule les dates de début au plus tôt.

Date au plus tôt d'une tâche $=\max$ des dates de fin de ses prédécesseurs.

La durée du projet est le plus long chemin.

$A\!:\!0$, $B\!:\!0$ ; $C\!:\!\max(0+3,\,0+2)=3$ ; $D\!:\!3+4=7$ ; $E\!:\!3+4=7$.

$A\!:\!3$, $B\!:\!2$, $C\!:\!7$, $D\!:\!8$, $E\!:\!9$. Durée du projet $=\max=9$.

Le plus long chemin est $A\to C\to E$ ($3+4+2=9$). $D$ finit à $8<9$, hors du chemin critique.

Calculer les dates de début au plus tard (rétro-planning depuis la fin $9$).

Marge $=$ date au plus tard $-$ date au plus tôt.

Une tâche est critique si sa marge est nulle.

En remontant : $E\!:\!9-2=7$, $D\!:\!9-1=8$, $C\!:\!\min(8,7)-4=3$, $B\!:\!3-2=1$, $A\!:\!3-3=0$.

Marge $=$ (au plus tard) $-$ (au plus tôt) : $A\!:\!0$, $B\!:\!1$, $C\!:\!0$, $D\!:\!1$, $E\!:\!0$, soit $(0,1,0,1,0)$.

Marge nulle : $A,C,E$ (le chemin critique). $B$ et $D$ disposent de $1$ unité de battement.

Seules les tâches du chemin critique fixent la durée totale.

Accélérer une tâche à marge non nulle ne fait que consommer cette marge.

Le chemin critique est $A\to C\to E$ ; $B$ et $D$ ont une marge de $1$.

Raccourcir $B$ (marge $1$) ou $D$ (marge $1$) ne change pas la durée du projet : on entame leur battement, mais le plus long chemin $A\to C\to E=9$ reste inchangé.

Pour gagner du temps, il faut raccourcir une tâche critique ($A$, $C$ ou $E$). Attention : en réduisant le chemin critique, un autre chemin peut le devenir (le critique se déplace).