informatique (tronc commun des prépas scientifiques) · Chapitre 12 · Application directe du cours

Lire un graphe

Les graphes : modèle et représentations · niveau 1 (application)

É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$ .

Exercices semblables

Les puissances de la matrice comptent les chemins corrigé
Sauver la matrice creuse — le dictionnaire d'arcs corrigé
Modéliser, c'est choisir — trois énoncés, trois graphes corrigé
Construire les fonctions de degré corrigé
De la liste d'arêtes aux deux représentations corrigé

Le cours du chapitre · Tous les exercices du chapitre