Théorie des graphes : Examen graphes 13 2h sans documents
Télécharger PDFExamendegraphes - I3 - 2 heures - sansdocuments
Question 1 : Dantzig (8 Pts)
Soit un réseau R = (E; A; l) constitué d'un graphe (E; A) sans boucle et d'une application l qui, à chaque arc, fait correspondre un réel représentant sa longueur. Les sommets du graphe sont E = {1, 2, ..., n}.
On veut, pour tout couple de sommets (x; y), calculer la longueur d'un plus court chemin de x à y. On cherche de plus une méthode incrémentale, c'est-à-dire une méthode évitant de tout recalculer si l'on possède déjà une solution pour un réseau R0, et que l'on rajoute un sommet à ce réseau.
L'idée est de partir d'un réseau trivial à un seul sommet, et de rajouter un à un les sommets. On considère pour cela les ensembles Ek = {1, 2, ..., k} avec 1 ≤ k ≤ n.
La solution de notre problème pour le réseau Rk, sous-réseau de R construit sur les éléments de Ek, est une matrice Lk de taille k × k dont l'élément Lk(i; j) a pour valeur la longueur d'un plus court chemin de i à j dans Rk. S'il n'existe pas de chemin de i à j dans Rk, on pose Lk(i; j) = ∞. De plus, on a L1(1; 1) = 0. La solution du problème pour tout le réseau R est évidemment la matrice L = Ln.
a) Donnez, pour le petit réseau ci-dessous, la suite des matrices Lk.
7 3 2 12 3 1 14
b) Proposez une méthode pour calculer Lk, connaissant Lk-1. On supposera qu'il n'existe pas de circuit absorbant, c'est-à-dire de circuit de longueur strictement négative. Justifiez votre réponse.
c) Sur la base de cette méthode, proposez un algorithme pour calculer Ln, dans le cas où il n'y a pas de circuit absorbant.
d) Quelle est la complexité de calcul de votre algorithme ?
e) Comment modifier votre algorithme pour détecter la présence éventuelle d'un circuit absorbant ?
Question 2 : Arbitrage (3 Pts)
Un arbitrage est une combinaison d'opérations financières permettant de réaliser un bénéfice sans risque (en théorie du moins), en tirant parti d'imperfections susceptibles d'apparaître entre différents marchés.
Étant donné un ensemble de devises (par exemple : l'Euro, le Dollar, le Yen), une table de taux de change est un tableau T de dimension n × n dans lequel l'élément T[i; j] indique le nombre d'unités de la devise j que l'on obtient en échangeant une unité de la devise i. Par exemple, si T[1; 2] = 1,3, on obtient 1,3 dollars pour un euro.
L'existence d'un arbitrage dans une table de taux de change constitue un désordre dans le système monétaire, car il permet à un opérateur de s'enrichir indéfiniment par des simples jeux d'écriture : celui-ci peut en effet, par une suite bien choisie de conversions, récupérer plus que sa mise initiale et recommencer autant de fois qu'il le souhaite.
Supposons par exemple la table suivante :
1 2 3
T[1; 2] = 1,30 T[1; 3] = 1,25
T[2; 1] = 0,90 T[2; 3] = 1,10
T[3; 1] = 0,80 T[3; 2] = 1,00
En opérant la suite de changes 1 → 2 → 3 → 1 sur une somme d'un Euro, un spéculateur récupère 1,30 × 0,90 × 0,80 = 1,008 Euro.
a) Formulez précisément, dans le cadre des graphes, le problème de la recherche de l'existence d'un arbitrage dans une table de taux de change.
b) Proposez une transformation du problème permettant de s'amener à un problème connu.
c) Quel algorithme peut-on employer pour résoudre ce problème ? Quelle est sa complexité ? Attention : il n'est pas demandé ici de fournir un algorithme, mais seulement de citer le nom d'un algorithme connu.
Question 3 : Ornoir (4 Pts)
En qualité d'ingénieur expert, vous recevez un appel d'ordre de la compagnie pétrolière ALF qui cherche à résoudre le problème suivant. Son réseau de pipelines lui permet d'acheminer des unités de production aux raffineries 19 millions de barils de pétrole brut par mois. Les chemins du réseau sont trouvés en figure 1. Les nombres M[D] indiquent pour chaque pipeline, le débit transitant actuellement (D) et le débit maximal supporté par ce pipeline (M), en millions de barils par mois. La compagnie souhaite savoir s'il est possible d'augmenter le débit total, sachant que les unités de production et de raffinage sont capables d'augmenter leur rendement.
a) Quel algorithme, étudié en cours, permet de résoudre ce problème ? (Il n'est pas demandé d'écrire l'algorithme)
b) Montrez comment trouver une solution au problème de la compagnie, en exécutant une étape de l'algorithme. On précisera les données intermédiaires utilisées lors de cette exécution (utilisez la feuille jointe en page 4).
UNITÉS DE PRODUCTION UNITÉS DE RAFFINAGE
7 [2]
6 [6]
11 [11]
2 [0]
5 [5]
6 [4]
3 [3]
1 [1]
3 [3]
7 [6]
4 [3]
6 [4]
6 [6]
5 [5]
c) Montrez que la solution que vous proposez est optimale. Si ce n'est pas le cas, il peut être nécessaire d'exécuter une nouvelle étape de l'algorithme.
Question 4 : Graphe hamiltonien sans circuit (3 Pts)
On considère un graphe sans circuit G = (E; A), et sa partition en niveaux E0, ..., Ep.
a) Rappeler la définition de la partition en niveaux d'un graphe.
On rappelle que, pour tout i ∈ {0, ..., p}, pour tout x ∈ Ei, le rang r(x) du sommet x est égal à i, autrement dit la longueur maximale d'un chemin déterminant en x est i.
b) Montrer que, si tous les ensembles Ei (i ∈ {0, ..., p}) contiennent chacun exactement un sommet, alors G admet un chemin hamiltonien, et que celui-ci est unique.
c) Montrer réciproquement, si G admet un chemin hamiltonien, alors tous les ensembles Ei (i ∈ {0, ..., p}) contiennent chacun exactement un sommet.
Question 5 : Graphe quasi-fortement connexe (2 Pts)
Un graphe G = (E; A) est dit quasi-fortement connexe si, à tout couple de sommets (x; y), on peut associer un sommet z tel qu'il existe un chemin de x à z et un chemin de z à y.
a) Rappeler la définition d'une racine.
b) Montrer que, si G est quasi-fortement connexe, alors G possède une racine.
FAQ
1. Qu'est-ce qu'un circuit absorbant dans le contexte des graphes ?
Un circuit absorbant est un circuit (chemin fermé) dont la longueur totale est strictement négative, ce qui peut fausser les calculs de plus courts chemins dans un réseau.
2. Comment peut-on détecter un arbitrage dans une table de taux de change ?
Un arbitrage peut être détecté en transformant le problème en un graphe pondéré et en cherchant un cycle de longueur strictement positive.
3. Qu'est-ce qu'un chemin hamiltonien dans un graphe ?
Un chemin hamiltonien est un chemin passant exactement une fois par chaque sommet du graphe, sans répétition.