Corrigé des Exercices sur les Graphes
Exercice 1 : Réseau social (README.md)
Rappel du graphe
Avec : - A ami avec B, C, D - B ami avec A, D - C ami avec A, E, D - D ami avec A, B, C, E, F - E ami avec C, D, F - F ami avec E, D
1°) Degré des sommets
| Sommet | Voisins | Degré |
|---|---|---|
| A | B, C, D | 3 |
| B | A, D | 2 |
| C | A, E, D | 3 |
| D | A, B, C, E, F | 5 |
| E | C, D, F | 3 |
| F | E, D | 2 |
Vérification : Somme des degrés = 3+2+3+5+3+2 = 18 = 2 × 9 arêtes ✓
2°) Ordre du graphe
L'ordre du graphe est 6 (il y a 6 sommets : A, B, C, D, E, F).
3°) Ce graphe est-il complet ?
Non, ce graphe n'est pas complet.
Dans un graphe complet d'ordre 6, chaque sommet serait de degré 5 (relié à tous les autres).
Contre-exemples : - A n'est pas relié à E et F - B n'est pas relié à C, E et F
Exercice 2 : Matrice d'adjacence du réseau social
En numérotant les sommets dans l'ordre alphabétique (A, B, C, D, E, F) :
| A | B | C | D | E | F | |
|---|---|---|---|---|---|---|
| A | 0 | 1 | 1 | 1 | 0 | 0 |
| B | 1 | 0 | 0 | 1 | 0 | 0 |
| C | 1 | 0 | 0 | 1 | 1 | 0 |
| D | 1 | 1 | 1 | 0 | 1 | 1 |
| E | 0 | 0 | 1 | 1 | 0 | 1 |
| F | 0 | 0 | 0 | 1 | 1 | 0 |
En Python :
M = [
[0, 1, 1, 1, 0, 0],
[1, 0, 0, 1, 0, 0],
[1, 0, 0, 1, 1, 0],
[1, 1, 1, 0, 1, 1],
[0, 0, 1, 1, 0, 1],
[0, 0, 0, 1, 1, 0]
]
Remarque : La matrice est symétrique car le graphe est non orienté.
Exercice 3 : Réseau social d'Arthur (EXERCICES.md)
Graphe
Représentation par dictionnaire
G = {
'Arthur': ['Benoit', 'Elodie'],
'Benoit': ['Arthur', 'Coralie'],
'Coralie': ['Benoit', 'Franck', 'David'],
'David': ['Coralie', 'Franck', 'Elodie'],
'Elodie': ['Arthur', 'David', 'Franck'],
'Franck': ['Coralie', 'David', 'Elodie']
}
Matrice d'adjacence
En ordre alphabétique : Arthur, Benoit, Coralie, David, Elodie, Franck
| Arthur | Benoit | Coralie | David | Elodie | Franck | |
|---|---|---|---|---|---|---|
| Arthur | 0 | 1 | 0 | 0 | 1 | 0 |
| Benoit | 1 | 0 | 1 | 0 | 0 | 0 |
| Coralie | 0 | 1 | 0 | 1 | 0 | 1 |
| David | 0 | 0 | 1 | 0 | 1 | 1 |
| Elodie | 1 | 0 | 0 | 1 | 0 | 1 |
| Franck | 0 | 0 | 1 | 1 | 1 | 0 |
Exercice 4 : Village d'Eva (graphe orienté pondéré)
Graphe
École
/ | \
3↓ 4↑ 6↕
/ | \
Boulangerie ←─── Mairie Salle des fêtes
↓ ↕2 ↕7 ↕5
4↓ Bureau Église Boucherie
↓ de poste
Boucherie
Sommets : Boulangerie, Bureau de poste, École, Boucherie, Église, Mairie, Salle des fêtes
Arêtes orientées avec poids : - Boulangerie ↔ Bureau de poste : 2 min (double sens) - École → Boulangerie : 3 min (sens unique) - Boulangerie → Boucherie : 4 min (sens unique) - École → Église : 3 min (sens unique) - Mairie → École : 4 min (sens unique) - École ↔ Salle des fêtes : 6 min (double sens) - Boucherie ↔ Salle des fêtes : 5 min (double sens) - Mairie ↔ Église : 7 min (double sens)
Exercice 5 : Ordre et degrés (img2.PNG)
(Réponse basée sur l'image du fichier)
Pour déterminer l'ordre : compter le nombre de sommets.
Pour déterminer le degré de chaque sommet : compter le nombre d'arêtes incidentes.
Méthode générale :
def ordre(graphe):
return len(graphe)
def degre(graphe, sommet):
return len(graphe[sommet])
def degres(graphe):
return {s: len(v) for s, v in graphe.items()}
Exercice 6 : Dictionnaire et matrice (img3.PNG)
(Réponse basée sur l'image du fichier)
Méthode pour créer le dictionnaire :
# Lire les sommets et leurs voisins depuis le graphe
G = {}
# Pour chaque sommet, lister ses voisins
# G['A'] = ['B', 'C', ...]
Méthode pour créer la matrice d'adjacence :
def creer_matrice(graphe):
sommets = list(graphe.keys())
n = len(sommets)
matrice = [[0] * n for _ in range(n)]
for i, s1 in enumerate(sommets):
for j, s2 in enumerate(sommets):
if s2 in graphe[s1]:
matrice[i][j] = 1
return matrice
Auteur : Florian Mathieu
Licence CC BY NC
Ce cours est mis à disposition selon les termes de la Licence Creative Commons Attribution - Pas d'Utilisation Commerciale - Partage dans les Mêmes Conditions 4.0 International.