Fiche de révision : Introduction à la recherche opérationnelle et théorie des graphes

📋 Plan du Cours

1. Origines de la recherche opérationnelle
2. Théorie des graphes et vocabulaire
3. Graphes orientés, pondérés et densité
4. Successeurs, prédécesseurs et matrices
5. Chemins, chaînes et circuits
6. Relations d’ordre et bornes
7. Diagramme de Hasse et exercice

📖 1. Origines de la recherche opérationnelle

🔑 Notions clés & Définitions

• Recherche opérationnelle : La recherche opérationnelle est un ensemble de méthodes rationnelles pour analyser et synthétiser des phénomènes d’organisation afin d’élaborer de meilleures décisions.
• Aide à la décision : L’aide à la décision désigne l’objectif pratique des méthodes de recherche opérationnelle, orientées vers le choix le plus favorable.
• Optimisation : L’optimisation correspond à la recherche d’un meilleur résultat, comme réduire un trajet ou une ressource, à partir d’un cadre de décision.

📝 Points essentiels

• En 1654, Fermat et Pascal découvrent l’espérance mathématique, utile pour aborder des problèmes liés à l’incertain et aux probabilités.
• En 1781, Monge pose les bases des problèmes de transport via un mémoire sur les déblais et les remblais.
• En 1918, Erlang met en place une solution pour désencombrer les lignes téléphoniques en s’appuyant sur les travaux de Fermat et Pascal sur l’espérance mathématique.

💡 Astuce mémo

Optimisation = décision + méthode (GPS : trajet le meilleur).

📖 2. Théorie des graphes et vocabulaire

🔑 Notions clés & Définitions

• Théorie des graphes : La théorie des graphes étudie des objets reliés par des liens, souvent pour résoudre des problèmes de circulation, de parcours ou de relations.
• Euler : Euler est cité comme père ou l’un des pères de la théorie des graphes grâce à la résolution du problème des sept ponts de Königsberg avec un graphe.
• Sept ponts de Königsberg : Les sept ponts de Königsberg sont un problème célèbre consistant à traverser chaque pont une seule fois pour relier deux rives.

📝 Points essentiels

• Le problème des sept ponts de Königsberg demande de traverser la rivière en utilisant chacun des sept ponts exactement une fois.
• La théorie des graphes décrit des objets et leurs relations en représentant les objets par des nœuds (sommets) et les liens par des arêtes (ou arcs).
• Un graphe est noté $G=(X,U)$ où $X$ est l’ensemble fini des sommets et $U$ l’ensemble des arêtes reliant des sommets.

💡 Astuce mémo

Euler = ponts : on convertit un problème en graphe.

📖 3. Graphes orientés, pondérés et densité

🔑 Notions clés & Définitions

• Graphe non orienté : Un graphe non orienté permet de se déplacer entre deux sommets grâce à une arête, comme une route à double sens.
• Graphe orienté : Un graphe orienté impose une direction de déplacement, avec des arcs munis d’une flèche pour indiquer l’origine et le but.
• Graphe valué : Un graphe valué est un graphe où chaque arc porte une valeur numérique, utilisable par exemple pour distances ou temps.

📝 Points essentiels

• Dans un graphe orienté, un arc noté $s\to t$ signifie qu’on peut aller de $s$ vers $t$, et que $t$ est successeur de $s$ et $s$ est prédécesseur de $t$.
• La densité d’un graphe orienté avec $M$ arcs et $N$ sommets est $M/N^2$, comprise entre $0$ et $1$.
• Une densité de $0$ correspond à des sommets isolés (sans arcs) et une densité de $1$ correspond à un graphe complet où chaque nœud est relié à chaque autre.

💡 Astuce mémo

Densité = arcs sur carré de sommets : plus il y a d’arcs, plus le graphe est « rempli ».

📖 4. Successeurs, prédécesseurs et matrices

🔑 Notions clés & Définitions

• Successeurs : Les successeurs d’un sommet $A$ sont les sommets qui reçoivent un arc dont l’origine est directement $A$.
• Prédécesseurs : Les prédécesseurs d’un sommet $B$ sont les sommets qui envoient un arc dont l’extrémité terminale est $B$.
• Représentation matricielle : La représentation matricielle encode un graphe par une matrice binaire où une entrée vaut $1$ si un déplacement est possible de la ligne vers la colonne.

📝 Points essentiels

• Les successeurs de $A$ sont donnés par $\Gamma^{+}(A)=\{z\in X\mid (A,z)\in U\}$ et si $\Gamma^{+}(A)=\emptyset$ alors $A$ est une sortie.
• Les prédécesseurs de $B$ sont donnés par $\Gamma^{-}(B)=\{y\in X\mid (y,B)\in U\}$ et si $\Gamma^{-}(B)=\emptyset$ alors $B$ est une entrée.
• Dans la matrice binaire d’un graphe orienté, une ligne correspond à un sommet de départ et une colonne à un sommet d’arrivée, et un $1$ indique la possibilité d’aller ligne vers colonne.

💡 Astuce mémo

$\Gamma^+$ suit la flèche ; $\Gamma^-$ remonte la flèche.

📖 5. Chemins, chaînes et circuits

🔑 Notions clés & Définitions

• Chemin : Un chemin est une suite d’arcs où l’extrémité terminale de chaque arc coïncide avec l’extrémité initiale de l’arc suivant.
• Chemin Hamiltonien : Un chemin hamiltonien passe une fois et une seule fois par chacun des sommets d’un graphe.
• Circuit : Un circuit est un chemin qui se referme, car l’extrémité terminale coïncide avec l’extrémité initiale.

📝 Points essentiels

• Un chemin élémentaire ne passe pas plus d’une fois par chacun des sommets du chemin.
• Un circuit hamiltonien est un circuit qui passe une fois et une seule fois par tous les sommets, et le sommet terminal doit être un prédécesseur du sommet initial.
• Dans un graphe non orienté, une chaîne est une suite d’arêtes où chaque arête a une extrémité commune avec la précédente et l’autre avec la suivante.

💡 Astuce mémo

Circuit = chemin qui revient au point de départ.

📖 6. Relations d’ordre et bornes

🔑 Notions clés & Définitions

• Relation d’ordre : Une relation d’ordre sur un ensemble vérifie la réflexivité, l’antisymétrie et la transitivité.
• Majorant et minorant : Un majorant d’une partie $A$ est un élément $z$ tel que tout $x\in A$ soit inférieur ou égal à $z$, et un minorant vérifie l’inégalité inverse.
• Borne supérieure et borne inférieure : La borne supérieure est le plus petit majorant d’une partie majorée, et la borne inférieure est le plus grand minorant d’une partie minorée.

📝 Points essentiels

• La réflexivité impose $R(x,x)$ pour tout $x$ de l’ensemble, et l’antisymétrie impose que $R(x,y)$ et $R(y,x)$ donnent $x=y$.
• Sur les réels, les relations strictes ($a<b$ ou $a>b$) ne sont pas des relations d’ordre, alors que $a\le b$, $a\ge b$ et $a=b$ correspondent à une relation d’ordre.
• Si l’ensemble des majorants admet un plus petit élément, il est noté $\sup(A)$, et si l’ensemble des minorants admet un plus grand élément, il est noté $\inf(A)$.

💡 Astuce mémo

Majorant = grand, donc $\sup(A)$ ; minorant = petit, donc $\inf(A)$.

📖 7. Diagramme de Hasse et exercice

🔑 Notions clés & Définitions

• Diagramme de Hasse : Le diagramme de Hasse représente visuellement un ordre fini en plaçant les éléments et en reliant ceux qui sont directement comparables.
• Ordre fini : Un ordre fini est un ordre portant sur un nombre fini d’éléments, adapté à une représentation graphique de type Hasse.

📝 Points essentiels

• Pour construire un diagramme de Hasse, on place les éléments par points et on positionne un élément au-dessus d’un autre s’il est plus grand selon la relation d’ordre.
• On ne trace que les relations nécessaires, sans segment entre $x$ et $z$ si $x\le y$ et $y\le z$ existent déjà, et on ne trace pas de boucle d’un point vers lui-même.
• L’exercice demande d’identifier une matrice du graphe et de donner au moins un chemin, une chaîne et un cycle ainsi que la notation algébrique de $G.

📅 Repères chronologiques

📊 Tableaux de synthèse

Orienté vs non orienté

⚠️ Pièges & confusions fréquents

1. Confondre $\Gamma^{+}(A)$ et $\Gamma^{-}(B)$ : $\Gamma^{+}$ suit l’origine de l’arc tandis que $\Gamma^{-}$ suit l’extrémité terminale.
2. Croire qu’une relation stricte comme $a<b$ est une relation d’ordre : le cours précise que les strictes ne le sont pas.
3. Mélanger densité et nombre d’arêtes : la densité utilisée est $M/N^2$, pas $M/N$.
4. Confondre chemin et circuit : un circuit doit fermer le parcours en revenant au sommet initial.
5. Utiliser le vocabulaire orienté sur un graphe non orienté : le cours distingue chemin/circuit et chaîne/cycle.
6. Penser qu’un chemin élémentaire peut repasser par un sommet déjà vu : il ne doit pas rencontrer plus d’une fois un même sommet.

✅ Checklist Examen

1. Définir la recherche opérationnelle et l’idée d’aide à la décision associée.
2. Citer au moins un repère historique donné (par ex. -814, 1654, 1781, 1824, 1918, 1926 ou 1936) et ce qui s’y rapporte.
3. Définir un graphe $G=(X,U)$ et préciser ce que représentent $X$ et $U$.
4. Différencier graphe non orienté (arêtes) et graphe orienté (arcs avec flèche) pour le déplacement.
5. Écrire la forme de successeurs et prédécesseurs avec $\Gamma^{+}(A)$ et $\Gamma^{-}(B)$ et savoir ce que signifie l’ensemble vide.
6. Savoir reconnaître une sortie (pas de successeur) et une entrée (pas de prédécesseur) à partir de $\Gamma^{+}$ et $\Gamma^{-}$.
7. Donner la formule de densité d’un graphe orienté et interpréter les valeurs 0 et 1.
8. Décrire comment construire une représentation matricielle binaire : ligne = sommet de départ, colonne = sommet d’arrivée, et $1$ indique la possibilité d’aller de la ligne à la colonne.
9. Définir chemin, chemin élémentaire et chemin hamiltonien dans un graphe orienté.
10. Définir circuit, puis circuit hamiltonien et la contrainte sur le sommet terminal comme prédécesseur du sommet initial.
11. Définir chaîne, chaîne élémentaire, cycle et cycle élémentaire dans un graphe non orienté.
12. Interpréter les notions de relation d’ordre (réflexivité, antisymétrie, transitivité) et dire pourquoi les relations strictes ne sont pas des relations d’ordre.
13. Définir maximum, minimum, majorant, minorant, puis borne supérieure $\sup(A)$ et borne inférieure $\inf(A)$.
14. Expliquer la règle de construction d’un diagramme de Hasse (positionnement, arêtes de couverture, suppression par transitivité, pas de boucle) et l’appliquer à l’exercice.