Représentations d'un Graphe
Matrice et liste d'adjacence
Enonce
Implémenter quatre fonctions utilitaires sur un graphe non orienté :
- matrice_vers_liste(M) — convertit une matrice $n \times n$ en dict d'adjacence
- liste_vers_matrice(G) — fait l'opération inverse
- degres(G) — renvoie un dict {sommet: degré}
- nb_aretes(G) — compte les arêtes (utiliser le lemme des poignées de main)
Signature attendue
def matrice_vers_liste(M: list) -> dict:
def liste_vers_matrice(G: dict) -> list:
def degres(G: dict) -> dict:
def nb_aretes(G: dict) -> int:Exemple
matrice_vers_liste([[0, 1, 1], [1, 0, 1], [1, 1, 0]])→{0: [1, 2], 1: [0, 2], 2: [0, 1]}
📖 Rappel de cours
Un graphe non orienté à $n$ sommets peut se représenter de deux façons principales :
Matrice d'adjacence :
Tableau $n \times n$ avec $M[i][j] = 1$ s'il existe une arête entre $i$ et $j$, $0$ sinon. Symétrique pour un graphe non orienté.
Test d'arête en $O(1)$, mais espace en $O(n^2)$ même pour un graphe creux.
Liste d'adjacence :
Dictionnaire {u: [voisins de u]}. Espace en $O(|V| + |E|)$ — bien plus économique pour les graphes creux.
Énumération des voisins en $O(\deg u)$, mais test d'existence d'une arête en $O(\deg u)$ aussi.
Définitions :
- Degré d'un sommet : nombre d'arêtes incidentes
- Lemme des poignées de main : $\sum_v \deg(v) = 2|E|$
← Exercices sur les graphes en Python — BFS, DFS, Dijkstra
Exercices du meme theme
- Algorithme de Kruskal
- Coloration de Graphe
- Plus Court Chemin dans un Labyrinthe
- Test de Bipartisme
- Détection de Cycle (graphe orienté)
- Diamètre d'un Arbre
La correction commentee, les indices progressifs, l'execution du code dans le navigateur et la verification par l'IA sont reserves aux abonnes.