Probleme – Rendre un graphe fortement connexe

1. Zéro arc : il n'y a rien à faire. Le test de l'exercice « Tester la forte connexité en deux parcours » le décide en $\Theta (n+m)$.

2. La minoration. Le quotient est acyclique et a au moins deux sommets. Une composante source n'a aucun arc entrant, une composante puits aucun arc sortant. Dans le graphe final, fortement connexe, tout sommet doit avoir au moins un arc entrant et un arc sortant.

Chaque source a donc besoin d'au moins un arc entrant nouveau : les arcs existants n'entrent pas dans une source, et un arc nouveau n'a qu'une extrémité d'arrivée, donc ne peut servir qu'à une seule source. Il faut au moins $s$ arcs. Le même raisonnement sur les puits en donne au moins $p$. Comme il s'agit du même ensemble d'arcs — un arc nouveau peut à la fois sortir d'un puits et entrer dans une source —, on obtient la minoration $\max (s,p)$ et non $s+p$.

Un quotient acyclique à au moins deux sommets a toujours au moins une source et un puits, donc $\max (s,p)\ge 1$ : le cas $0$ est bien celui de la question 1.

3. La construction. Appelons paire un couple $(S,P)$ formé d'une source et d'un puits tel que $P$ soit accessible depuis $S$. On commence par choisir $k$ paires $(S_1,P_1),\dots ,(S_k,P_k)$ deux à deux disjointes — aucune source ni aucun puits n'apparaît deux fois —, avec $k$ maximal. On ajoute alors les $k$ arcs qui les enchaînent en un cycle :

$$P_1\to S_2,P_2\to S_3,\dots ,P_{k-1}\to S_k,P_k\to S_1.$$

Il reste $s-k$ sources et $p-k$ puits non appariés. On raccroche chacun d'eux au cycle par un arc : pour une source restante $S$, un arc $P_1\to S$ ; pour un puits restant $P$, un arc $P\to S_1$. Coût total :

$$k+(s-k)+(p-k)=s+p-k.$$

Le graphe obtenu est fortement connexe. Depuis n'importe quel sommet, on descend le quotient — acyclique et fini — jusqu'à un puits ; de ce puits, un arc ajouté mène à une source du cycle ; et depuis une source du cycle on rejoint toute autre source en parcourant le cycle, puis toute composante en descendant. Tout sommet atteint donc $S_1$, et $S_1$ atteint tout sommet.

Il reste à savoir que $k=\min (s,p)$. C'est le point délicat, et c'est un théorème d'Eswaran et Tarjan que nous admettons : dans le quotient d'un graphe orienté, on peut toujours choisir $\min (s,p)$ paires source-puits deux à deux disjointes. Avec $k=\min (s,p)$, le coût devient $s+p-\min (s,p)=\max (s,p)$, et la minoration de la question 2 montre qu'on ne peut pas faire mieux.

Une remarque sur cet appariement : ce n'est pas un couplage biparti ordinaire, et le théorème de Hall de l'exercice « Hall et König » ne s'applique pas. Sur le quotient réduit à $S\to A$, $S\to B$ avec $A$ et $B$ puits, il n'y a qu'une source pour deux puits : $k=1=\min (1,2)$, et l'on retrouve bien $1+2-1=2=\max (1,2)$ arcs, à savoir $A\to S$ et $B\to S$.

4. La vérification. Sur $400$ graphes orientés tirés au hasard (de $2$ à $5$ sommets), on compare $\max (s,p)$ au nombre minimal d'arcs trouvé par recherche exhaustive — on essaie tous les ensembles de $1$ arc, puis de $2$, etc. : aucun désaccord.

Sur le graphe de la figure du chapitre — composantes $\{a,b,c\}$, $\{d,e\}$, $\{f\}$ avec le quotient $C_1\to C_2\to C_3$ —, on a $s=1$ (seule $C_1$ est source) et $p=1$ (seule $C_3$ est puits) : un seul arc suffit, et l'ajout de $f\to a$ referme le cycle. La force brute confirme.

Ce que le problème illustre. On a remplacé un problème sur $G$ par un problème sur son quotient, qui est acyclique donc beaucoup plus simple. C'est l'usage annoncé au début du chapitre : la décomposition en composantes fortement connexes est la manière standard de rendre acyclique un graphe qui ne l'est pas. Ici, elle transforme une question de connexité en un dénombrement de sources et de puits.