QCM : Introduction à la recherche opérationnelle et théorie des graphes — 14 questions

Explication

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.

Explication

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.

Explication

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.

Explication

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.

Explication

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

Explication

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.

Explication

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.

Explication

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.

Explication

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.

Explication

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.

Explication

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.

Explication

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.

Explication

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.

Explication

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.