INSEA 2021 − 2022 Pr.
Ilyas Himmich
Théorie des graphes
Série d’exercices
Exercice 1 :
Un graphe orienté pondéré G(V, A) est donné par la matrice des distances A = aij , définie telle
que chaque élément aij représente une pondération sur un arc (i, j) ∈ A. Une case (i, j) vide dans
la matrice A signifie que (i, j) ∈
/ A.
- Dessinez le réseau G(V, A)
- Construire à, l’aide d’un d’un algorithme approprié, une arborescence de plus courts chemins
de racine a.
- En déduire les longueurs des chemins les plus courts reliant a à tous les autres sommets du
graphe.
- Définir le chemin le plus court pour aller de c à t.
Exercice 2 :
Confirmer (et prouver) ou infirmer (avec un contre-exemple) les propriétés suivantes :
- Un sous-chemin d’un plus court chemin est un plus court chemin.
- Un sous-chemin d’un plus long chemin est un plus long chemin.
Exercice 3 :
Un élève souhaite voir le soleil de minuit sur les fjords de Norvège. Il décide de se rendre à
Rana, ville située à proximité du cercle polaire. Après avoir fait le tour des compagnies aériennes,
il a recensé plusieurs connexions aériennes possibles lui permettant d’aller de Grenoble à Rana.
Voir le réseau qui s’en suit :
1
INSEA 2021 − 2022 Pr. Ilyas Himmich
- 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.
- Le réseau présenté ne tient pas compte des temps de transit à chaque escale, entre deux
vols. Comment les modéliseriez-vous ?
- Quel serait le chemin ayant le nombre minimal d’escales ?
- Son ami, un amateur de voyages, voudrait par contre profiter de son congé, relativement
plus long, pour visiter le nombre maximum possible de villes. Pouvez-vous l’aider à tracer
sa trajectoire ?
Exercice 4 :
Dans une ville, on veut construire 2 facilités, un château de distribution d’eau potable, et une
station d’épuration pour les eaux usées. La ville est composée de 5 quartiers : A, B, C, D et E, et
est équipée d’un réseau de canaux de transmission d’eau. Les coûts de transmission d’eau entre les
différents quartiers sont donnés dans le tableau suivant. Parallèlement à ce réseau, il existe un autre
réseau destiné à assurer la transmission des eaux usées (même connexions entre les quartiers). Par
contre, à cause des différences d’altitude entre les différents quartiers. La transmission des aux
usées exige un coût supplémentaire par rapport au coût d transmission d’eau, cette différence
de coûts est estimée à +20%. Une case vide dans le tableau des coûts signifie une connexion
inexistante. Le quartier A se situe sur une colline, les dirigeants de la ville ont alors décidé d’y
installer le château d’eau.
A B C D E
A 1
B 2 3
C 2 1
D 3 1 2
E 4 3
- Représenter le problème à l’aide d’une graphe orienté pondéré.
- Construire un réseau permettant de distribuer l’eau à moindre coût (coût total) à partir
du château vers les différents quartiers de la ville.
- L’endroit où installer la station d’épuration n’est pas encore décidé. Aider les dirigeants
de la ville à choisir un emplacement (un quartier) où construire cette station de façon à
minimiser les coûts totaux de transmission des eaux usées.
Exercice 5 :
Déterminer une base de cycles et une base de cocycles dans le graphe ci-dessous, en se basant
sur l’arbre dont les arêtes sont représentées en gras.
2
INSEA 2021 − 2022 Pr. Ilyas Himmich
Exercice 6 :
On organise un tournoi de tennis entre n joueurs africains. Chacun des n joueurs doit confron-
ter tous les autres joueurs, et chaque match se termine par une victoire d’un des joueurs (pas de
match nul).
Si on modélise le problème à l’aide d’un graphe G(V, A), tel que chaque sommet i ∈ V correspond
à un joueur, et un arc (i, j) ∈ A si le joueur i a vaincu le joueur j, sinon, l’arc d’orientation opposée
j(j, i) ∈ A.
Le comité organisateur du tournoi prétend que ce dernier permettra d’établir un classement des
joueurs participants, de telle sorte que le 1er joueur a vaincu le 2eme joueur, le 2eme à vaincu le
3eme , ..., le (n − 1)eme a vaincu le neme , sans écarter la possibilité que le 3eme ait vaincu le 1er par
exemple.
- Traduire en termes des notions vues dans le cours de théorie des graphes, la prétention du
comité organisateur.
- Confirmer ou infirmer la prétention.
Exercice 7 :
Afin de préparer une cérémonie de remise des diplômes à l’INSEA, un comité d’étudiants à
préparé le tableau de bord ci-dessous récapitulant les différentes tâches à accomplir, leurs durées
respectives en nombre de jours, ainsi qu’aux contraintes de précédence.
- Déterminer la durée totale minimale nécessaire pour organiser la cérémonie.
- Déterminer pour chaque tâche la date de démarrage au plus tôt et la date de démarrage
au plus tard en supposant que l’organisation commence le jour 0.
