Graphes : structures relationnelles

Spé. NSI · Terminale · cours rédigé et vérifié par Claryo, conforme au Bulletin officiel

L'essentiel

Un graphe est une structure relationnelle : un ensemble de sommets (nœuds) reliés par des arêtes (graphe non orienté) ou des arcs (graphe orienté). Il modélise des relations entre objets : réseaux sociaux, routes, pages web, réseaux informatiques.

Notions clés : - Un chemin est une suite de sommets consécutivement reliés. - Un cycle est un chemin fermé revenant au point de départ. - Le degré d'un sommet est le nombre d'arêtes qui lui sont incidentes.

Deux représentations en machine : - La matrice d'adjacence : tableau n \times n avec M[i][j]=1 s'il y a une arête. Test d'arête immédiat, mais espace O(n^2). - Les listes d'adjacence : à chaque sommet, la liste de ses voisins. Espace O(n+m), adapté aux graphes creux.

Formules et schémas clés

Lemme des poignées de main (graphe non orienté à m arêtes) : \sum_{s \in V} \deg(s) = 2m.

Coûts mémoire :

| Représentation | Espace | Test d'arête | Lister les voisins | |---|---|---|---| | Matrice d'adjacence | O(n^2) | O(1) | O(n) | | Listes d'adjacence | O(n+m) | O(\deg) | O(\deg) |

Représentation Python (listes d'adjacence, graphe non orienté) :

g = {'A': ['B', 'C'], 'B': ['A', 'C'], 'C': ['A', 'B']} def degre(g, s): return len(g[s]) def nb_aretes(g): return sum(len(g[s]) for s in g) // 2

Méthode type bac

1. Identifier sommets et arêtes/arcs ; déterminer si le graphe est orienté. 2. Choisir la représentation : listes d'adjacence si creux, matrice si dense ou tests fréquents. 3. Pour compter les arêtes, sommer les degrés puis diviser par 2 (non orienté). 4. Pour un graphe non orienté, vérifier la symétrie des listes d'adjacence.

Pièges

  • Oublier la symétrie dans un graphe non orienté : si A liste B comme voisin, B doit lister A.
  • Compter chaque arête deux fois sans diviser par 2 dans la somme des degrés.
  • Confondre arc (orienté) et arête (non orienté).
  • Pour un graphe creux, la matrice d'adjacence gaspille beaucoup de mémoire.

Pour l'épreuve

Les graphes sont un thème majeur du programme. Le correcteur attend la maîtrise des deux représentations et de leurs complexités spatiales, ainsi que la relation \sum \deg = 2m, dite lemme des poignées de main. À l'épreuve pratique, on représente quasi toujours un graphe par un dictionnaire de listes d'adjacence : sachez calculer le degré d'un sommet, le nombre d'arêtes (somme des degrés divisée par deux) et lister les voisins d'un sommet. Vous devez aussi savoir convertir une représentation en l'autre, par exemple construire la matrice d'adjacence à partir des listes. C'est le préalable indispensable aux parcours BFS et DFS étudiés dans le thème algorithmique.