Quiz Graphes orientés
Dans un graphe orienté représenté par une matrice d'adjacence, cette dernière est toujours symétrique.
Faux
Non c'est le cas seulement dans les graphes non orientés. Il y a une matrice symétrique si pour chaque arc existant on trouve son inverse.
Par exemple si l'arc 0 -> 1 existe, on doit avoir l'arc 1 -> 0
Pour un graphe creux, il est préférable de choisir une implémentation par listes d'adjacence
Vrai
Oui, et dans le cas d'un graphe pratiquement plein, une matrice d'ajacence
Le tri topologique peut être utilisé sur des graphes qui contiennent un ou plusieurs cycles
Faux
Le but du tri topologique est de faire pointer tous les arcs d'un graphe dans la même direction.
Ce n'est donc pas possible avec un graphe qui contient un ou plusieurs cycles
Le tri topologique correspond à un parcours en profondeur post-ordre
Faux
Il manque l'indication que le résultat de ce parcours est inversé!
Soit un graphe dont les listes d'adjacences sont les suivantes
0: 1, 3
1: 4
2: 0, 1, 3
3:
4:
5: 1, 4, 6
6: 1, 2Effectuez un tri topologique de ce graphe à partir du sommet 0
1) Donnez le résultat sous forme de liste (sans blanc entre les chiffres) 2) Si on part d'un autre sommet (hormis le 1 et le 4), va-t'on trouver le même résultat? Répondre par oui ou non
Séparez vos deux réponses par un espace ! Exemple: réponse_1 réponse_2
5620314 non
Les sommets v et w sont fortement connectés s'il existe un chemin de v à w et un chemin de w à v
Vrai
Un graphe G et son graphe inverse, obtenu en inversant le sens de ses arcs, n'ont pas les mêmes composantes fortement connexes
Faux
Les deux graphes ont les mêmes composantes fortement connexes
Soit un graphe G dont les listes d'adjacences sont les suivantes
0: 1, 4
1: 0, 2
2: 0, 3, 4
3: 0, 1
4: 3, 5
5: 6
6: 7
7: 5Effectuer l'Algorithme de Kosaraju-Sharir pour déterminer les composantes connexes de ce graphe
1) Indiquez le résultat du parcours post ordre inverse pour le graphe inverse de G 2) Indiquez la liste des composantes connexes sous la forme de liste sans espaces avec des virgules pour séparer les composantes connexes
Séparez vos deux réponses par un espace ! Exemple: réponse_1 réponse_2
57601342 567,01234
Soit un graphe G dont les listes d'adjacences sont les suivantes
1: 2,4,6
2: 3
3: 2, 6
4: 2, 5
5: 2, 3, 4
6: 3On parcourt ce graphe en profondeur itérativement à partir du sommet 1. Effectuez l’algorithme en précisant l’état de la pile, le traitement des sommets pré-ordonnés et post-ordonnés
Dans la première case de réponse, indiquez le résultat du parcours pré-ordre Dans la seconde case de réponse, indiquez le résultat du parcours post-ordre
Séparez vos deux réponses par un espace ! Exemple: réponse_1 réponse_2
123645 632541