TD1 2024-2025

Notions de base de la théorie des graphes 1 G. Indus A/B

Théorie des graphes Pr. Med DHIB

Exercice 1
1. Quel est l’ordre du graphe G ?
2. Quel est le degré du sommet 3 ?
3. Quel est le sommet de plus haut degré ?
4. Trouver un sous-graphe de G complet ?
5. Le sous-graphe composé des sommets 1, 2, 3 et 5 est-il
connexe ?
6. Quels sont les sommets adjacents au sommet 5 ?
7. Quels sont les sommets adjacents au sommet 1 ?
8. Trouver si possible une chaine de longueur 5 d’extrémités 1 et 3 ?
9. Combien d’arêtes faudrait-il ajouter au sous graphe d’extrémités 1, 3, 4 et 5 pour qu’il soit complet ?
10. Trouver trois cycles d’extrémité 1.
11. Citer deux chaînes de longueurs différentes d’extrémités 2 et 5.

Exercice 2
Dessiner un graphe simple dont les sommets correspondent aux nombres réels de 1 à 9 et dont deux
sommets x et y seront reliés par une arête si et seulement si x+y est divisible par 3.
a. Quel est l’ordre de ce graphe ?
b. Quel est le degré du sommet 1 ? du sommet 9 ?

Exercice 3
Dessiner un graphe de 5 sommets A, B, C, D et E répondant aux conditions précisées dans le tableau ci-
contre :
Sommet Adjacent à (et seulement à)
A B, D, E, C
B A, C
C B, A, E, D
D A, C
E A, C

Exercice 4

Dire parmi les dessins suivants lesquels représentent le même graphe (isomorphes) :

1
Exercice 5
1. Pour chacun des graphes suivants, construire la matrice 𝑀 associée à chaque graphe et déduire le nombre
d’arêtes (arcs) à partir de 𝑀.

2. On considère le graphe associé à la matrice suivante

1 0 2 1
𝑀= 0 1 0 0
0 1 0 0
0 0 1 0
a. Ce graphe est-il orienté ? Justifier la réponse.
b. Quel est le nombre de ses arêtes ? Expliquer comment l’obtenir.
c
b. . A-t-il des boucles ? Si oui, lesquelles ? Justifier.
d. Représenter ce graphe

Exercice 6
1. Existent-t-ils des graphes simples dont les sommets ont pour degré les séquences suivantes ? Si la réponse
est oui, dessiner le graphe correspondant.
a) (0,0,1,2,2) b) (1,1,2,2,4) c) (1,2,3,3,5) d) (2,2,2,3,3)
e) (0,1,2,2,3) f) (0,1,2,3,4) g) (1,3,3,4,4) h) (3,3,3,3,4)
2. Dans chacune des suites suivantes, trouver un entier x, pour que la suite soit une suite de degré d’un
graphe simple connexe G :
a) (1,2,2,x,4) b) (1,2,2,2,x)
3. Donner le nombre d’arêtes d'un graphe simple d'ordre 6 ayant 4 sommets de degré 2 et deux sommets de
degré 4. Dessiner ce graphe.
4. Soit G un graphe d'ordre 10, de 11arêtes et dont les sommets sont de degré 2 ou 3. Donner le nombre de
sommets de degré 2 et de degré 3. Dessiner le graphe G.
5. Est-t-il possible de construire un graphe d'ordre 10 et de 50 arêtes ?
6. Un graphe d'ordre 4 peut-il avoir un sommet de degré 1 et 3 sommets de degré 3 ?
7. Existe t-il un graphe d'ordre 4 et de 7 arêtes ? Justifier votre réponse.
8. Construire le graphe biparti complet K2,3 et compter son nombre d’arêtes. Combien le graphe biparti
complet Km,n possède-t-il d’arêtes ? (m, n ≥ 1)

Exercice 7
Soit un graphe G de sommets A, B, C, D, E, F et M sa matrice d'adjacence, les sommets étant pris dans l'ordre
alphabétique
0 1 0 1 1 1
1 0 1 0 1 1
⎛0 1 0 0 0 1⎞
𝑀=⎜ ⎜1 ⎟
0 0 0 0 1⎟
1 1 0 0 0 1
⎝1 1 1 1 1 0⎠
1. Représenter le graphe G associé à la matrice M.
2. On donne

2
 8 11 5 7 9 11
11 8 7 5 9 11
⎛5 7 2 3 4 8 ⎞
𝑀 =⎜
⎜ ⎟
7 5 3 2 4 8 ⎟
9 9 4 4 6 11
⎝11 11 8 8 11 10⎠

a. Donner, en justifiant, le nombre de chemins de longueur 3 reliant C à D et écrire toutes ces chaînes.
b. Combien y a-t-il de cycles de longueur 3 partant et arrivant à B?
c. Combien y a-t-il de cycles de longueur 3 dans le graphe?

Exercice 8
Pour les graphes suivants :
1. Préciser l’ordre ainsi que le nombre d’arêtes de chaque graphe.
2. Les graphes suivants possèdent-ils des chaînes eulériennes ? des cycles eulériens ?

a) b) c)

d) e) f)

Exercice 9
Indiquer si possible pour le graphe ci-dessous :
1. Un cycle eulérien
2. Un cycle hamiltonien d’origine et d’extrémité 4.

Exercice 10
Un musée est constitué de 9 salles notées 𝐴, 𝐵, 𝐶, 𝐷,
𝐸, 𝐹, 𝐺, 𝐻 et 𝑆. Le plan du musée est représenté ci-
contre. Ainsi, un visiteur qui se trouve dans la salle 𝑆
peut atteindre directement les salles 𝐴, 𝐷 ou 𝐺. S’il se
trouve dans la salle 𝐶, il peut se rendre directement
dans la salle 𝐵 mais pas dans la salle 𝐹. On s’intéresse
au parcours d’un visiteur dans ce musée. Cette
situation peut être modélisée par un graphe, les
sommets étant les noms des salles, les arêtes
représentant les portes de communication.
1. Dessiner un graphe modélisant la situation décrite.
2. Est-il possible de visiter le musée, en empruntant chaque porte une fois et une seule ? Donner ce chemin.

3
Exercice 11
Colorier les figures ci-dessous
dessous sachant que deux régions voisines sont de couleurs différentes (deux régions
sont voisines si elles ont une ligne frontière commune) et trouver le nombre chromatique.

Exercice 12
Un amateur d’aquarium vient d’acheter des poissons dont certains ne peuvent cohabiter. Dans le tableau qui
suit les poissons sont numérotés de 1 à 9 et les incompatibilités sont indiquées par des croix.
1 2 3 4 5 6 7 8 9
1   
2   
3   
4  
5  
6    
7    
8  
9   
1. Combien d’aquarium faudra
faudra-t-il prévoir ?
2. Proposer deux répartitions possibles pour les poissons.
Exercice 13
On désire implanter 6 stations radio dans 6 endroits (Figure) dont les distances mutuelles en Km sont
données dans le tableau ci-dessous.
dessous. Si deux émetteurs sont trop proches, ils ne peuvent pas transmettre sur
la même fréquence à cause d’interférences.

En sachant que deux stations interfèrent si elles se trouvent à moins de 100 km l’une de l’autre, quel est alors
le nombre minimum de fréquences qu’il faut prévoir pour éviter toute interférence ?
A B C D E F
A 0 55 110 108 60 50
B 0 87 95 133 142
C 0 77 111 165
D 0 75 114
E 0 63