Tout graphe orienté acyclique possède une source

1. La démonstration. Soit $G$ un dag fini non vide. Considérons un chemin de longueur maximale $s_0\to s_1\to \cdots \to s_k$ — il en existe : les chemins d'un dag ne répètent aucun sommet, donc leur longueur est bornée par $n-1$, et l'ensemble des longueurs est une partie finie non vide de $\mathbb{N}$.

Affirmons que $s_0$ est une source. Sinon, il existerait un arc $w\to s_0$.

• Si $w$ n'est pas sur le chemin, alors $w\to s_0\to \cdots \to s_k$ est un chemin de longueur $k+1$ : contradiction avec la maximalité.
• Si $w=s_i$ pour un $i\ge 1$, alors $s_0\to \cdots \to s_i\to s_0$ est un cycle : contradiction avec l'acyclicité.

Donc $s_0$ n'a pas de prédécesseur.

Le même argument sur $s_k$ montre que tout dag possède aussi un puits, sommet de degré sortant nul. Vérifié sur des dag tirés au hasard : chacun présente au moins une source et au moins un puits.

2. Sans l'acyclicité, l'énoncé est faux. Mesuré sur $a\to b\to c\to a$ : aucune source, aucun puits — chaque sommet a un prédécesseur et un successeur. C'est bien l'acyclicité, et rien d'autre, qui fait le résultat.

Plus précisément : un graphe orienté fini est acyclique si et seulement si tout sous-graphe induit non vide possède une source. Le sens direct découle de ce qui précède, appliqué au sous-graphe ; la réciproque s'obtient en remarquant qu'un cycle est un sous-graphe induit sans source.

3. Ce à quoi il sert, et il sert beaucoup.

• Le tri topologique. Il fournit l'algorithme directement : prendre une source, l'émettre, la retirer avec ses arcs, recommencer. Le résultat précédent garantit qu'à chaque étape le graphe restant — encore un dag — a une source, donc que l'algorithme ne bloque jamais. Le programme fait explicitement « le lien entre accessibilité dans un graphe orienté acyclique et ordre » ; c'est ici (chapitre chap:parcours).
• La bonne fondation. Un dag fini est exactement un ordre partiel strict bien fondé sur ses sommets, et l'induction du chapitre chap:induction s'y applique. Un raisonnement par récurrence sur un dag part des sources ; une définition récursive part des puits.
• La détection de cycle. L'algorithme de tri topologique par degrés entrants — retirer les sommets de degré entrant nul jusqu'à épuisement — s'arrête avec des sommets restants si et seulement si le graphe a un cycle. Il détecte donc les cycles en $\Theta (n+m)$ tout en calculant l'ordre, ce qui est la manière usuelle de vérifier qu'un système de dépendances est cohérent : compilation d'un projet, feuille de calcul, ordonnancement de tâches.