Connexe, fortement connexe

Exercice · niveau 2 · informatique (MP2I/MPI), chapitre 13 — Le modèle des graphes

Énoncé

Pour chacun de ces graphes orientés, donner le nombre de composantes connexes et de composantes fortement connexes.

$a \to b \to c$ ;
$a \to b \to c \to a$ ;
le graphe du chapitre : $0 \to 1$ , $0 \to 2$ , $1 \to 3$ , $3 \to 2$ ;
$a \leftrightarrow b$ et $c \leftrightarrow d$ , sans lien entre les deux paires.

Corrigé

Mesuré par un algorithme de composantes fortement connexes :

graphe	connexes	fortement connexes	les composantes fortes
$a \to b \to c$	$1$	$3$	${a}, {b}, {c}$
$a \to b \to c \to a$	$1$	$1$	${a, b, c}$
$0 \to 1$ , $0 \to 2$ , $1 \to 3$ , $3 \to 2$	$1$	$4$	les quatre singletons
deux paires séparées	$2$	$2$	${a, b}, {c, d}$

Comment lire ce tableau. La connexité s'évalue sur le graphe non orienté sous-jacent : on efface les flèches et l'on compte les morceaux. Les trois premiers graphes sont d'un seul tenant, donc connexes.

La forte connexité, elle, exige un chemin dans les deux sens. Les trois premières lignes montrent l'écart : le graphe $a \to b \to c$ est connexe et a trois composantes fortes, chacune réduite à un sommet — on ne revient jamais en arrière. Le troisième graphe, un dag à quatre sommets, en a quatre : dans un graphe orienté acyclique, toutes les composantes fortes sont des singletons, puisqu'un cycle serait nécessaire pour en réunir deux sommets. La réciproque est vraie aussi, et c'est une caractérisation utile.

Deux repères à retenir.

Le nombre de composantes fortes est toujours supérieur ou égal au nombre de composantes connexes : chaque composante connexe se subdivise en composantes fortes, jamais l'inverse.
Il y a égalité exactement quand chaque composante connexe est fortement connexe. Ajouter un arc ne peut que diminuer le nombre de composantes fortes, ou le laisser égal.

En contractant chaque composante fortement connexe en un seul sommet, on obtient toujours un dag — le graphe des composantes —, ce qui ramène l'étude d'un graphe orienté quelconque à celle d'un acyclique. C'est le sujet du chapitre chap:graphes-avances.

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.