Quiz Graphes non orientés Résumé
Soit un graphe dont les listes d'adjacences sont les suivantes
0: 1, 4
1: 0, 4, 5
2: 3, 6
3: 2, 4, 6
4: 0, 1, 3
5: 1
6: 2, 3Quel est l'ordre V de ce graphe ?
7
Soit un graphe dont les listes d'adjacences sont
0: 1, 4
1: 0, 4, 5
2: 3, 6
3: 2, 4, 6
4: 0, 1, 3
5: 1
6: 2, 3Quel est la taille E de ce graphe ?
8
Soit un graphe dont les listes d'adjacences sont les suivantes
0: 1, 4
1: 0, 4, 5
2: 3, 6
3: 2, 4, 6
4: 0, 1, 3
5: 1
6: 2, 3Effectuez un parcours en profondeur de ce graphe à partir du sommet 2 et donnez la liste des noeuds parcouru en pré-ordre (sans blanc entre les chiffres)
2340156
Soit un graphe dont les listes d'adjacences sont les suivantes
0: 1, 4
1: 0, 4, 5
2: 3, 6
3: 2, 4, 6
4: 0, 1, 3
5: 1
6: 2, 3Effectuez un parcours en profondeur de ce graphe à partir du sommet 0 et donnez la liste des noeuds parcouru en post-ordre (sans blanc entre les chiffres)
6234510
Soit un graphe dont les listes d'adjacences sont les suivantes
0: 1, 4
1: 0, 4, 5
2: 3, 6
3: 2, 4, 6
4: 0, 1, 3
5: 1
6: 2, 3Effectuez un parcours en largeur de ce graphe à partir du sommet 4 et donnez la liste des noeuds parcourus (sans blanc entre les chiffres)
4013526
Soit un graphe dont les listes d'adjacences sont
0: 1, 4
1: 0, 4, 5
2: 3, 6
3: 2, 4, 6
4: 0, 1, 3
5: 1
6: 2, 3Ecrivez sans espace la cinquième ligne de la matrice d'adjacence
1101000
Soit un graphe dont les listes d'adjacences sont
0: 1, 4
1: 0, 4, 5
2: 3, 6
3: 2, 4, 6
4: 0, 1, 3
5: 1
6: 2, 3Effectuez un parcours en largeur avec parents de ce graphe à partir du sommet 3
1) Indiquez le tableau des parents obtenu (sans blanc entre les chiffres) Exemple: 5312551 signifie que le sommet 5 est le parent du sommet 0, le sommet 3 est le parent du sommet 1, le sommet 1 est le parent du sommet 2 etc.
2) En partant du tableau obtenu, donnez la chaîne reliant le sommet 5 au sommet initial (3)
Séparez vos deux réponses par un espace ! Exemple: réponse_1 réponse_2
4433313 5143
Soit un graphe (attention différent du précédent) dont les listes d'adjacences sont
0: 2
1: 5
2: 0, 4, 6
3: 7
4: 2
5: 1
6: 2
7: 3Utilisez l'algorithme de calcul des composantes connexes avec un parcours en profondeur en pré-ordre de ce graphe à partir du sommet 4 afin de déterminer le nombre de composantes connexes
1) Indiquez le nombre de composantes connexes
2) Donnez la liste des noeuds parcourus (sans blanc entre les chiffres) S'il y a plus d'une composante connexe, séparez les composantes connexes avec une virgule
Séparez vos deux réponses par un espace ! Exemple: réponse_1 réponse_2
3 4206,15,37
Donnez la complexité en O() d'un parcours en largeur sur un graphe pour V sommets et E arêtes
1) Avec une représentation par Matrice d'adjacence 2) Avec une représentation par Listes d'adjacence
Séparez vos deux réponses par un espace ! Exemple: réponse_1 réponse_2
O(V*V) O(V+E)
Vrai ou faux Une chaîne Eulérienne ne passe que par des sommets de degré pair
Faux
Vrai ou faux Un cycle Eulérien passe une et une seule fois par chaque arrête et un cycle Hamiltonien passe une et une seule fois par chaque sommet
Vrai