Lire un graphe

Exercice · informatique (tronc commun des prépas scientifiques), chapitre 12 — Les graphes : modèle et représentations

Énoncé

Pour le graphe orienté $H$ du cours ( $S = {u, v, w, x}$ et $A = {(u, v), (v, w), (w, u), (v, x), (x, x)}$ ), donner les degrés entrants/sortants et tous les chemins de $u$ à $x$ de longueur inférieure ou égale à 3.

Corrigé

Degrés sortants : $d^{+} (u) = 1$ , $d^{+} (v) = 2$ , $d^{+} (w) = 1$ , $d^{+} (x) = 1$ (boucle). Somme $= 5$ .
Degrés entrants : $d^{-} (u) = 1$ , $d^{-} (v) = 1$ , $d^{-} (w) = 1$ , $d^{-} (x) = 2$ ( $v$ et boucle). Somme $= 5 = ∣ A ∣$ (vérifie le lemme).
Chemins de $u$ à $x$ :
Longueur 2 : $u \to v \to x$ .
Longueur 3 : $u \to v \to x \to x$ (via la boucle). Le graphe possède deux cycles : le cycle simple $u \to v \to w \to u$ et la boucle $x \to x$ .

Les autres exercices de ce chapitre Le cours du chapitre

Un blocage sur cet exercice ? Le tuteur d'Adloun guide par questions, sans donner la réponse.