Spé. NSI · Terminale · cours rédigé et vérifié par Claryo, conforme au Bulletin officiel
Un graphe est fait de sommets (nœuds) et de liens entre eux. La nature du lien distingue deux familles.
Dans un graphe non orienté, les liens sont des arêtes symétriques : si A est relié à B, alors B est relié à A (amitié, route à double sens). On note une arête \{A, B\}.
Dans un graphe orienté, les liens sont des arcs à sens unique, notés A \to B : la relation n'est pas forcément réciproque (lien hypertexte, abonnement). On parle alors de successeur (B est successeur de A) et de prédécesseur (A est prédécesseur de B).
Le degré d'un sommet est son nombre d'arêtes (non orienté). En orienté, on distingue degré entrant (arcs reçus) et degré sortant (arcs émis).
Graphe non orienté à m arêtes : \sum_{s} \deg(s) = 2m.
Graphe orienté à m arcs : \sum_{s} \deg^{+}(s) = \sum_{s} \deg^{-}(s) = m (chaque arc a une origine et une destination).
Matrice d'adjacence : symétrique si non orienté, quelconque si orienté.
Représentation Python d'un graphe orienté (successeurs) :
g = {'A': ['B', 'C'], 'B': ['C'], 'C': ['A']} # A->B, A->C, B->C, C->A def successeurs(g, s): return g[s] def predecesseurs(g, s): return [t for t in g if s in g[t]]
1. Lire la relation modélisée : est-elle symétrique (non orienté) ou directionnelle (orienté) ? 2. Choisir arête ou arc en conséquence. 3. Pour un sommet en orienté, compter séparément arcs entrants et sortants. 4. Vérifier la symétrie (non orienté) ou son absence (orienté) dans la matrice/les listes.
Bien identifier l'orientation du graphe oriente tout le reste (représentation, parcours, calcul des degrés). Le correcteur valorise un vocabulaire exact et constant : sommet, arête pour le non orienté, arc pour l'orienté, successeur et prédécesseur, degré entrant et degré sortant. Savoir calculer les prédécesseurs d'un sommet à partir des listes de successeurs est un exercice fréquent à l'épreuve pratique, car les listes d'adjacence ne donnent directement que les successeurs : il faut parcourir tous les sommets pour retrouver ceux qui pointent vers la cible. Pensez aussi qu'un graphe non orienté peut se coder comme un graphe orienté symétrique, où chaque arête donne deux arcs opposés.