Théorie des graphes : Graphes nadia brauner uga
Télécharger PDFExercices de Graphe
Nadia Brauner
Université Grenoble Alpes
Table des matières
1 Graphes2
2 Chemins et cycles8
3 Arbres11
4 Plus courts chemins15
5 Coloration19
6 Couplage23
7 Flots25
8 Dessins de graphes321 1 Graphes
Modélisation
Exercice1 :Qui a tué le Duc de Dunsmore ?(d’après Claude Berge)
Un jour, Sherlock Holmes reçoit la visite de son ami Watson que l’on avait chargé d’enquêter
sur un assassinat mystérieux datant de plus de 10 ans. A l’époque, le Duc de Graphistan avait
été tué par l’explosion d’une bombe, qui avait également détruit le château de Graphistan où il
s’était retiré. Les journaux d’alors relataient que le testament, détruit lui aussi par l’explosion,
avait tout pour déplaire à l’une de ses 7 ex-femmes. Or, avant sa mort, le Duc les avait toutes
invitées à passer quelques jours dans sa retraite écossaise.
Holmes- Je me souviens de l’affaire ; ce qui est étrange, c’est que la bombe avait été fabriquée
spécialement pour être cachée dans l’armure de la chambre à coucher, ce qui suppose que
l’assassin a nécessairement effectué plusieurs visites au château !
Watson- Certes, et pour cette raison, j’ai interrogé chacune des ex-épouses : Ann, Betty,
Charlotte, Edith, Félicia, Georgia et Helen. Elles ont toutes juré qu’elles n’avaient été au
château de Graphistan qu’une seule fois dans leur vie.
Holmes- Hum ! leur avez-vous demandé à quelle période ont eu lieu leurs séjours respectifs ?
Watson- Hélas, aucune ne se rappelait les dates exactes, après 10 ans ! Néanmoins, je leur
ai demandé qui elles y avaient rencontré :
— Ann a déclaré y avoir rencontré Betty, Charlotte, Félicia, Georgia ;
— Betty a déclaré y avoir rencontré Ann, Charlotte, Edith, Félicia, Helen ;
— Charlotte a déclaré y avoir rencontré Ann, Betty, Edith ;
— Edith a déclaré y avoir rencontré Betty, Charlotte, Félicia ;
— Félicia a déclaré y avoir rencontré Ann, Betty, Edith, Helen ;
— Georgia a déclaré y avoir rencontré Ann, Helen ;
— Helen a déclaré y avoir rencontré Betty, Félicia, Georgia.
Vous voyez mon cher Holmes, ces réponses sont concordantes !
C’est alors que Holmes prit un crayon et dessina un étrange petit dessin. Puis, après moins
de 30 secondes, Holmes s’écria : “tiens, tiens ! Ce que vous venez de dire détermine de façon
unique l’assassin”.
Question 1 – Mais qui donc est l’assassin ?
Exercice2 :
Échange de cavaliers(Jean-Paul Davalan)
Pour résoudre ce casse-tête vous devez échanger les positions des deux cavaliers blancs avec
celles des deux noirs, en respectant évidemment les règles du déplacement du cavalier sur un
échiquier et en n’utilisant que les dix cases dessinées.2 Question 1 – Modéliser le problème à l’aide d’un graphe.
Question 2 – Utiliser cette modélisation pour résoudre ce casse-tête.
Question 3 – Y-a-t-il des cases inutiles ?
Exercice3 :Dans un tournoi d’échecs, chaque participant doit rencontrer tous les autres.
Chaque partie dure une heure. Déterminer la durée minimum du tournoi dans le cas où le
nombre de participant est 3, 4, 5 ou 6.
Exercice4 :
Trois missionnaires, venus évangéliser la population locale, voyagent avec trois
cannibales. Si les missionnaires sont en infériorité numérique par rapport aux cannibales, alors
ces derniers mangent les missionnaires... Les missionnaires et les cannibales veulent traverser
une rivière. Pour cela, ils disposent d’une barque, qui ne permet de transporter que deux
personnes à la fois d’une rive à l’autre.
Question 1 – Modéliser le problème à l’aide d’un graphe. Tout le monde peut-il traverser sans
qu’aucun missionnaire ne soit mangé ?
Notions de base
Exercice5 :
Dessiner tous les graphes à 3 et 4 sommets, à isomorphisme près.
Exercice6 :(N. Trotignon) Déterminer tous les graphes auto-complémentaires à 1, 2, 3, 4,
5, 6, 7 sommets. Pour les courageux : il y a 10 graphes auto-complémentaires à 8 sommets.
Les trouver.
Exercice7 :(N. Trotignon) Montrer qu’un graphe auto-complémentaire possède4aou4a+ 1
sommets. Réciproquement, montrer que pour toutail existe un graphe auto-complémentaire
sur4asommets, et un graphe auto-complémentaire sur4a+ 1sommets.
Exercice8 :
Une ligue de football contient 15 clubs. Pour des raisons de temps, on décide3 que chaque club ne jouera que la moitié des matchs possibles. Comment organiser le tournoi ?
(on pourra commencer par étudier le cas de 7 clubs).Degrés Exercice9 :Séquence de degrés
On dit que séquence de nombres entiers estréalisables’il existe un graphe dont les sommets
ont exactement les degrés de la séquence.
Question 1 – Pour chaque séquence qui suit, dites si la séquence est réalisable ou non. Si la
réponse est oui, dessinez un tel graphe et dire s’il est unique (à isomorphisme près), sinon justifiez
pourquoi il n’y a pas de tel graphe.
a.(1; 2; 2; 4; 5; 5)
b.(2; 2; 2; 2; 2; 2)
c.(1; 1; 1; 1; 1; 1)
d.(3; 3; 3; 3; 3; 5)
e.(2; 2; 2; 3; 3; 3)
f.(0; 2; 2; 3; 4; 5)
g.(5; 5; 5; 5; 2; 2)
Question 2 – Donnez des conditions nécessaires pour qu’une séquence soit réalisable. Sont-elles
suffisantes ?
Exercice10 :
Théorème d’Havel-Hakimi(N. Trotignon)
SoitGun graphe etd1 ≤d2 ≤...≤dn les degrés des sommets deG.
Question 1 – Montrer qu’il existe un grapheHsurV={v1 ,...,vn }, tel queNH (vn ) ={v n−d(vn ),...,v n−1
}et pour tout1≤i≤non adeg(vi ) =di .
Question 2 – On dit qu’une suite d’entiers(d1 ,...,dn )telle qued1 ≤d2 ≤...≤dn est une
séquence de degréss’il existe un graphe surnsommets de degrésd1 ,...,dn . Montrer qu’une suite
Sest une séquence de degrés si et seulement si ou bienS= (0)ou bien la suiteS′ définie ci-
dessous est une séquence de degré :S′ = (d′ 1,...,d ′n−1 )avecd′ i=d i
si1≤i≤n−dn −1etd ′i =di −1sin−dn ≤i≤n−1.
Exercice11 :
Jeux de mains
Le tout-Grenoble se retrouve lors du vernissage d’une exposition dans une galerie d’art contem-
porain locale. Certaines des personnes présentes au vernissage se connaissent, d’autres pas. La
plus élémentaire des politesses veut que les personnes qui se connaissent se serrent la main.
Deux personnes ne se connaissant pas ne se serrent pas la main.
Question 1 – Démontrer qu’il existe au moins deux personnes qui ont serré le même nombre demains. Exercice12 :Le professeur McBrain
Le professeur McBrain et son épouse Muriel donnent une surprise-partie à laquelle ils invitent
4 autres couples mariés. À l’arrivée, certaines paires de personnes se sont serrées la main (bien
sûr, aucun couple marié ne se serre la main). À la fin de la soirée, le professeur demande à4 chacune des 9 personnes, à combien de personnes elles ont serré la main au début de la soirée
et il obtient 9 réponses différentes.
Question 1 – À combien de personnes Muriel a-t-elle serré la main ?
Exercice13 :Dessinez un graphe3-régulier qui ne soit pas le graphe completK4 .
Exercice14 :Conseil municipal
Le conseil municipal d’une ville comprend 7 commissions, qui obéissent aux règles suivantes :
— Règle 1 : tout conseiller municipal fait partie de 2 commissions exactement ;
— Règle 2 : deux commissions quelconques ont exactement un conseiller en commun.
Question 1 – Combien y’a t-il de membres dans le conseil municipal ?
Exercice15 :
Sept étudiants partent en vacances. Ils décident que chacun enverra une carte
à trois autres. Est-il posible que chaque étudiant recoivent des cartes postales précisément de
la part des trois personnes auxquelles il en a envoyé ?
Exercice16 :
On a 13 PCs, mais seulement 6 imprimantes. On doit connecter directement
les PCs aux imprimantes de sorte que les utilisateurs de 6 PCs quelconques (parmi les 13)
puissent utiliser les 6 imprimantes simultanément. On peut évidemment réaliser une connexion
avec cette propriété avec 13x6 = 78 liaisons, mais quel est le nombre minimum de liaisons
nécessaires ?
Question 1 – Justifier ce minimum et donner une (ou plusieurs) réalisation.
Généralisez : On apPCs etqimprimantes (p≥q). Trouver une architecture minimale (avec
la propriété :qPCs quelconques peuvent utiliser lesqimprimantes simultanément).
Représentations des graphes
Exercice17 :
Question 1 – Représenter le graphe correspondant à la matrice d’adjacence suivante
0 1 0 0 1
1 0 1 1 0
0 1 0 0 0
0 1 0 0 1
1 0 0 1 0
Question 2 – Est-ce que les matrices suivantes sont les matrices d’incidence d’un graphe simple
non orienté. Si c’est le cas, représenter ce graphe. Sinon, donner la raison.M 1= 1 1 0 0
1 0 0 1
0 1 0 1 M 2= 0 1 0 1
1 0 1 1
1 1 1 0 5 M3 =
0 1 1 1
1 1 0 1
1 0 1 0 M 4= 0 1 1 0
1 1 1 1
1 0 1 1
Exercice18 :
(A. Parreau)
Dans chacun des exemples suivants, dites si la matrice utilisée peut être une matrice d’adja-
cence, d’incidence ou ne pas représenter un graphe. Dans les deux premiers cas, dessinez un
graphe correspondant, dans le dernier cas, justifiez pourquoi.M 1= 01 10 10 10 11 01 00 10 M2 = 0 11 01 01 01 10 10 11 0 M 3= 01 00 10 10 01 01 10 10 01 11 M4 = 0 11 00 10 01 01 00 01 01 00 10 01 10 Exercice19 :
On considère les deux représentations machine des graphes (simples, non orientés) vues en
cours, à savoir matrice d’adjacence et listes d’adjacence.
Question 1 – Pour chacune de ces deux représentations, donner un algorithme permettant de
déterminer si deux sommets donnési,jont au moins un voisin commun (autre queietjsiiet
jsont voisins).
Question 2 – Donner le temps de calcul de chacun de ces deux algorithmes. Discuter des cas dans
lesquels l’un de ces deux algorithmes est meilleur que l’autre.
Exercice20 :
(A. Parreau)
Chaque colonne du tableau suivant représente un graphe différent, avec une représentation
différente.
Dans chaque cas, on demande de répondre aux questions suivantes (sans passer par une autre
représentation).
1. Quelle représentation du graphe a-t-on ?
2. Quels sont les voisins du sommet 1 ?
3. Quel est le nombre de voisins du sommet 4 ?
4. Est-ce que 5 est un sommet isolé ?
5. Combien y-a-t-il d’arêtes dans le graphe ?
6. Est-ce que les sommets 3 et 4 sont adjacents ?6 1234 5
V={1,2,3,4,5}
E={12,34,15}
1 0 0 0
1 1 1 0
0 1 0 1
0 0 1 1
0 0 0 0
0 0 1 0 1
0 0 1 1 0
1 1 0 1 1
0 1 1 0 1
1 0 1 1 0
—1 : [2,3,4]
—2 : [1,3,4]
—3 : [1,2,4]
—4 : [1,2,3]
—5 : []1 23 45 6
Exercice21 :(A. Parreau)
Complétez le tableau suivant :
Définition ensemblisteReprésentation
graphique
Matrice adjacenceMatriced’inci-dence Liste d’adjacence12 345 V={1,2,3,4,5}
E={12,45,34,14,35}
0 1 1 1 1
1 0 1 1 1
1 1 0 1 1
1 1 1 0 1
1 1 1 1 0
1 0 0 0
1 1 1 0
0 1 0 1
0 0 0 1
0 0 1 0
—1 : [2,3,5]
—2 : [1,4]
—3 : [1,5]
—4 : [2,5]
—5 : [1,3,4]7 2 Chemins et cycles
Exercice22 :
Montrer qu’un graphe simple de degré minimum au moinskcontient une chaîne
élémentaire de longueurk.
Exercice23 :
SoitGun graphe simple dont exactement deux sommetsxetysont de degré
impair. Montrer qu’il existe une chaîne dansGdexày.
Exercice24 :SoitGun graphe simple ànsommets etmarêtes. Montrer que sim >1 2(n− 1)(n−2), alorsGest connexe.
Exercice25 :SoitGun graphe non orienté. Montrer qu’un moins un des deux graphes,G
ou son complémentaire, est connexe.
Exercice26 :
SoitGun graphe simple ànsommets tel que chaque sommet est de degré
supérieur ou égal àn 2
. Montrer queGest connexe.
Graphes eulériens
Exercice27 :Sans lever le crayon
(a)(b)(c)
Figure1 –
Question 1 – Quels dessins dans la Figure 1 peuvent être dessinés sans lever le crayon et sans
passer deux fois sur le même trait ?
Exercice28 :
Est-il possible de tracer une courbe, sans lever le crayon, qui coupe chacun des
16 segments de la figure suivante exactement une fois ?8 Exercice29 :
Question 1 – SoitGun graphe connexe non eulérien. Est-il toujours possible de rendreGeulérien
en lui rajoutant des arêtes ?
Question 2 – Combien d’arêtes au minimum doit-on rajouter à G pour le rendre Eulérien.
Exercice30 :Les dominos
On considère des dominos dont les faces sont numérotées 1, 2, 3, 4 ou 5.
Question 1 – En excluant les dominos doubles, de combien de dominos dispose-t-on ?
Question 2 – Montrez que l’on peut arranger ces dominos de façon à former une boucle fermée
(en utilisant la règle habituelle de contact entre les dominos).
Question 3 – Pourquoi n’est-il pas nécessaire de considérer les dominos doubles ?
Question 4 – Si l’on prend maintenant des dominos dont les faces sont numérotées de 1 àn, est-il
possible de les arranger de façon à former une boucle fermée ?
Exercice31 :
Carcasse de cube
On dispose d’un fil de fer de 120 cm. Est-il possible de préparer une carcasse de cube de 10
cm d’arête sans couper le fil ? Sinon, combien de fois au minimum faut-il couper le fil de fer
pour fabriquer cette carcasse ?
Exercice32 :Jeu de cartes(Matej Stehlik)
Dans un jeu de52 = 13×4cartes, chaque carte a une valeur(A,2,3,4,5,6,7,8,9,10,V,D,R)
et une couleur (♥,♦,♣,♠)
Question 1 – Quelle est la longueur maximale d’une suite de cartes qu’on peut construire à partir
d’un jeu de 52 cartes de façon à ce que deux cartes consécutives soient de la même valeur ou de la
même couleur, mais si on prend trois cartes consécutives quelconques, elles n’ont pas toutes trois
la même valeur ni la même couleur ? Par exemple,A♠,7♠,7♥,D♥est une suite qui respecte
cette règle.
Exercice33 :
Ramassage des poubelles
Voici le plan simplifié d’un quartier de Propreville. Une benne venant de l’usine d’incinération
doit vider les 70 conteneurs indiqués sur le croquis et revenir à l’usine.9 avenue (1000m)
avenue (1000m)avenue (750m)
avenue (750m)
avenue (1000m)
avenue (1250m)
rue (1000m)
rue (2250m)
rue (1750m)
La circulation sur les avenues et sur les rues est dans les deux sens. La vitesse du camion-benne
à vide (ou entre deux ramassages) est de 30km/h et il est le même dans les deux sens. Il faut
compter 30 secondes pour vider un conteneur. Chaque avenue a deux voies et il faut réaliser
le ramassage indépendamment de chaque coté, ce qui nécessite deux passages de la benne (un
dans chaque sens). Le ramassage sur les trois rues se fait des deux cotés en même temps.
Question 1 – Trouver le trajet optimal qui minimise le temps total du parcours nécessaire pour
ramasser toutes les ordures.
Exercice34 :
Peinture sur court
Vous possédez, dans votre jardin, un court de tennis et vous venez d’acheter une machine
pour peindre les lignes du court. Chaque ligne ne peut être peinte qu’une seule fois et vous
ne souhaitez pas déplacer trop souvent la machine sans peindre afin d’éviter les taches de
peinture dans votre magnifique pelouse.
Question 1 – Où commencez-vous à peindre et quel trajet choisissez-vous pour la machine ?
Exercice35 :Le digicode10 Un digicode possède 10 touches numérotées de 0 à 9. Le code fait 4 chiffres. On cherche à
deviner le code en tapant le minimum de touches. On tire parti du fait que le digicode ouvre
la porte dès que les 4 chiffres sont tapés. Quelle est la longueur minimale d’une suite de 0 et 9
telle que tout code possible de 4 chiffres apparait comme sous-suite de 4 éléments consécutifs ?
3 Arbres
Exercice36 :Arbres à6sommets
Trouver tous les arbres à6sommets.
Exercice37 :
Cycles dans un graphe et son complémentaire
SoitGun graphe dont le nombre de sommets est supérieur ou égal à5.
Question 1 – Montrer queGou
Gcontient un cycle.
Exercice38 :
SoitTun arbre comportant au moins 3 sommets de degré 1.
Question 1 – Montrer queTcontient au moins un sommet de degré au moins 3.
Exercice39 :
SoitFune forêt ayantccomposantes connexes etnsommets, avecc≥1etn≥1.
Question 1 – Donner le nombre d’arêtes deFen fonction decetn.
Exercice40 :La séquence de degrés d’un arbre est 5, 4, 3, 2, 1, ..., 1. Determinez le nombre
de ”1” dans la séquence.
Exercice41 :
(N. Trotignon)
Une étoile est un arbre surnsommets avec l’un des sommets adjacent auxn−1autres. Soit
Tun arbre surn≥2sommets. Montrer queTest connexe si et seulement siTn’est pas uneétoile. Arbre couvrants de poids minimum
Exercice42 :Le château d’eau :
Une communauté de commune veut desservir un ensemble de villages en eau potable à partir
d’un château d’eau placé dans l’un des villages. Selon des paramètres législatifs, géologiques,
etc., le coût d’installation des canalisations pour transporter l’eau est estimé pour certaines
paire de villages. Certains villages ne peuvent pas être reliés directement à cause du relief. On
suppose que les capacités des canalisations sont illimitées. Il faut déterminer un réseau qui
puisse acheminer de l’eau dans chaque village, et ce au moindre coût.11 Figure2 – Le château d’eau est représenté par le cyclindre, les disques étant les villages à
desservir. Les chiffres représentent les coûts de liaison entre deux villages.
Question 1 – Proposez une solution pour ce problème.
Exercice43 :
Monsieur le 9(GI)
Un opérateur téléphonique veut installer un nouveau réseau de communication haut débit
connectant les principales villes de France : Brignoud, Gières, Lans en Vercors, Monestier de
Clermont, Tullins et Uriage.
Les coûts de connexion entre 2 villes dépendent de la distance, du relief, des lignes déjà
existantes. Ils sont donnés dans le tableau suivant :GBLUTM G-582211B-74812 L-6713U-312 T-10M- Question 1 – Quelles connexions permettent de relier les villes à moindre coût ?
Exercice44 :(inspiré dePearls in Graph Theoryde N. Hartsfield et G. Ringel)
Dans le graphe du cube en dimension 3, on sait que quatre arêtes ont un poids de 1, quatre
arêtes ont un poids de 2 et quatre arêtes ont un poids de 3. Quelle est une répartition possible
des arêtes telle que le poids de l’arbre couvrant de poids minimum est 10. Même question si
ce poids est 11.
Exercice45 :
(inspiré dePearls in Graph Theoryde N. Hartsfield et G. Ringel)
Dans le graphe de la Figure ci-dessous, l’arbre couvrant de poids minimum a un poids de 17.
Réarranger les poids des arêtes afin que les arbres couvrants de poids minimum aient un poids
de 19.12 Exercice46 :Camion(J.-F. Hèche)
Le réseau ci-dessous représente une partie du réseau routier d’une ville. Les nœuds corres-
pondent aux carrefours, les arêtes aux routes que l’on suppose toutes à double sens et les
nombres sur les arêtes indiquent la hauteur maximale (en centimètres) qu’un véhicule peut
avoir s’il désire emprunter la route correspondante.
Un livreur désire se rendre du pointAau pointB. Pour ceci, il veut déterminer la hauteur
maximalex, en mètres, du camion qu’il peut utiliser.
Question 1 – Trouver manuellement la solution au problème du livreur.
Question 2 – Déterminer quel problème de la théorie des graphes permet de décider si le livreur,
ayant un camion de hauteurxmètres, peut effectuer sa livraison en utilisant uniquement les routes
du réseau donné.
Question 3 – Citer un algorithme permettant de résoudre le problème précédent.
Question 4 – Appliquer l’algorithme cité ci-dessus afin de déterminer la hauteur maximale du
camion pour que la livraison soit possible et donner un itinéraire réalisable.13 Exercice47 :Traductions
Un document important, rédigé en anglais, doit être traduit en huit autres langues : allemand,
danois, espagnol, français, grec, italien, néerlandais et portugais. Parce qu’il est plus difficile
de trouver des traducteurs pour certaines langues que pour d’autres, certaines traductions
sont plus chères que d’autres. Les coûts (en euros) sont indiqués dans la table ci-dessous.
de/àdan. néd. ang. fr. all. grec it. port. esp.dan.∗90 100 120 60 160 120 140 120
néd.90∗70
80 50 130 90120 80ang.100 70∗50 60 150 110 15090 fr.120
8050∗70 120 70100 60
all.605060
70∗120 80130 80
grec160 130 150 120 120∗100 170 150it.120 90
110 70 80 100∗11070 port.140 120 150 100 130 170 110∗50esp.120 8090
60 80 150 7050∗
On veut obtenir une version du document dans chaque langue à un coût total minimum.
Question 1 – Modéliser le problème comme un problème d’un arbre couvrant de poids minimum.
Décrire clairement le graphe.
Question 2 – Quelles traductions devront être faites afin d’obtenir une version dans chaque langue
à un coût total minimum ?
Exercice48 :
Découpe(Wojciech Bienia)
A l’aide d’une scie à découper les courbes, on doit découper les 10 profils placés sur un morceau
rectangulaire35×25de contre-plaqué comme l’indique le schéma ci-dessous.
Le problème consiste à trouver le tracé qui minimise la longueur totale de découpe réellement
effectuée, c’est-à-dire que les passages en arrière, les déplacements répétés par une ligne ou un
trou déjà découpés ne comptent pas comme une augmentation de la longueur. Pour découper14 un morceau placé à l’intérieur de la planche il faut obligatoirement commencer le déplace-
ment de la scie à partir du bord de la planche, pour des raisons techniques.Question 1 –
Présentez le problème général comme un modèle classique de la théorie des graphes et justifiez
cette modélisation.
Question 2 – Traitez l’exemple et proposez un plan optimal de découpe. Ce plan est-il unique ?
(justifier)
Question 3 – La partie restante (quadrillée) du contre-plaqué peut-elle être en plusieurs morceaux
à l’issue d’une découpe optimale ? Expliquez ce phénomène sur la base de la théorie des graphes.
4 Plus courts chemins
Exercice49 :
Application de l’algorithme de Bellman(J. Moncel)
On considère le graphe orienté ci-dessous.
Question 1 – Donner pour toutxdistinct desle poids d’un plus court chemin allant desàx.
Détailler toutes les étapes de calcul réalisées par l’algorithme de Bellman.
Question 2 – Donner pour toutxdistinct desle poids d’un plus long chemin allant desàx.
Détailler toutes les étapes de calcul réalisées par l’algorithme de Bellman.
Exercice50 :
Application de l’algorithme de Bellman(Zoltán Szigeti)
Donnerles plus courtschemins issus du sommets, et puisles plus longschemins, dans le
graphe orienté pondéré suivant.
Exercice51 :Adaptation de l’algorithme de Bellman(J. Moncel)15 Supposons que l’on dispose d’un graphenon orientéG= (V,E), dont les arêtes sont valuées
par une fonctionp:E→R. Soitsun sommet deG. On souhaite calculer le poids minimum
d’un chemin entresetxpour toutxdistinct des.
Question 1 – Expliquer comment transformerGen un graphe orienté de sorte à ce que l’algorithme
de Bellman vu en cours puisse résoudre le problème.
Question 2 – Quelle(s) condition(s) doit vérifier le grapheGpour que cet algorithme soit valide ?
Exercice52 :
Algorithme de Dijkstra(Zoltán Szigeti)
Question 1 – En appliquant l’algorithme de Dijkstra, indiquez sur la figure ci-dessous la longueur
des plus courts chemins issus du sommets, dans le graphe. Vous indiquerez sur les dessin toutes
les traces de l’algorithme.
Question 2 – Indiquez l’arborescence des plus courts chemins issus dessur le dessin suivant.
Exercice53 :Un élève de Polytech’Grenoble souhaite voir le soleil de minuit sur les fjords
de Norvège. Il décide soudain de se rendre à Rana, charmante ville située à proximité du
cercle polaire. Après avoir fait le tour de quelques compagnies aériennes, il a recensé plusieurs
connexions aériennes possibles lui permettant d’aller de Grenoble (Lyon St Exupéry) à Rana,
qu’il a représenté à l’aide du graphe suivant :
Question 1 – Notre voyageur n’ayant que très peu de jours de vacances, aidez-le à déterminer le
chemin le plus rapide pour se rendre de Grenoble à Rana.
Question 2 – Le graphe dessiné par notre voyageur n