graph chap0

Qu’est-ce que la Recherche Opérationnelle (RO) ?

Un ensemble de méthodes mathématiques et algorithmiques d’aide à la décision visant le contrôle ou l’optimisation.

Quel est l’objectif général de la RO ?

Améliorer l’efficacité, réduire les coûts et mieux utiliser les ressources.

Quel est le but d’une démarche de RO ?

Chercher une solution rationnelle à un problème réel sous contraintes.

Quelle idée clé résume la RO ?

« Mieux faire avec moins » en construisant un modèle exploitable.

Quelle est l’origine historique de la RO selon le support ?

Son développement pendant la Seconde Guerre mondiale pour optimiser la logistique militaire.

Quels sont les domaines d’application de la RO en production/industrie ?

Planification, stocks, affectation de ressources et trajectoires de machines.

Quels sont les domaines d’application de la RO en transport/logistique ?

Livraisons, voyageurs, niveaux de vol et plus court chemin.

Quels sont les domaines d’application de la RO en télécommunications ?

Allocation de fréquences, routage et réseaux.

Quels sont les domaines d’application de la RO en gestion/finance ?

Banques, assurances, planification et optimisation des coûts.

Quels autres domaines d’application de la RO sont cités ?

Santé, éducation, environnement, marketing et économie.

Quelles sont les 5 étapes d’une démarche de RO ?

1) Formuler le problème, 2) Construire un modèle, 3) Choisir une méthode de résolution, 4) Résoudre, 5) Implémenter la solution.

Dans le problème du voyageur de commerce, que représentent les villes ?

Les sommets du graphe.

Dans le problème du voyageur de commerce, que représentent les déplacements ?

Les arêtes du graphe.

Dans le problème du voyageur de commerce, que représentent distance, temps ou coût ?

Les poids des arêtes.

Quel est l’objectif du voyageur de commerce selon le support ?

Trouver un meilleur parcours selon le critère choisi.

Comment note-t-on un graphe non orienté ?

G = (V, E).

Que représente V dans G = (V, E) ?

L’ensemble des sommets.

Que représente E dans G = (V, E) ?

L’ensemble des arêtes.

Qu’est-ce que l’ordre d’un graphe ?

Le nombre de sommets |V|.

Quand deux sommets sont-ils adjacents ou voisins ?

Lorsqu’ils sont reliés par une arête.

Qu’est-ce qu’un sommet isolé ?

Un sommet adjacent à aucun autre sommet.

Qu’est-ce qu’une arête incidente à un sommet ?

Une arête dont une extrémité est le sommet considéré.

Qu’est-ce qu’une boucle ?

Une arête reliant un sommet à lui-même.

Qu’est-ce qu’une arête multiple ?

Une des plusieurs arêtes reliant la même paire de sommets.

Qu’est-ce qu’un graphe simple ?

Un graphe sans boucle et sans arêtes multiples.

Qu’est-ce qu’un multigraphe ?

Un graphe où les arêtes multiples sont autorisées.

Qu’est-ce qu’un pseudographe ?

Un graphe pouvant contenir des boucles et/ou des arêtes multiples.

Qu’est-ce qu’un sous-graphe ?

Un graphe G'=(V',E') avec V' ⊆ V et E' ⊆ E.

Qu’est-ce qu’un graphe partiel ?

Un graphe avec les mêmes sommets que G, mais seulement une partie des arêtes.

Qu’est-ce qu’une chaîne ?

Une suite de sommets reliés par des arêtes.

Qu’est-ce qu’un cycle ?

Une chaîne fermée.

Quand un graphe non orienté est-il connexe ?

Lorsqu’il existe une chaîne entre toute paire de sommets.

Qu’est-ce qu’une composante connexe ?

Un sous-graphe connexe maximal d’un graphe non connexe.

Qu’est-ce qu’un graphe complet Kn ?

Un graphe où chaque sommet est relié à tous les autres.

Combien d’arêtes possède un graphe complet Kn ?

n(n−1)/2.

Qu’est-ce qu’un graphe biparti ?

Un graphe dont les sommets sont divisés en deux ensembles V1 et V2, toute arête reliant un sommet de V1 à un sommet de V2.

Quels types de graphes faut-il particulièrement savoir distinguer pour l’examen ?

Graphe simple, multigraphe et pseudographe.

Quelles notions de parcours faut-il particulièrement distinguer ?

Chaîne et cycle.

Quelles notions de connexité faut-il particulièrement distinguer ?

Connexe et non connexe.

Qu’est-ce que le degré d(v) d’un sommet dans un graphe non orienté ?

Le nombre d’arêtes incidentes au sommet v.

Comment une boucle compte-t-elle dans le degré d’un sommet ?

Elle compte double.

Qu’est-ce que le degré du graphe selon le support ?

Le degré maximum parmi tous les sommets.

Qu’est-ce qu’un graphe régulier ?

Un graphe dont tous les sommets ont le même degré.

Quelle est la formule du lemme des poignées de mains ?

Σ d(v) = 2|E|.

Que signifie le lemme des poignées de mains ?

La somme des degrés de tous les sommets vaut deux fois le nombre d’arêtes.

Qu’est-ce qu’un arc ?

Une arête orientée possédant un sens.

Pour un arc e=(u,v), quel est le sommet initial ?

u.

Pour un arc e=(u,v), quel est le sommet final ?

v.

Qu’est-ce qu’un successeur de vi ?

Un sommet vj tel que (vi,vj) ∈ E.

Qu’est-ce qu’un prédécesseur de vj ?

Un sommet vi tel que (vi,vj) ∈ E.

Qu’est-ce que le degré extérieur d⁺(v) ?

Le nombre d’arcs sortant du sommet v.

Qu’est-ce que le degré intérieur d⁻(v) ?

Le nombre d’arcs entrant dans le sommet v.

Comment calcule-t-on le degré total dans un graphe orienté ?

d(v) = d⁺(v) + d⁻(v).

Qu’est-ce qu’un chemin dans un graphe orienté ?

Une succession de sommets adjacents respectant le sens des arcs.

Qu’est-ce qu’un circuit ?

Un chemin fermé dont le sommet de départ est le sommet d’arrivée.

Quand un graphe orienté est-il fortement connexe ?

Pour tout u et v, il existe un chemin orienté de u vers v et de v vers u.

Quand un graphe orienté est-il faiblement connexe ?

Lorsqu’il devient connexe si l’on ignore le sens des arcs.

Quelle égalité relie les degrés entrants et sortants dans un graphe orienté ?

Σ d⁺(v) = Σ d⁻(v) = |E|.

Pourquoi Σ d⁺(v) = Σ d⁻(v) = |E| ?

Parce que chaque arc compte une fois comme sortie et une fois comme entrée.

Qu’est-ce qu’un graphe valué ?

Un graphe où chaque arête ou arc possède un poids.

Quels exemples de poids sont cités ?

Distance, coût, temps et capacité.

Qu’est-ce qu’une matrice d’adjacence pour un graphe simple non orienté ?

Une matrice n×n où A[i,j]=1 si vi et vj sont reliés, sinon 0.

Quelles sont les propriétés de la matrice d’adjacence d’un graphe simple non orienté ?

Elle est carrée, symétrique et sa diagonale est nulle s’il n’y a pas de boucles.

Comment obtenir le degré d’un sommet à partir de la matrice d’adjacence d’un graphe simple non orienté ?

En faisant la somme des éléments de sa ligne.

La matrice d’adjacence d’un graphe orienté est-elle forcément symétrique ?

Non.

Comment représente-t-on un graphe valué dans une matrice d’adjacence ?

A[i,j] contient le poids de l’arête/arc s’il existe, sinon 0.

Dans une matrice d’incidence sommets-arcs orientée, que représente une ligne ?

Un sommet.

Dans une matrice d’incidence sommets-arcs orientée, que représente une colonne ?

Un arc.

Pour un arc (i,j), quelle valeur est placée au sommet initial dans la matrice d’incidence selon le cours ?

+1.

Pour un arc (i,j), quelle valeur est placée au sommet final dans la matrice d’incidence selon le cours ?

−1.

Quelle valeur est placée ailleurs dans la colonne d’un arc de la matrice d’incidence ?

0.

Qu’est-ce qu’une liste d’adjacence ?

Pour chaque sommet, la liste de ses voisins ou de ses successeurs/prédécesseurs.

Quand une liste d’adjacence est-elle particulièrement efficace ?

Lorsque le graphe possède relativement peu d’arêtes.

Quelle est la complexité mémoire approximative d’une matrice d’adjacence ?

≈ n².

Pour quels graphes la matrice d’adjacence est-elle adaptée ?

Les graphes denses et les tests rapides d’adjacence.

Quelle est la complexité mémoire approximative d’une liste d’adjacence ?

≈ n+m, ou n+2m en non orienté.

Pour quels graphes la liste d’adjacence est-elle adaptée ?

Les graphes creux.

Quelle notation fondamentale faut-il savoir définir avant l’examen ?

G=(V,E).

Quelle formule de degré faut-il impérativement mémoriser ?

Σ d(v)=2|E|.

Quelles notions de parcours faut-il distinguer entre graphes non orientés et orientés ?

Chaîne/cycle pour non orienté ; chemin/circuit pour orienté.

Quels degrés faut-il savoir calculer dans un graphe orienté ?

d⁺(v) et d⁻(v).

Quelles représentations faut-il savoir construire et lire ?

Matrice d’adjacence et liste d’adjacence.

Quelle chaîne de raisonnement de la RO faut-il retenir ?

Problème → modèle → méthode → résolution → implémentation.