Quiz: Introduction à la recherche opérationnelle et théorie des graphes — 14 domande

1. Quel est l’objectif pratique principal de la recherche opérationnelle ?

A. Décrire uniquement des phénomènes physiques sans choix à faire

B. Élaborer de meilleures décisions à partir de méthodes rationnelles

C. Classer des objets selon leur ancienneté

D. Remplacer toute décision humaine par le hasard

Answer: (B)

Spiegazione

La recherche opérationnelle vise à analyser et synthétiser des phénomènes d’organisation pour aider à prendre de meilleures décisions. Elle est donc directement liée à l’aide à la décision, et non à une simple description des phénomènes.

2. Quel repère historique est associé à la mise en place d’une solution pour désencombrer les lignes téléphoniques ?

A. Erlang en 1918

B. Monge en 1781

C. Fermat et Pascal en 1654

D. König en 1936

Answer: (A)

Spiegazione

En 1918, Erlang met en place une solution pour désencombrer les lignes téléphoniques en s’appuyant sur les travaux sur l’espérance mathématique. Les autres dates renvoient à d’autres étapes historiques du domaine.

3. Comment un graphe est-il défini dans la notation usuelle donnée ?

A. Par une matrice binaire des distances

B. Par un couple formé des chemins et des circuits

C. Par un ensemble d’angles et de longueurs

D. Par un couple formé de l’ensemble des sommets et de l’ensemble des arêtes

Answer: (D)

Spiegazione

Un graphe est noté G=(X,U), où X désigne l’ensemble des sommets et U l’ensemble des arêtes reliant ces sommets. Cette notation formalise les objets et leurs relations.

4. Quel problème célèbre a conduit Euler à être cité parmi les pères de la théorie des graphes ?

A. Le problème des sept ponts de Königsberg

B. Le désencombrement des lignes téléphoniques

C. La construction du diagramme de Hasse

D. Le problème des déblais et remblais

Answer: (A)

Spiegazione

Euler est associé au problème des sept ponts de Königsberg, qu’il a résolu en modélisant la situation par un graphe. Les autres propositions correspondent à d’autres domaines ou auteurs.

5. Dans un graphe orienté, que signifie l’arc s→t ?

A. On peut aller de t vers s

B. s et t sont forcément des sommets isolés

C. On peut aller de s vers t

D. s et t sont reliés sans direction

Answer: (C)

Spiegazione

Un arc s→t indique un déplacement possible de s vers t, avec une direction imposée par la flèche. Ce n’est pas une simple liaison sans sens comme dans un graphe non orienté.

6. Quelle formule donne la densité d’un graphe orienté comportant M arcs et N sommets ?

A. M/N

B. M+N

C. N²/M

D. M/N²

Answer: (D)

Spiegazione

La densité est définie par M/N² et elle est comprise entre 0 et 1. Une densité de 0 correspond à des sommets isolés, tandis qu’une densité de 1 correspond à un graphe complet.

7. Dans la représentation matricielle binaire d’un graphe orienté, que représente une entrée égale à 1 ?

A. Le fait que la colonne soit un prédécesseur de la ligne

B. Une boucle obligatoire sur le sommet

C. La possibilité d’aller de la ligne vers la colonne

D. L’absence totale de lien entre les sommets

Answer: (C)

Spiegazione

Dans la matrice binaire, la ligne correspond au sommet de départ et la colonne au sommet d’arrivée ; un 1 signifie qu’un déplacement de la ligne vers la colonne est possible. Un 0 indique l’absence de possibilité de déplacement.

8. Quand un sommet est-il appelé sortie ?

A. Quand il appartient à un circuit

B. Quand il a exactement deux successeurs

C. Quand il n’a aucun successeur

D. Quand il n’a aucun prédécesseur

Answer: (C)

Spiegazione

Un sommet est une sortie lorsque son ensemble de successeurs est vide, donc lorsqu’aucun arc ne part de lui. À l’inverse, l’absence de prédécesseur caractérise une entrée.

9. Qu’est-ce qu’un circuit dans un graphe ?

A. Un parcours qui évite tout sommet déjà vu

B. Une suite d’arêtes sans lien entre elles

C. Un chemin qui se referme en revenant au sommet initial

D. Une chaîne qui ne contient que des arêtes orientées

Answer: (C)

Spiegazione

Un circuit est un chemin dont l’extrémité terminale coïncide avec l’extrémité initiale, ce qui ferme le parcours. L’option sur l’évitement de sommets décrit plutôt un chemin élémentaire.

10. Quelle propriété caractérise une chaîne dans un graphe non orienté ?

A. Chaque arête doit avoir une direction imposée par une flèche

B. Le parcours doit revenir au sommet de départ

C. Chaque arête partage une extrémité avec la précédente et l’autre avec la suivante

D. Chaque sommet doit être visité exactement une seule fois

Answer: (C)

Spiegazione

Dans un graphe non orienté, une chaîne est une suite d’arêtes consécutives qui se touchent par une extrémité commune. Le retour au sommet initial définit plutôt un cycle.

11. Quelle propriété distingue une relation d’ordre sur un ensemble ?

A. Elle vérifie la symétrie, l’antisymétrie et la transitivité

B. Elle compare tous les éléments sans exception

C. Elle vérifie la réflexivité, l’antisymétrie et la transitivité

D. Elle vérifie seulement la réflexivité et la symétrie

Answer: (C)

Spiegazione

Une relation d’ordre doit être réflexive, antisymétrique et transitive. Les relations strictes comme « < » ne conviennent pas ici car elles ne sont pas des relations d’ordre dans ce cadre.

12. Quelle affirmation décrit correctement la borne supérieure d’une partie majorée ?

A. C’est un élément qui appartient forcément à la partie

B. C’est un majorant quelconque de cette partie

C. C’est le plus grand minorant de cette partie

D. C’est le plus petit majorant de cette partie

Answer: (D)

Spiegazione

La borne supérieure, notée sup(A), est le plus petit des majorants d’une partie majorée. À l’inverse, la borne inférieure est le plus grand des minorants.

13. Lors de la construction d’un diagramme de Hasse, que doit-on faire si l’on sait déjà que x ≤ y et y ≤ z ?

A. Ne pas tracer le segment entre x et z

B. Ajouter une boucle sur chacun des trois éléments

C. Placer x au-dessus de z

D. Tracer un segment entre x et z pour rappeler la transitivité

Answer: (A)

Spiegazione

Dans un diagramme de Hasse, on ne trace que les relations nécessaires : les relations déduites par transitivité sont supprimées. On ne trace pas non plus de boucle d’un point vers lui-même.

14. Comment sont placés les éléments dans un diagramme de Hasse par rapport à l’ordre représenté ?

A. Un élément plus grand est placé au-dessus d’un élément plus petit

B. Tous les éléments sont placés sur une même ligne sans hiérarchie

C. Un élément plus petit est placé au-dessus d’un élément plus grand

D. Les éléments sont placés uniquement selon leur ordre alphabétique

Answer: (A)

Spiegazione

Dans un diagramme de Hasse, on positionne un élément au-dessus d’un autre s’il est plus grand selon la relation d’ordre. Cette disposition visuelle permet de lire directement les comparaisons essentielles.