QCM : Introduction aux graphes et leurs propriétés — 18 questions

Explication

Un circuit eulérien parcourt chaque arête exactement une fois et se referme sur le sommet de départ. Le fait de revenir au départ est essentiel, contrairement à un simple parcours de tous les sommets.

Explication

Un sous-graphe couvrant vérifie Y=X : il conserve tous les sommets du graphe initial. Il ne conserve pas nécessairement toutes les arêtes.

Explication

Le degré d’un sommet est le nombre d’arêtes qui lui sont incidentes. Il mesure donc combien d’arêtes touchent ce sommet.

Explication

Dans cette modélisation, les ponts sont représentés par des arêtes. Les zones terrestres deviennent, elles, des sommets.

Explication

Chaque arête contribue à deux degrés, un pour chacune de ses extrémités. La somme des degrés vaut donc deux fois le nombre d’arêtes.

Explication

L’isomorphisme conserve la structure d’adjacence : deux sommets adjacents restent adjacents après la bijection. Il ne se contente pas de préserver seulement le dessin.

Explication

Une liste d’adjacences donne, pour chaque sommet, les sommets auxquels il est adjacent. C’est une représentation non graphique du graphe.

Explication

Le sous-graphe induit contient toutes les arêtes du graphe initial ayant leurs deux extrémités dans Y. Il est aussi appelé sous-graphe engendré.

Explication

Un graphe planaire admet une représentation dans le plan où les arêtes ne se coupent pas. Cela ne concerne pas les boucles ou les arêtes multiples.

Explication

Dans l’écriture G=(V,E), V est l’ensemble des sommets et E l’ensemble des arêtes. C’est la notation standard d’un graphe.

Explication

Dans une matrice d’adjacences, la valeur 1 en position (i,j) indique que les sommets i et j sont adjacents. Les lignes et colonnes représentent les sommets.

Explication

Un graphe simple interdit les boucles et n’autorise au plus qu’une arête entre deux sommets. Le critère de non-croisement concerne plutôt la planarité.

Explication

Une chaîne est une suite du type sommet, arête, sommet, arête, sommet. Chaque arête relie deux sommets consécutifs de la suite.

Explication

Deux graphes sont isomorphes s’il existe une bijection entre leurs sommets qui conserve l’adjacence dans les deux sens. Les noms des sommets peuvent changer.

Explication

Une arête relie deux sommets et s’écrit comme une paire non ordonnée. L’ordre des deux extrémités ne compte pas.

Explication

Une chaîne élémentaire ne répète aucun sommet : tous les sommets qui la composent sont distincts deux à deux. Cela implique aussi qu’elle est simple.

Explication

Un graphe est connexe si l’on peut relier n’importe quelle paire de sommets par une chaîne. C’est la définition centrale de la connexité.

Explication

Une composante connexe est un sous-graphe connexe maximal, qu’on ne peut pas agrandir sans perdre la connexité. C’est le découpage d’un graphe non connexe.