LST Génie Logiciel, S5 FST Errachidia A-U 2024/2025
Exercice 1 : Représentation d’un graphe
Considérez l’ensemble des sommets V = {A, B, C, D} et les arêtes:E = {{A, B}, {B, C}, {C, D}, {A, D}}.
1. Représentez ce graphe sous forme de liste d’adjacence.
2. Dessinez ce graphe.
3. Écrivez la matrice d’adjacence associée à ce graphe.
Exercice 2 : Degrés des sommets
Soit le graphe non orienté suivant :
V = {A, B, C, D, E}, E = {{A, B}, {A, C}, {B, D}, {C, D}, {D, E}}
1. Déterminez le degré de chaque sommet.
2. Vérifiez que la somme des degrés est égale à deux fois le nombre d’arêtes.
3. Ajoutez une arête pour transformer le graphe en un graphe connexe si nécessaire.
Exercice 3 : Graphe orienté
Considérez le graphe orienté défini par les sommets V = {1, 2, 3, 4} et les arcs:
A = {(1, 2), (2, 3), (3, 4), (4, 1), (2, 4)}
1. Dessinez ce graphe.
2. Déterminez le degré entrant et le degré sortant de chaque sommet.
3. Ce graphe contient-il un cycle ? Si oui, identifiez-le.
Exercice 4 : Représentation d’un graphe
Soit le graphe orienté G = (X, U ) avec X = {1, 2, 3, 4} et
Γ+ (1) = {2}, Γ+ (2) = {2}, Γ+ (3) = {1}, Γ+ (4) = {}.
1. Tracer le graphe G.
2. Donner le degré de chaque sommet dans G.
Exercice 5 : Lemme des poignées de main
Soit le graphe non orienté simple G = (X, U ) d’ordre N qui possède 15 arêtes, 3 sommets de degré 4 et tous les
autres sommets de degré 3. Quel est l’ordre de ce graphe ?
Exercice 6 : Fermeture transitive
Soit le graphe orienté suivant :
A C
D E
1. Déterminez A, la matrice d’adjacence booléenne associée à ce graphe.
2. Calculez les puissances A2 et A3 de la matrice A. Que représentent ces matrices dans le contexte du graphe ?
3. Déterminez la matrice de fermeture transitive du graphe.
4. Représentez graphiquement la fermeture transitive obtenue.
Exercice 7 : Graphe complet
Un graphe complet Kn est un graphe non orienté contenant n sommets où chaque sommet est connecté à tous
les autres par une arête.
1. Représentation graphique Représentez graphiquement les graphes complets K3 , K4 , et K5 .
2. Nombre d’arêtes Le nombre d’arêtes dans un graphe complet Kn est donné par la formule :
n(n − 1)
|E| =
2
• Vérifiez cette formule pour n = 3, n = 4, et n = 5.
• Calculez le nombre d’arêtes pour K10 .
3. Degrés des sommets
• Quel est le degré de chaque sommet dans un graphe complet Kn ?
• Vérifiez votre réponse pour K4 et K5 .
4. Extension : Graphe orienté
• Si Kn devient orienté, chaque paire de sommets a deux arcs (un dans chaque direction).
• Donnez le nombre total d’arcs pour un graphe complet orienté Kn . Vérifiez votre réponse pour n = 4.
Exercice 8 : Connexité
1. Un graphe non orienté est donné par les sommets V = {P, Q, R, S, T } et les arêtes
E = {{P, Q}, {Q, R}, {R, S}}
• Ce graphe est-il connexe ? Justifiez votre réponse.
• Proposez une modification pour rendre le graphe connexe.
2. Est-ce que tous les sommets dans un graphe connexe sont accessibles à partir de n’importe quel autre sommet
Expliquez ?
Exercice 9 : Connexité
Soit le graphe orienté suivant :
1 3
5 4
1. Ce graphe est-il fortement connexe ? Justifiez votre réponse.
2. Identifiez les composantes fortement connexes du graphe.
3. Ajoutez des arêtes pour rendre ce graphe fortement connexe. Représentez le graphe obtenu.
Exercice 10 : Connexité
Un réseau maillé sans fil est constitué d’appareils (ordinateurs, téléphones, etc.) qui peuvent communiquer de
manière directe s’ils sont assez proches. Dans ces réseaux, les communications peuvent également se faire de
manière indirecte en multi-saut.
On suppose que, dans un certain réseau maillé sans fil, tout appareil est assez proche d’au moins la moitié des
appareils du réseau. Prouver que toute paire d’appareils peut alors communiquer dans ce réseau.
Exercice 11 : Coloration
Considérez le graphe suivant :
C D
A B E
1. Déterminez un encadrement du nombre chromatique de ce graphe.
2. Proposez une coloration en respectant ce nombre chromatique.
3. Justifiez que cette coloration est optimale.
Exercice 12 : Algorithme de Dijkstra
Soit le graphe pondéré suivant :
B
2 3
A C 5 F
1 2
1
D 4 E
1. Appliquez l’algorithme de Dijkstra pour trouver le plus court chemin entre le sommet A et le sommet F .
2. Représentez le chemin trouvé sur le graphe.