TP Python Théorie des graphes
UNIVERSITÉ DE DOSSO
Institut Universitaire de Technologie (IUT)
Filière : Informatique de Gestion Deuxième Année
FICHE DE TRAVAUX PRATIQUES
Théorie des Graphes avec Python
Durée : 10 heures Année académique : 20252026
Ob jectifs
À l'issue de cette séance de travaux pratiques, l'étudiant devra être capable de :
Représenter un graphe en Python ;
Manipuler les sommets et les arêtes d'un graphe ;
Mettre en ÷uvre les parcours en profondeur (DFS) et en largeur (BFS) ;
Déterminer certaines propriétés d'un graphe ;
Utiliser la bibliothèque NetworkX pour la modélisation et la visualisation des graphes ;
Résoudre un problème de plus court chemin.
Rappel théorique
Un graphe est un couple :
G = (V, E)
où :
V est l'ensemble des sommets ;
E est l'ensemble des arêtes reliant certains sommets.
Considérons le graphe :
V = {A, B, C, D, E}
E = {(A, B), (A, C), (B, D), (C, D), (D, E)}.
Exercice 1 : Représentation d'un graphe
On considère le graphe dé ni ci-dessus.
1
TP Python Théorie des graphes
Travail demandé
1. Représenter ce graphe sous forme de liste d'adjacence en Python ;
2. A cher les voisins du sommet D ;
3. Calculer le degré de chaque sommet ;
4. Déterminer le sommet de degré maximal.
Indication
1 graphe = {
2 'A ' :[ 'B ','C '] ,
3 'B ' :[ 'A ','D '] ,
4 'C ' :[ 'A ','D '] ,
5 'D ' :[ 'B ','C ', 'E '],
6 'E ' :[ 'D ']
7 }
Exercice 2 : Parcours en profondeur (DFS)
Le parcours en profondeur (Depth First Search ) consiste à explorer un graphe en
visitant récursivement les sommets adjacents.
Travail demandé
1. Écrire une fonction Python réalisant un parcours DFS à partir du sommet A ;
2. A cher l'ordre de visite des sommets ;
3. Véri er si le graphe est connexe.
Prototype suggéré
1 def dfs ( graphe , sommet , visites ) :
2 pass
Exercice 3 : Parcours en largeur (BFS)
Le parcours en largeur (Breadth First Search ) explore les sommets niveau par niveau.
Travail demandé
1. Écrire un programme Python réalisant le parcours BFS ;
2. A cher l'ordre de visite des sommets ;
3. Comparer le résultat obtenu avec celui du DFS.
2
TP Python Théorie des graphes
Indication
1 from collections import deque
Exercice 4 : Visualisation d'un graphe avec NetworkX
Installer au préalable les bibliothèques nécessaires :
1 pip install networkx matplotlib
Puis exécuter le programme suivant :
1 import networkx as nx
2 import matplotlib . pyplot as plt
3
4 G = nx . Graph ()
5
6 G. add_edges_from ([
7 ( 'A ','B ') ,
8 ( 'A ','C ') ,
9 ( 'B ','D ') ,
10 ( 'C ','D ') ,
11 ( 'D ','E ')
12 ])
13
14 nx . draw (G , with_labels = True )
15
16 plt . show ()
Travail demandé
1. A cher graphiquement le graphe ;
2. Déterminer le nombre de sommets ;
3. Déterminer le nombre d'arêtes ;
4. Calculer le degré de chaque sommet ;
5. Véri er si le graphe est connexe.
Exercice 5 : Plus court chemin
On considère le graphe pondéré suivant :
E = {(A, B, 4), (A, C, 2), (B, D, 5), (C, D, 1), (D, E, 3)} .
Travail demandé
1. Construire le graphe pondéré avec NetworkX ;
2. Déterminer le plus court chemin entre A et E ;
3
TP Python Théorie des graphes
3. Calculer la distance minimale entre ces deux sommets ;
4. Véri er le résultat à l'aide de l'algorithme de Dijkstra.
Exercice 6 : Application à un réseau informatique
On considère le réseau suivant :
Le routeur R1 est connecté à R2 et R3 ;
Le routeur R2 est connecté à R4 ;
Le routeur R3 est connecté à R4 ;
Le routeur R4 est connecté à R5 .
Travail demandé
1. Modéliser ce réseau par un graphe ;
2. Représenter graphiquement le graphe ;
3. Déterminer le nombre de sommets ;
4. Déterminer le nombre d'arêtes ;
5. Calculer le degré de chaque sommet ;
6. Déterminer un chemin reliant R1 à R5 .
Exercice 7 : Mini-pro jet
On souhaite modéliser le réseau social d'une promotion comportant les étudiants :
{A, B, C, D, E, F, G}.
Les relations d'amitié sont :
(A, B), (A, C), (B, D), (B, E), (C, F ), (E, G), (F, G).
Travail demandé
1. Construire le graphe correspondant ;
2. Représenter graphiquement le réseau ;
3. Déterminer les degrés des sommets ;
4. Identi er les étudiants les plus connectés ;
5. Déterminer un chemin entre A et G ;
6. Interpréter les résultats obtenus.
4
TP Python Théorie des graphes
Compte rendu
Le compte rendu devra comporter :
Les programmes Python réalisés ;
Les captures d'écran des résultats ;
Les graphes obtenus ;
Une conclusion de quelques lignes sur les applications de la théorie des graphes en
informatique de gestion.
Fin de la séance de Travaux Pratiques