Quiz: Introduction aux graphes et leurs propriétés — 18 Fragen

1. Quel énoncé décrit correctement un circuit eulérien ?

A. Un parcours qui passe une seule fois par chaque sommet et peut s’arrêter n’importe où

B. Un parcours qui emprunte chaque arête exactement une fois et revient au point de départ

C. Un parcours qui évite toute arête déjà utilisée mais ne revient pas forcément au départ

D. Un parcours qui relie tous les sommets sans utiliser toutes les arêtes

Answer: (B)

Erklärung

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.

2. Quand un sous-graphe est-il dit couvrant ?

A. Quand il ne garde qu’un seul sommet

B. Quand il est connexe et sans cycle

C. Quand il contient toutes les arêtes du graphe initial

D. Quand son ensemble de sommets est égal à celui du graphe initial

Answer: (D)

Erklärung

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.

3. Que représente le degré d’un sommet ?

A. Le nombre total de sommets du graphe

B. Le nombre de cycles passant par ce sommet

C. Le nombre de composantes connexes du graphe

D. Le nombre d’arêtes incidentes à ce sommet

Answer: (D)

Erklärung

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.

4. Dans la modélisation du problème des ponts de Königsberg, quel élément devient une arête ?

A. Chaque point de départ choisi

B. Chaque chemin possible entre deux zones

C. Chaque pont

D. Chaque zone terrestre

Answer: (C)

Erklärung

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

5. Quelle relation est toujours vérifiée pour la somme des degrés des sommets d’un graphe ?

A. Elle est égale au carré du nombre d’arêtes

B. Elle est égale à deux fois le nombre d’arêtes

C. Elle est égale au nombre d’arêtes

D. Elle est égale au nombre de sommets

Answer: (B)

Erklärung

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.

6. Que préserve un isomorphisme de graphes ?

A. La structure d’adjacence entre sommets

B. Le degré maximal uniquement

C. Le nombre de composantes connexes uniquement

D. Le dessin des arêtes dans le plan

Answer: (A)

Erklärung

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.

7. Que fournit une liste d’adjacences pour chaque sommet ?

A. La position de ses coordonnées dans le plan

B. Le nombre de cycles qui le traversent

C. La liste de ses voisins adjacents

D. La totalité des arêtes du graphe en ordre croissant

Answer: (C)

Erklärung

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

8. Qu’est-ce qu’un sous-graphe induit par un ensemble de sommets Y ?

A. Un sous-graphe contenant seulement quelques arêtes entre les sommets de Y

B. Un sous-graphe contenant toutes les arêtes dont les extrémités sont dans Y

C. Un sous-graphe qui possède exactement les mêmes arêtes que le graphe initial

D. Un sous-graphe formé uniquement des sommets de plus grand degré

Answer: (B)

Erklärung

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é.

9. Quand dit-on qu’un graphe est planaire ?

A. Quand il peut être dessiné sans croisement entre deux arêtes quelconques

B. Quand il ne possède aucune arête multiple

C. Quand il est formé d’une seule composante connexe

D. Quand tous ses sommets ont le même degré

Answer: (A)

Erklärung

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.

10. Que signifie l’écriture G=(V,E) ?

A. V désigne les composantes et E les degrés

B. V désigne les arêtes et E les sommets

C. V désigne les chemins et E les cycles

D. V désigne l’ensemble des sommets et E l’ensemble des arêtes

Answer: (D)

Erklärung

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.

11. Dans une matrice d’adjacences, que signifie une entrée égale à 1 ?

A. Le sommet i est isolé

B. Les sommets i et j sont adjacents

C. Les sommets i et j appartiennent à des composantes différentes

D. L’arête entre i et j est orientée

Answer: (B)

Erklärung

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.

12. Quelle propriété caractérise un graphe simple ?

A. Il peut comporter plusieurs arêtes entre deux sommets

B. Il doit être dessinable sans croisement

C. Il peut comporter une boucle sur un sommet

D. Il n’a ni boucle ni arête multiple entre deux sommets

Answer: (D)

Erklärung

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é.

13. Quelle forme correspond à une chaîne dans un graphe ?

A. Une arête reliant plusieurs sommets à la fois

B. Une suite alternant sommets et arêtes

C. Un ensemble de sommets tous reliés deux à deux

D. Une suite de sommets sans arêtes

Answer: (B)

Erklärung

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.

14. Que faut-il pour que deux graphes soient isomorphes ?

A. Ils doivent être tous deux planaires

B. Ils doivent avoir exactement les mêmes noms de sommets

C. Ils doivent avoir le même nombre d’arêtes seulement

D. Il doit exister une bijection entre leurs sommets préservant l’adjacence

Answer: (D)

Erklärung

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.

15. Qu’est-ce qu’une arête dans un graphe ?

A. Un ensemble de sommets adjacents

B. Une paire ordonnée de sommets

C. Un sommet de degré maximal

D. Une liaison entre deux sommets sous forme de paire non ordonnée

Answer: (D)

Erklärung

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.

16. Quand une chaîne est-elle dite élémentaire ?

A. Quand tous ses sommets sont deux à deux distincts

B. Quand elle revient à son point de départ

C. Quand elle n’utilise aucune arête

D. Quand elle contient exactement deux arêtes

Answer: (A)

Erklärung

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.

17. Quand un graphe est-il connexe ?

A. Quand il peut être dessiné sans croisement

B. Quand il possède au moins un cycle

C. Quand il existe une chaîne entre chaque paire de sommets

D. Quand tous ses sommets ont le même degré

Answer: (C)

Erklärung

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é.

18. Comment définir une composante connexe ?

A. Comme un sous-graphe connexe maximal

B. Comme une arête reliant deux parties du graphe

C. Comme un ensemble de sommets de même degré

D. Comme un sous-graphe sans arête

Answer: (A)

Erklärung

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.