Exactitude de l'algorithme des composants fortement connectés pour un graphique dirigé

J'ai lu un algorithme pour trouver les composants fortement connectés dans un graphe orienté $G=(V,E)$. Il considère deux recherches DFS et la deuxième étape consiste à transposer le graphique d'origine$G^T$.

L'algorithme est le suivant:

1. Exécuter DFS sur $G$ (à partir d'un sommet de départ arbitraire), en gardant une trace des temps de fin de tous les sommets.
2. Calculer la transposition,
3. Exécuter DFS sur $G^T$, commençant au sommet avec le dernier temps de fi nition, formant un arbre enraciné à ce sommet. Une fois un arbre terminé, passez au sommet non visité avec l'heure de fin suivante et formez un autre arbre à l'aide de DFS et répétez jusqu'à ce que tous les sommets de$G^T$ sont visités.
4. Générez les sommets de chaque arbre formé par le deuxième DFS en tant que composant distinct fortement connecté.

Ma question est :

1. Quelle est l'intuition derrière cette étape intermédiaire du calcul d'une transposition?

Transposition de la matrice d'adjonction $A$ Est-ce que

$\qquad A[i,j] = 1 \iff A^T[j,i] = 1$.

En termes de graphiques, cela signifie

$\qquad u \to_G v \iff v \to_{G^T} u$.

En d'autres termes, la transposition inverse la direction de tous les bords. Notez que$G^T$ a les mêmes composants solides que $G$.

L'algorithme que vous regardez est celui de Kosaraju . Méfiez-vous de votre notion d '«heure de fin»: ce n'est pas l'heure à laquelle le nœud est visité, mais lorsque la recherche a traversé le sous-graphe accessible depuis celui-ci. Wikipedia propose d'utiliser une pile pour gérer cela, ce qui, je pense, est une bonne idée.

Pourquoi est-il correct d'utiliser $G^T$, intuitivement? Présumer$x$ est le premier nœud de sa forte composante visité par le DFS.

• Le DFS sur $G$ traverse toute la forte composante de $x$ après avoir atteint $x$, ainsi que d'autres via des bords qui quittent le composant.
• Puisque nous utilisons un ordre de pile pour mémoriser l'ordre des nœuds, $x$ est également le premier nœud de sa composante forte visité (comme nœud de départ, même) dans la deuxième phase.
• Depuis $G$ et $G^T$ ont les mêmes composants forts, tous les nœuds de la composante forte de $x$ sont visités lors de la recherche $G^T$ de $x$. Ces bords laissant le composant dans le premier point de phase dans la mauvaise direction$G^T$et ne sont donc pas suivies. Tous les bords quittant le composant de$x$ dans $G^T$ ont déjà été supprimés en raison de l'ordre de la pile.

Ma compréhension:

Lorsque vous exécutez DFS sur n'importe quel graphique DAG en gardant une trace des temps de finition, la seule chose que vous pouvez garantir est que le nœud récepteur n'obtiendra jamais le temps de finition le plus élevé [1] . Mais en même temps, le temps de finition le plus bas peut apparaître dans n'importe quelle composante du graphique . Par conséquent, cela rend le temps de finition le plus bas inutile.

Fondamentalement, le fait [1] est également inutile dans le graphe d'origine , mais il est très utile dans le graphe transposé . Lorsque vous transposez, cette déclaration conduit aux éléments suivants:

Dans le graphe transposé, le nœud qui était un puits dans le graphe non transposé obtiendra toujours le temps de finition le plus élevé .