Introduction à la théorie des graphes - QCM sur les notions de base

Pour chaque QCM, vous devez cocher une ou plusieurs cases qui correspondent à une réponse correcte.

Lorsque vous aurez terminé tous les QCM, vous cliquez sur correction pour avoir le pourcentage de réponses justes pour l'ensemble des exercices et obtenir les bonnes réponses ainsi que des commentaires sur les propositions de réponses justes et/ou fausses.

QCM Notions de base

Parmi les éléments suivants, quels sont ceux absolument nécessaires pour définir un graphe orienté ?

	Sommets (ou points ou nœuds) Le plus petit graphe contient au minimum un sommet.
	Arêtes Les arêtes sont des arcs dont on ignore l'orientation. Il suffit donc d'avoir des arcs. Néanmoins, une arête correspond à un arc dans les deux sens et un ensemble d'arêtes peut également suffire si tous les arcs existent dans les deux sens.
	Arcs Seul le graphe vide ne contient aucun arc. Sans arc on ne pourrait donc définir qu'un seul graphe, le graphe vide !
	Boucles Les boucles ne sont pas obligatoires. Très souvent les graphes utilisés qui correspondent à des problèmes concrets ne contiennent pas de boucle.

Exercice

Parmi les éléments suivants, quels sont ceux absolument nécessaires pour définir un graphe non orienté ?

	Sommets (ou points ou nœuds) Le plus petit graphe contient au minimum un sommet.
	Arêtes Elles suffisent effectivement dans ce cas puisque l'on n'est plus intéressé par le sens des arcs.
	Arcs Le sens des arcs est inutile, néanmoins en oubliant le sens des arcs on obtient les arêtes. Donner les arcs peut suffire.
	Boucles Les boucles sont généralement sans intérêt dans le cas des graphes non orientés.

Diverses représentations d'un graphe

Cocher les cases a), b), c) et/ou d) lorsque les représentations par matrice en variables 0-1 et/ou par listes des points et des arcs correspondent à la représentation graphique donnée au dessus.

	Matrice en variable 0-1 a) Cela ne peut pas correspondre puisque tous les arcs existent dans les deux sens.
	Matrice en variable 0-1 b) Oui, les arcs qui existent correspondent bien dans les deux représentations.
	Liste des sommets et des arcs c) Oui, les arcs qui existent correspondent bien dans les deux représentations.
	Liste des sommets et des arcs d) Non, deux arcs ont pour extrémité 3, alors que deux arcs devraient avoir pour origine 3.

Diverses représentations d'un graphe non orienté

Cocher les cases a), b), c) et/ou d) lorsque les représentations par matrice en variables 0-1 et/ou par listes des points et des arêtes correspondent à la représentation graphique donnée au dessus.

	Matrice en variable 0-1 a) Oui, les arcs existent dans les deux sens. Il est à noter que l'on aurait pu ne représenter que la partie de la matrice supérieure à la diagonale.
	Matrice en variable 0-1 b) Non, les arcs doivent exister dans les deux sens.
	Liste des sommets et des arêtes c) Oui, car on donne une liste d'arêtes, sans se préoccuper de l'ordre des deux extrémités.
	Liste des sommets et des arêtes d) Oui, car on donne une liste d'arêtes, sans se préoccuper de l'ordre des deux extrémités.

Exercice

Dans le graphe suivant, quel est l'ensemble Γ(1) associé au sommet 1 ?

	Γ(1) = {2,3} Non, car 3 n'est pas un successeur de 1.
	Γ(1) = {1} Γ(1) ne peut pas contenir 1, puisqu'il n'y a pas de boucles en 1.
	Γ(1) = {3} Non, car 3 n'est pas un successeur de 1.
	Γ(1) = {2} Oui, 2 est le seul et unique successeur de 1.

Exercice

Dans le graphe suivant, quel est l'ensemble Γ^-1(1) associé au sommet 1 ?

	Γ^-1(1) = {2,3} Non, 2 n'est pas un prédécesseur de 1.
	Γ^-1(1) = {1} Γ^-1(1) ne peut pas contenir 1, car il n'y a pas de boucle en 1.
	Γ^-1(1) = {3} Oui, 3 est le seul et unique prédécesseur de 1.
	Γ^-1(1) = {2} Non, 2 n'est pas prédécesseur de 1.