Graphe acyclique orienté

Dans tout graphe orienté acyclique, il y a au moins un sommet d'où ne part aucune flèche. Sinon, partant n'importe où et suivant les flèches, on pourrait faire un chemin orienté contenant strictement plus de sommets que le graphe, c'est-à-dire une boucle.

Pour écrire la matrice d'adjacence, on numérote tous les sommets d'où ne part aucune flèche, $s_1,\dots,s_{k_1}$. Puis on les « efface », ainsi que toutes les arêtes qui aboutissent à l'un d'entre eux et on recommence : on numérote tous les sommets d'où ne part aucune flèche de ce nouveau graphe (ça veut dire : les sommets d'où les seules flèches qui partent aboutissent dans $\{s_1,\dots,s_{k_1}\}$) : ce sont les sommets $s_{k_1+1},\dots,s_{k_1+k_2}$. Puis on recommence. Avec cet ordre de sommets, la matrice d'adjacence devrait être strictement triangulaire supérieure.

à gaga : pas clôture transitive je veux dire que tu RAJOUTES une arête allant de x à y chaque fois qu'il existe un chemin y allant. Après avoir fait ça ton graphe est un ordre. Au besoin tu rajoutés encore des arêtes pour qu'il soit total. Et..... ça devient évident de la trigonaliser. Mais qui peut le plus peut le moins les arêtes sue tu as ajoutee s deviennent des .. Zéros dans la matrice.

C'est un excellent exemple du théorème que je rappelle sans cesse sur le forum: tout théorème est un cas particulier d'évidence. C'est d'autant plus dur à prouver que ce n'est pas assez général.

Et s'il n'y avait pas de matrice dans l'histoire ? J'attache un truc pour faire joujou (sic).