Aller au contenu

Ces exercices accompagnent le chapitre Graphes.

Arbres

Exercice

Soit \(T = (S, A)\) un graphe non orienté avec \(S \neq \emptyset\).

Montrer que les propriétés suivantes sont équivalentes :

  1. \(T\) est acyclique et connexe ;
  2. \(T\) est acyclique maximal (si on ajoute une arête il devient cyclique) ;
  3. \(T\) est acyclique et \(|A| \ge |S|-1\) ;
  4. \(T\) est connexe minimal (si on retire une arête il devient non connexe) ;
  5. \(T\) est connexe et \(|A| \le |S|-1\) ;
  6. il existe un unique chemin élémentaire entre deux sommets de \(T\).

On dit que \(T\) est un arbre.

Corrigé

\(6 \Rightarrow 1\) : il existe un chemin entre deux sommets quelconques donc \(T\) est connexe, et si \(T\) a un cycle, on en déduit deux chemins élémentaires distincts entre deux sommets de ce cycle en le coupant en deux.

\(1 \Rightarrow 6\) : soit \(x, y \in S\) deux sommets distincts. Si, par l'absurde, il existe deux chemins élémentaires différents entre \(x\) et \(y\), alors on peut considérer le dernier sommet \(z\) commun aux deux chemins avant qu'ils ne se séparent et le premier sommet \(t\) après \(z\) sur le premier chemin qui appartient aussi au second (il existe car les chemins se rejoignent forcément en \(y\)). On peut alors construire un cycle avec les deux sous-chemins de \(z\) à \(t\) qui n'ont, par construction, que \(z\) et \(t\) en commun. Ce cycle est de longueur au moins 3 : les deux sous-chemins ne peuvent pas être tous les deux réduits à l'arête \(z \smile t\) puisque les chemins se séparent après \(z\).

\(1 \Rightarrow 2\) : soit \(x \smile y\) l'arête qu'on rajoute. Comme \(T\) est connexe, il y a un chemin élémentaire de \(x\) à \(y\). En rajoutant la nouvelle arête à ce chemin, on obtient un cycle.

\(2 \Rightarrow 1\) : soit \(x, y\) deux sommets distincts. Si \(x \smile y \not\in A\), alors comme rajouter cette arête rendrait \(T\) cyclique, c'est que le cycle créé passe par cette arête et qu'il existe un chemin de \(x\) à \(y\) dans \(T\). Ainsi, dans tous les cas, \(x\) et \(y\) sont reliés. \(T\) est bien connexe.

\(1 \Rightarrow 4\) : soit \(x \smile y\) l'arête qu'on enlève. Comme \(T\) est acyclique, il ne peut exister de chemin élémentaire entre \(x\) et \(y\) sans cette arête, sinon ce chemin prolongé de l'arête omise serait un cycle dans \(T\).

\(4 \Rightarrow 1\) : si \(T\) avait un cycle, il suffirait de supprimer n'importe quelle arête du cycle pour qu'il reste connexe. Ainsi, \(T\) est acyclique.

Pour les deux équivalences restantes, c'est un peu plus compliqué. On commence par montrer un lemme.

Lemme. Si \(T\) est un arbre (au sens de 1) alors \(|A| = |S|-1\).

Preuve du lemme. Par récurrence forte sur \(|S|\). C'est direct si \(|S| = 1\) : il n'y a aucune arête.

Supposons le résultat vrai pour les arbres à moins de \(n \ge 2\) sommets et soit \(T\) un arbre ayant \(n\) sommets. Comme \(T\) est connexe et a au moins deux sommets, il possède une arête \(e = x \smile y\). Le graphe \(T' = T - e\) est non connexe car \(T\) est connexe minimal (\(1 \Rightarrow 4\)). Il a exactement deux composantes connexes, celle de \(x\) et celle de \(y\) : tout sommet \(z\) est relié à \(x\) dans \(T\) et, si le chemin élémentaire correspondant passe par \(e\), sa partie avant \(e\) relie \(z\) à \(x\) ou à \(y\) dans \(T'\). Ces deux composantes \(C_1 = (S_1,A_1)\) et \(C_2=(S_2,A_2)\) sont connexes et acycliques, donc des arbres ayant moins de \(n\) sommets, et l'hypothèse de récurrence s'applique : \(|S| = |S_1|+|S_2| = |A_1|+|A_2|+2 = |A|+1\) car \(A = A_1 \cup A_2 \cup \{ e\}\), réunion disjointe. On a bien validé la récurrence.

On en déduit donc \(1 \Rightarrow 3\) et \(1 \Rightarrow 5\), ainsi que le corollaire suivant, en appliquant le lemme à chaque composante connexe : si \(G = (S, A)\) est acyclique et a \(k\) composantes connexes, alors \(|A|=|S|-k\).

\(3 \Rightarrow 1\) : soit \(k \ge 1\) le nombre de composantes connexes de \(T\). On a \(|A|=|S|-k \ge |S|-1\), donc \(k \le 1\) et ainsi \(k = 1\) : \(T\) est connexe.

\(5 \Rightarrow 1\) : il existe \(A' \subset A\) tel que \(T' = (S,A')\) soit connexe et acyclique. En effet, on commence avec \(A' = A\) et tant que \(T'\) contient un cycle, on retire une arête du cycle de \(A'\), ce qui conserve la connexité. Ce processus termine car \(A'\) est fini. L'arbre \(T'\) obtenu vérifie \(|A'|=|S|-1 \ge |A|\) et donc \(A = A'\). Ainsi \(T\) était déjà acyclique.

Parcours en largeur

Note dans cette partie on va considérer un graphe orienté, mais la plupart des notions se transmettent directement au cas des graphes non orientés.

On considère le parcours en largeur écrit ainsi :

Algorithme : parcours en largeur

Entrées :

  • Un graphe \(G = (S,A)\)
  • Un sommet \(s \in S\) source du parcours

Déroulement :

  • On crée une file ne contenant que \(s\)
  • Tous les sommets sont non marqués.
  • On pose \(d(s) = 0\) et \(d(x) = \infty\) pour \(x \neq s\).
  • Tant que la file est non vide
    • On retire un sommet \(x\) de la file
    • Si \(x\) n'est pas marqué
      • On marque \(x\)
      • Pour chaque \(x \rightarrow y \in A\) où \(d(y) = \infty\)
        • On ajoute \(y\) dans la file
        • On pose \(d(y) = 1 + d(x)\)
  • On renvoie \(d\)

Dans la suite un sommet non marqué et dont \(d(x) = \infty\) est dit inconnu alors qu'un sommet non marqué et dont \(d(x) < \infty\) est dit découvert.

Définition

Soit \(G = (S,A)\) un graphe et \(x, y \in S\), on pose

\[ \delta(x,y) = \begin{cases} \infty & \text{s'il n'existe aucun chemin } x \leadsto y \\ \min \enscomp{ |\varphi|}{\varphi : x \leadsto y} & \text{sinon.} \end{cases} \]

Il s'agit de la plus petite longueur d'un chemin de \(x\) à \(y\) lorsqu'il en existe.

Question 1. Montrer que si \(x \in S\) et \(y \rightarrow z \in A\), alors \(\delta(x,z) \le \delta(x,y) + 1\).

Question 2. Soit \(G = (S,A)\) et \(s \in S\). On considère un parcours en largeur de source \(s\). À la fin du BFS, montrer qu'on a \(\forall x \in S, d(x) \ge \delta(s,x)\).

Question 3. On suppose que durant l'exécution du BFS, la file contient les sommets \((v_1,v_2,\dots,v_r)\) où \(v_1\) est la tête de la file (le sommet qui sera retiré en premier).

Montrer qu'on a \(d(v_r) \le d(v_1) + 1\) et que \(d(v_1) \le d(v_2) \le \dots \le d(v_r)\).

Question 4. En déduire que si \(v_i\) et \(v_j\) sont insérés dans la file lors de l'exécution et que \(v_i\) a été inséré avant \(v_j\), alors on a \(d(v_i) \le d(v_j)\) au moment où on insère \(v_j\).

Question 5. Soit \(G = (S,A)\) un graphe orienté et \(s \in S\) source à partir duquel on a effectué un BFS. Montrer que pour tout \(x \in S\), \(x\) est marqué si et seulement s'il est accessible depuis \(s\), et que dans ce cas on a \(d(x) = \delta(s,x)\) et le chemin emprunté par le parcours est un plus court chemin.

Un exemple de parcours

On considère le graphe orienté :

On effectue un parcours en profondeur récursif partant de \(a\) puis un parcours récursif partant de \(e\).

Question 6. Déterminer les temps d'entrée et de sortie sur une frise chronologique et classifier les arêtes (voir la partie Classification des arêtes du cours).

Corrigé

On suppose que les voisins sont examinés dans l'ordre alphabétique. Le parcours depuis \(a\) découvre tous les sommets sauf \(e, i, j, m, n\), que découvre ensuite le parcours depuis \(e\). On obtient le mot bien parenthésé

\[ (_a (_b (_f (_g (_c (_h (_d )_d (_l (_o (_k )_k )_o (_p )_p )_l )_h )_c )_g )_f )_b )_a (_e (_i (_n (_j (_m )_m )_j )_n )_i )_e \]

c'est-à-dire les temps suivants :

sommet \(a\) \(b\) \(c\) \(d\) \(e\) \(f\) \(g\) \(h\) \(i\) \(j\) \(k\) \(l\) \(m\) \(n\) \(o\) \(p\)
\(t_e\) 1 2 5 7 23 3 4 6 24 26 11 9 27 25 10 14
\(t_s\) 22 21 18 8 32 20 19 17 31 29 12 16 28 30 13 15

Classification des arêtes :

  • arêtes de liaison : \(a \rightarrow b\), \(b \rightarrow f\), \(f \rightarrow g\), \(g \rightarrow c\), \(c \rightarrow h\), \(h \rightarrow d\), \(h \rightarrow l\), \(l \rightarrow o\), \(o \rightarrow k\), \(l \rightarrow p\), \(e \rightarrow i\), \(i \rightarrow n\), \(n \rightarrow j\), \(j \rightarrow m\) ;
  • arêtes arrière : \(g \rightarrow a\), \(d \rightarrow c\), \(k \rightarrow h\), \(k \rightarrow l\), \(m \rightarrow i\) ;
  • arêtes avant : \(f \rightarrow l\), \(g \rightarrow k\) ;
  • arêtes transverses : \(e \rightarrow f\), \(j \rightarrow k\), \(n \rightarrow o\).

Le graphe a donc des cycles, puisqu'il y a des arêtes arrière. Ce même graphe sert d'exemple pour l'algorithme de Kosaraju dans le chapitre Algorithmique avancée des graphes.