QCM - Algorithme de Kosaraju

QCM - Composantes fortement connexes et Kosaraju

Question 1. Une composante fortement connexe (CFC) d'un graphe orienté est :

Un ensemble maximal de sommets tel que pour toute paire u, v, il existe un chemin de u à v ET de v à uUn ensemble de sommets sans arc entre euxUn cycle passant par tous les sommetsUn ensemble de sommets de même degré

Question 2. Un ordre topologique d'un graphe orienté est :

Un ordre des sommets tel que pour tout arc (u, v), u apparaît avant vUn ordre des sommets par degré croissantUn ordre alphabétique des sommetsUn ordre quelconque des sommets

Question 3. Un graphe orienté admet un ordre topologique si et seulement si :

Il est connexeIl est fortement connexeIl est acyclique (DAG)Il a un nombre pair de sommets

Question 4. L'inverse d'un parcours postfixe d'un graphe acyclique donne :

Un ordre préfixeUn ordre topologiqueLes composantes connexesUn chemin hamiltonien

Question 5. L'algorithme de Kosaraju calcule les CFC en :

$O(n)$$O(n + p)$$O(n^2)$$O(n \cdot p)$

Question 6. La première étape de l'algorithme de Kosaraju consiste à :

Calculer le graphe transposé et faire un DFS pour obtenir l'ordre postfixe inverseTrouver tous les cycles du grapheTrier les sommets par degréCalculer les distances entre tous les sommets

Question 7. Le graphe transposé $G^T$ d'un graphe orienté $G$ est obtenu en :

Supprimant tous les arcsInversant le sens de tous les arcsAjoutant l'arc inverse pour chaque arcSupprimant les cycles

Question 8. Les CFC de $G$ et de son graphe transposé $G^T$ sont :

DifférentesLes mêmesComplémentairesInverses l'une de l'autre

Question 9. Le graphe quotient (ou DAG des CFC) est :

Toujours fortement connexeToujours acycliqueToujours un arbreToujours complet

Question 10. Dans un parcours DFS, l'ordre postfixe ajoute un sommet :

Au début de l'appel récursif (avant les voisins)À la fin de l'appel récursif (après les voisins)Quand il est découvert pour la première foisQuand tous ses voisins sont visités