Université de Mustapha Stambouli

Faculté des Sciences Exactes, Département d’Informatique

2année Licence Informatique

Théorie des Graphes - TD n°1

Exercice 1
Trois professeurs P1, P2 et P3 devront donner le même jour un certain nombre d’heures de cours à trois
classes C1, C2 et C3, tel que :
• P1 doit donner 2 heures de cours à C1 et 1 heure à C2 ;
• P2 doit donner 1 heure de cours à C1, 1 heure à C2 et 1 heure à C3 ;
• P3 doit donner 1 heure de cours à C1, 1 heure à C2 et 2 heures à C3.
Questions :
1. Comment représenter cette situation par un graphe ?
2. Quel type de graphe obtenez-vous ? Donner sa matrice d’adjacence
3. Combien faudra-t-il de plages horaires au minimum ?
4. Aidez-vous du graphe pour proposer un horaire pour ces professeurs.
Exercice 2
Six colis de poids respectifs 200kg, 500kg, 300kg, 600kg, 100kg, et 400kg arrivent, dans cet ordre
chronologique, vers une trémie de distribution. Indiquez le nombre minimum de fourgons nécessaires
pour distribuer ces colis, sachant que :
• ces colis doivent être chargés dans l’ordre chronologique de leurs arrivées ;
• un colis de poids supérieur ne peut être superposé sur un colis de poids inférieur.
Exercice 3
Un tournoi d’échecs oppose 6 personnes. Chaque joueur doit affronter tous les autres.
1. Construisez un graphe représentant toutes les parties possibles.
2. Quel type de graphe obtenez-vous ? Donner sa matrice d’adjacence
3. Si chaque joueur ne joue qu’un match par jour, combien de jours faudra-t-il pour terminer le
tournoi ?
4. Aidez-vous du graphe pour proposer un calendrier des matches.
Exercice 4
Sur un échiquier 3×3, les deux cavaliers noirs sont placés sur les cases a1 et c1, les deux
cavaliers blancs occupant les cases a3 et c3. Aidez-vous d’un graphe pour déterminer
les mouvements alternés des blancs et des noirs qui permettront aux cavaliers blancs
de prendre les places des cavaliers noirs, et vice versa. Les blancs commencent.
Exercice 5
Soient I1…In des intervalles de la droite réelle.

Un graphe d’intervalles est composé des sommets 1…n, tel que il y a une arête entre un sommet i et j
si 𝐼𝑖 ∩ 𝐼𝑗 = ∅, autrement dit les intervalles Ii et Ij ne se chevauchent pas.
1. Donnez le graphe d’intervalles des intervalles ci-dessus.
2. Quel type de graphe obtenez-vous ?
3. Donnez les différentes représentations informatiques de ce graphe.

Théorie des Graphes – TD 1 Page 1 sur 4

Exercice 6
Michel est invité par André (A) à un dîner de famille. Les premières phrases que Michel entend sont :
1) Béatrice (B) : « Bonjour ! Je suis la mère d’André »
2) Carole (C) : « Bienvenue ! Je suis la sœur du père d’André »
3) Daniel (D) : « Salut ! Je suis le fils unique de la sœur de la mère d’André »
4) Emile (E) : « Bonjour ! Je suis l’unique beau-frère du fils de Karl »
5) Fabienne (F) : « Mère de deux filles, je suis aussi la grand-mère maternelle de Daniel »
6) Gaston (G) : « Salut ! Je suis un des fils de Lucien et un des petits-fils de Fabienne »
7) Honoré (H) : « Je suis le grand-père paternel de Lucien »
8) Irène (I) : « Je suis l’unique belle-sœur de Lucien »
9) Joseph (J) : « Salut ! Je suis le neveu de Lucien et le petit fils de Karl »
10) Karl (K) : « Mon petit-fils m’a parlé de vous »
11) Lucien (L) : « Bienvenue dans cette maison ; je vous ai vu à l’instant parlé avec mon père »
Aidez Michel à représenter la situation familiale de ses hôtes au moyen d’un graphe.
Exercice 7
L’inspecteur Homes et son ami Watson enquêtaient sur l’affaire de l’explosition d’une bombe dans un
château qui a causé la mort de son propriétaire. Les sept ex-épouses du propriétaire interrogées par
Watson ont répondu comme suit :
1) Ann (A) a rencontré Betty (B), Charlotte (C), Félicia (F) et Georgia (G).
2) Betty a rencontré Ann, Charlotte, Edith (E), Félicia et Helen (H).
3) Charlotte a rencontré Ann, Betty et Edith.
4) Edith a rencontré Betty, Charlotte et Félicia.
5) Félicia a rencontré Ann, Betty, Edith et Helen.
6) Georgia a rencontré Ann et Helen.
7) Helen a rencontré Betty, Félicia et Georgia.
L’inspecteur Homes pense que l’épouse qui a déposé la bombe est celle qui a passé le plus de temps
dans le château. Aidez-vous d’un graphe pour déterminer le coupable.
Exercice 8
Le conseil d’une administration est composé de 7 membres M1 ,…, M7 . Chacun de ces membresinfluence
un certain nombre de ses collègues, conformément au tableau suivant :
Membre Influence
M1 M2, M3, M4, M5, M6, M7.
M2 Aucun
M3 M2
M4 M2, M3, M5, M7
M5 M2, M3
M6 M2, M3, M4, M5, M7.
M7 M2, M3, M5.
Modéliser cette situation sous forme d’un graphe.
Exercice 9
Soient les graphes suivants :
G2 a
G1 b e

a c d b

f
d
c

1. Donnez leurs matrices d’adjacence, et listes d’arcs

2. Donnez la liste des prédécesseurs, successeurs, voisins et degrés de chaque sommet.
3. Etudiez les propriétés de ces graphes (symétrie, connexité, forte connexité, circuits, etc )

Théorie des Graphes – TD 1 Page 2 sur 4

Exercice 10
Soit le graphe ci-contre :
1. Etudiez les propriétés de ce graphe (symétrie, 2
connexité, forte connexité, etc ). 1 3
2. Représentez ce graphe sous forme d’une matrice
d’adjacence, indiquez l’ensemble des successeurs
de chaque sommet. 4
3. Retrouvez le plus long chemin simple de G,
indiquez sa cardinalité. 7
4. Retrouvez la plus grande chaîne simple de G, 5
indiquez sa cardinalité. 6
5. Testez l’existence de circuits et cycles dans ce
graphe G.
Exercice 11
1. Montrez que la somme des degrés des sommets de n’importe quel graphe fini est paire.
2. Montrez que n’importe quel graphe simple possède deux sommets de même degré.
Exercice 12
Est-ce que les graphes suivants sont planaires ou bipartis ?
G1 G2

G3 G4

Exercice 13
Indiquez le type de chacun des graphes suivants :

Théorie des Graphes – TD 1 Page 3 sur 4

Exercice 14
Soit 𝐺 = (𝑋, 𝑈) un graphe simple d’ordre 𝑛 = |𝑋|.
1. Montrez que ∀𝑥 ∈ 𝑋, 𝑑(𝑥) ≤ 𝑛 − 1.
2. Montrez qu'il ne peut y avoir dans 𝐺 à la fois deux sommets 𝑥 et 𝑦 tel que 𝑑(𝑥) = 0 et 𝑑(𝑦) =
𝑛 − 1.
3. Montrez que ∑𝑥∈𝑋 𝑑(𝑥) = 2|𝑈|.
4. Montrez que 𝐺 a un nombre pair de sommets ayant des degrés impairs.
Exercice 15
Soit 𝐺 = (𝑋, 𝑈) un graphe simple biparti d’ordre 𝑛 = |𝑋| et de taille 𝑚 = |𝑈|.
1. Montrez que 𝑚 ≤ 𝑛2/4 .
2. En déduire qu’il existe un sommet 𝑥 tel que 𝑑(𝑥) ≤ 𝑛/2.
Exercice 16
Démontrez que si deux sommets 𝑥 et 𝑦 appartiennent à une même composante fortement connexe 𝐶,
alors tout chemin de 𝑥 à 𝑦 est entièrement inclus dans 𝐶.
Exercice 17
A) Soit le graphe ci-dessous, dont la matrice d’adjacence 𝑀 et la matrice des arcs 𝐴 sont données :
𝖥0 1 1 0 11
𝖥
∅ 𝑎𝑏 𝑎𝑐 ∅ 𝑎𝑒
1
b I0 1 1 0 0I I ∅ 𝑏𝑏 𝑏𝑐 ∅ ∅ I
𝑀 = I0 0 0 1 0I , 𝐴 = I ∅ ∅ ∅ 𝑐𝑑 ∅ I I𝑑𝑎.
I1 0 0 0 1I ∅ ∅ ∅ 𝑑𝑒I [𝑒𝑎 ∅ 𝑒𝑐
a c [1 0 1 0 0] ∅ ∅]

a) Calculer le produit matriciel classique 𝑀2 = 𝑀 × 𝑀.

e d b) Définissons le produit matriciel spécial 𝐴2 = 𝐴 ⊗ 𝐴
par :
• la loi de multiplication est remplacée par la concaténation de
deux arcs (puis de deux chemins) dont l’extrémité terminale du premier est l’extrémité initiale du
second, par exemple : (ab).(bc)=(abc) ; (ae).(cd)=ф ; (abc)(cd)=(abcd).
• la loi d’addition est remplacée par la réunion ensembliste, par exemple, l’addition des deux chemins
(abc) et (aec) consiste à mettre ces deux chemins dans la même case de la nouvelle matrice.
Vérifiez le produit suivant :
∅ 𝑎𝑏 𝑎𝑐 ∅ 𝑎𝑒 ∅ 𝑎𝑏 𝑎𝑐 ∅ 𝑎𝑒 𝑎𝑒𝑎 𝑎𝑏𝑏 𝑎𝑏𝑐, 𝑎𝑒𝑐 𝑎𝑐𝑑 ∅
𝖥 1 𝖥 1 𝖥 1
∅ 𝑏𝑏 𝑏𝑐 ∅ ∅ ∅ 𝑏𝑏 𝑏𝑐 ∅ ∅ ∅ 𝑏𝑏𝑏 𝑏𝑏𝑐 𝑏𝑐𝑑 ∅
I I I I I I
𝐴2 = 𝐴 ⊗ 𝐴 = I ∅ ∅ ∅ 𝑐𝑑 ∅I⊗I∅ ∅ ∅ 𝑐𝑑 ∅ I = I𝑐𝑑𝑎 ∅ ∅ ∅ 𝑐𝑑𝑒I
I𝑑𝑎 ∅ ∅ ∅ 𝑑𝑒I I𝑑𝑎 ∅ ∅ ∅ 𝑑𝑒I I𝑑𝑒𝑎 𝑑𝑎𝑏 𝑑𝑎𝑐, 𝑑𝑒𝑐 ∅ 𝑑𝑎𝑒I
[𝑒𝑎 ∅ 𝑒𝑐 ∅ ∅ ] [𝑒𝑎 ∅ 𝑒𝑐 ∅ ∅] [ ∅ 𝑒𝑎𝑏 𝑒𝑎𝑐 𝑒𝑐𝑑 𝑒𝑎𝑒]
c) Vérifiez que chaque valeur 𝑚𝑖𝑗2de 𝑀2 représente le nombre de chemins de longueur 2 (c-
à-d ayant 2 arcs) entre les sommets i et j.
d) Calculez le produit matriciel 𝑀3 = 𝑀2 × 𝑀.
e) Calculez le produit matriciel 𝐴3 = 𝐴2 ⊗ 𝐴
f) Vérifiez que chaque valeur 𝑚𝑖𝑗3de 𝑀3 représente le nombre de chemins de longueur 3
entre les sommets i et j.
B) Considérons le cas général d’un graphe 𝐺 = (𝑋, 𝑈) avec une matrice d’adjacence 𝑀. Montrez que la
valeur 𝑚𝑖𝑗𝑘 de la matrice 𝑀𝑘indique le nombre de chemins de longueur k entre les sommets i et j.
Exercice 18
Est-il possible de tracer les figures suivantes sans lever le crayon et sans passer deux fois sur le même
trait ? G1 G2 G3 G4 G5

Corrigé Exercice 2

Théorie des Graphes – TD 1 Page 4 sur 4