Graphe acyclique orienté
Bonjour,
J'aimerais montrer qu'il est possible de transformer la matrice d'adjacence d'un Graphe Acyclique Orienté en une matrice triangulaire inférieure par permutations des lignes et colonnes.
Je sais qu'une telle matrice est carrée et qu'elle ne possède que des zéros sur la diagonale car pas de cycles.
Après je bloque, pourriez vous me donner des pistes?
Merci d'avance.
J'aimerais montrer qu'il est possible de transformer la matrice d'adjacence d'un Graphe Acyclique Orienté en une matrice triangulaire inférieure par permutations des lignes et colonnes.
Je sais qu'une telle matrice est carrée et qu'elle ne possède que des zéros sur la diagonale car pas de cycles.
Après je bloque, pourriez vous me donner des pistes?
Merci d'avance.
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
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.
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.