Arbres et graphes

Arbres : vocabulaire, taille, hauteur et profondeur#

Basiseduscol-programme-nsi-terminale

Un arbre annoté : racine, nœuds internes, feuilles, profondeurs et hauteur

Fig. 1Profondeur d'un nœud = nombre d'arêtes jusqu'à la racine (racine = 0). Hauteur = profondeur maximale, ici 3 (atteinte par la feuille G, sur le chemin mis en évidence). Taille = 7 nœuds ; feuilles = D, E, G.

Un ARBRE est une structure de données HIÉRARCHIQUE (non linéaire) faite de NŒUDS reliés par des liens. Il possède un nœud particulier, la RACINE (au sommet), et chaque autre nœud a exactement UN parent. Un arbre n'a ni cycle ni nœud à deux parents : c'est précisément ce qui le distingue d'un graphe quelconque. Vocabulaire : un nœud B est un FILS du nœud A (et A est le PARENT de B) lorsque A est directement relié à B au-dessus de lui.

Une FEUILLE est un nœud SANS fils (en bas de l'arbre) ; un nœud qui a au moins un fils est un nœud INTERNE. Tout nœud d'un arbre est lui-même la racine d'un SOUS-ARBRE formé de ce nœud et de toute sa descendance : c'est cette propriété qui rend la structure naturellement RÉCURSIVE.

La TAILLE d'un arbre est son nombre total de nœuds. La PROFONDEUR d'un nœud est le nombre d'arêtes (de liens) sur le chemin qui le sépare de la racine : par convention la racine est à la profondeur 0, ses fils à la profondeur 1, etc. La HAUTEUR de l'arbre est la profondeur MAXIMALE atteinte, c'est-à-dire la plus grande profondeur parmi toutes les feuilles.

Attention aux CONVENTIONS, à fixer explicitement avant tout calcul : avec la convention « hauteur = nombre d'arêtes du plus long chemin racine→feuille », une feuille seule (arbre à un seul nœud) a une hauteur 0, et l'arbre VIDE a une hauteur conventionnelle de −1 ; sa taille est 0. (Certains manuels comptent la hauteur en NŒUDS, décalant tout de 1 — vérifier la convention de l'énoncé.)

Une BRANCHE est un chemin de la racine jusqu'à une feuille ; le DEGRÉ (ou ARITÉ) d'un nœud est son nombre de fils. Un arbre N-aire autorise jusqu'à N fils par nœud ; le cas N = 2 (arbres binaires) est central au programme et fait l'objet de la section suivante.

Situations modélisées par un arbre : l'arborescence des fichiers d'un système d'exploitation (dossiers et fichiers), un arbre généalogique descendant, la structure d'un document (titres, sections, sous-sections), un arbre de décision, ou encore l'arbre syntaxique d'une expression. Dès qu'une relation est strictement HIÉRARCHIQUE (un seul parent, pas de cycle), l'arbre est la bonne structure.

\text{taille}(A) = \text{nombre total de nœuds de } A

Taille d'un arbre

On compte tous les nœuds, racine comprise. L'arbre vide a une taille de 0.

\text{profondeur}(\text{racine}) = 0 \;;\quad \text{hauteur}(A) = \max_{\,f\ \text{feuille}} \big(\text{profondeur}(f)\big)

Profondeur d'un nœud et hauteur de l'arbre

La profondeur d'un nœud est le nombre d'arêtes qui le séparent de la racine (racine à la profondeur 0). La hauteur est la profondeur maximale, atteinte par la feuille la plus éloignée de la racine.

Exemple corrigé

Lire un arbre : taille, feuilles, profondeur, hauteur et sous-arbre

On considère un arbre dont la racine A a pour fils B et C ; B a pour fils D et E ; C a un seul fils F ; F a un seul fils G. (a) Donner la taille de l'arbre. (b) Lister les feuilles. (c) Donner la profondeur du nœud G. (d) Donner la hauteur de l'arbre (convention : nombre d'arêtes du plus long chemin racine→feuille). (e) Décrire le sous-arbre enraciné en C.

Compter les nœuds (taille)
On dénombre tous les nœuds : A, B, C, D, E, F, G.
Repérer les feuilles
Une feuille n'a aucun fils. D et E n'ont pas de fils ; G n'a pas de fils. B, C et F ont au moins un fils, donc ne sont pas des feuilles. A est la racine et a des fils.
Profondeur de G
On compte les arêtes de A jusqu'à G : A→C (1), C→F (2), F→G (3).
Hauteur de l'arbre
La hauteur est la profondeur maximale parmi les feuilles. D et E sont à la profondeur 2, G à la profondeur 3. Le maximum est 3.
Sous-arbre enraciné en C
Le sous-arbre de racine C est formé de C et de toute sa descendance : C, son fils F, et le fils G de F. C'est un arbre de taille 3 et de hauteur 2.

Résultat : (a) taille = 7. (b) feuilles : D, E, G. (c) profondeur(G) = 3. (d) hauteur = 3. (e) le sous-arbre enraciné en C contient C, F et G (taille 3, hauteur 2). Cet arbre est DÉSÉQUILIBRÉ : la branche A–C–F–G est nettement plus longue que la branche A–B–D.

Erreurs fréquentes

Confondre HAUTEUR et TAILLE : la hauteur est une longueur de chemin (profondeur maximale), la taille est le nombre de nœuds. Un arbre profond peut avoir peu de nœuds, et un arbre large peut être peu haut.
Oublier de fixer la convention de hauteur : compter en arêtes ou en nœuds change le résultat de 1. Donner toujours la convention utilisée avant de répondre.
Appeler « feuille » un nœud qui a encore des fils : une feuille n'a AUCUN fils. Inversement, croire que la racine ne peut pas être une feuille — un arbre réduit à un seul nœud a sa racine qui est aussi son unique feuille.

Révision active

On considère un arbre dont la racine A a deux fils B et C ; B a deux fils D et E ; C a un fils F ; F a un fils G. (a) Donner la taille de l'arbre. (b) Lister les feuilles. (c) Donner la profondeur de G. (d) Donner la hauteur de l'arbre (convention : nombre d'arêtes du plus long chemin racine→feuille). (e) Décrire le sous-arbre enraciné en C.

Rappel actif

Rappelle-toi les points clés — puis révèle.

Sources : Programme de spécialité NSI — classe terminale (voie générale), BO spécial n° 8 du 25 juillet 2019 (Ministère de l'Éducation nationale) · Programmes et ressources en numérique et sciences informatiques — voie générale (Éduscol)

Arbres binaires et structure récursive#

Standardeduscol-programme-nsi-terminale

Deux arbres binaires de même taille (7 nœuds), de hauteurs opposées

Fig. 2À taille égale (7 nœuds), un arbre binaire équilibré a une hauteur d'ordre log₂(n) (ici 2), tandis qu'un arbre filiforme atteint la hauteur n−1 (ici 6). C'est tout l'enjeu de l'équilibrage pour la recherche.

Un ARBRE BINAIRE est un arbre où chaque nœud a AU PLUS DEUX fils, distingués par leur position : un fils GAUCHE et un fils DROIT. Cette distinction est essentielle : un nœud ayant seulement un fils gauche n'est PAS le même arbre que le même nœud avec seulement un fils droit, contrairement à un arbre général où l'ordre des fils n'importe pas toujours.

Définition RÉCURSIVE d'un arbre binaire — c'est la formulation centrale du programme : un arbre binaire est SOIT l'arbre VIDE (aucun nœud), SOIT un nœud, appelé racine, portant une valeur (ou clé) et possédant deux arbres binaires : son sous-arbre gauche et son sous-arbre droit. Tout traitement d'un arbre se programme alors récursivement, en distinguant le cas de base (arbre vide) du cas général (racine + deux sous-arbres).

La TAILLE d'un arbre binaire se définit récursivement : taille(vide) = 0, et taille(nœud) = 1 + taille(sous-arbre gauche) + taille(sous-arbre droit). De même la HAUTEUR : hauteur(vide) = −1, et hauteur(nœud) = 1 + max(hauteur(gauche), hauteur(droit)) (convention « arêtes »). Ces deux définitions illustrent exactement le schéma cas de base / cas récursif.

Pour un arbre binaire de TAILLE n, la hauteur h dépend de sa FORME et reste encadrée par log2(n+1) − 1 ≤ h ≤ n − 1. La borne INFÉRIEURE est atteinte par l'arbre PARFAITEMENT ÉQUILIBRÉ (le plus « tassé » : toutes les feuilles sur les deux derniers niveaux, les niveaux supérieurs complets) — c'est la hauteur minimale possible à n nœuds fixé. La borne SUPÉRIEURE est atteinte par l'arbre FILIFORME (chaque nœud n'a qu'un seul fils — l'arbre dégénère en liste chaînée). Cet encadrement explique pourquoi l'équilibre est si recherché : il maintient h proche de log2(n).

Un arbre binaire est COMPLET (ou « parfait ») si tous ses niveaux sont entièrement remplis ; il a alors exactement 2^(h+1) − 1 nœuds pour une hauteur h. Par exemple un arbre complet de hauteur 3 contient 2^4 − 1 = 15 nœuds, et un arbre complet de hauteur h a 2^h feuilles. Réciproquement, un arbre binaire à n nœuds a une hauteur minimale d'environ log2(n).

REPRÉSENTATIONS d'un arbre en machine (au choix selon le langage) : par une STRUCTURE RÉCURSIVE — un nœud est un objet/triplet (valeur, sous-arbre gauche, sous-arbre droit), l'arbre vide étant codé par une valeur sentinelle (None en Python) ; ou par des DICTIONNAIRES / LISTES indexant chaque nœud et ses fils. La représentation récursive épouse naturellement la définition et la programmation récursive de l'arbre.

\text{taille}(a) = \begin{cases} 0 & \text{si } a \text{ est vide} \\ 1 + \text{taille}(g) + \text{taille}(d) & \text{sinon} \end{cases}

Taille d'un arbre binaire (définition récursive)

Cas de base : l'arbre vide a 0 nœud. Cas récursif : la racine compte pour 1, à quoi s'ajoutent les tailles des sous-arbres gauche g et droit d.

\text{hauteur}(a) = \begin{cases} -1 & \text{si } a \text{ est vide} \\ 1 + \max\big(\text{hauteur}(g),\ \text{hauteur}(d)\big) & \text{sinon} \end{cases}

Hauteur d'un arbre binaire (convention « arêtes »)

Cas de base : l'arbre vide a la hauteur conventionnelle −1, de sorte qu'une feuille (deux sous-arbres vides) ait une hauteur 0. Cas récursif : on descend du plus haut des deux sous-arbres.

\log_2(n+1) - 1 \ \le\ h \ \le\ n - 1

Encadrement de la hauteur h d'un arbre binaire à n nœuds

Borne inférieure atteinte par l'arbre parfaitement équilibré (le plus « tassé ») ; borne supérieure atteinte par l'arbre filiforme (dégénéré en liste). C'est l'argument central de la complexité de l'ABR.

Croissance de la hauteur d'un arbre binaire à n nœuds : log2 (équilibré) vs linéaire (filiforme)

Exemple corrigé

Définir récursivement la hauteur, l'appliquer et l'encadrer

Un arbre binaire est représenté par None (arbre vide) ou par un triplet (valeur, gauche, droite). (a) Donner une définition récursive de la hauteur avec la convention hauteur(None) = −1. (b) Appliquer cette définition à l'arbre complet à 7 nœuds. (c) Vérifier la cohérence avec l'encadrement log2(n+1) − 1 ≤ h ≤ n − 1.

Cas de base
L'arbre vide est codé par None ; sa hauteur conventionnelle est −1.
Cas récursif
Pour un nœud (v, g, d), la hauteur est 1 de plus que la plus grande des hauteurs des deux sous-arbres.
Application à l'arbre complet de 7 nœuds
Un arbre complet de 7 nœuds a 3 niveaux : racine (niveau 0), 2 nœuds (niveau 1), 4 feuilles (niveau 2). Les feuilles ont une hauteur 0 ; leurs parents 1 + max(0, 0) = 1 ; la racine 1 + max(1, 1) = 2.
Vérification de l'encadrement
Pour n = 7 : la borne inférieure est log2(7+1) − 1 = log2(8) − 1 = 3 − 1 = 2 ; la borne supérieure est 7 − 1 = 6. La hauteur 2 atteint la borne inférieure : l'arbre est parfaitement équilibré.

Résultat : La hauteur de l'arbre complet de 7 nœuds vaut 2 : c'est exactement la borne inférieure log2(n+1) − 1 de l'encadrement, ce qui confirme que l'arbre est aussi « tassé » que possible. Un arbre filiforme de 7 nœuds atteindrait au contraire la borne supérieure 6.

Schritt-für-Schritt Erklärung4 Schritte

1
Un arbre binaire se définit récursivement : il est soit vide, soit un nœud portant une valeur et possédant deux arbres binaires, un sous-arbre gauche et un sous-arbre droit.
2
Cette définition se traduit directement en fonctions récursives. Pour la taille : zéro pour l'arbre vide, sinon un, plus la taille des deux sous-arbres.
3
Pour la hauteur, on descend du plus haut des deux sous-arbres en ajoutant un, l'arbre vide valant moins un par convention.
4
À nombre de nœuds fixé, la hauteur dépend de la forme : minimale et logarithmique pour un arbre équilibré, maximale et linéaire pour un arbre filiforme.

Erreurs fréquentes

Oublier le cas de base de l'arbre vide dans une fonction récursive : sans ce cas d'arrêt, la récursion ne se termine pas (ou provoque une erreur en accédant aux sous-arbres d'un arbre vide).
Traiter le fils gauche et le fils droit comme interchangeables : dans un arbre binaire, gauche et droit sont distincts. C'est une erreur fatale pour les arbres binaires de recherche (section suivante).
Confondre arbre binaire « complet » (tous les niveaux pleins, n = 2^(h+1) − 1) et arbre binaire « équilibré » (hauteur de l'ordre de log2(n) mais derniers niveaux pas forcément pleins) : tout arbre complet est équilibré, la réciproque est fausse.

Révision active

Écrire en Python une fonction récursive hauteur(a) qui renvoie la hauteur d'un arbre binaire, l'arbre vide étant représenté par None et un nœud non vide par un triplet (valeur, gauche, droite). On adoptera la convention hauteur(None) = −1. Tester la fonction sur un arbre complet de 7 nœuds (vérifier qu'elle renvoie 2) et sur un arbre filiforme de 4 nœuds (vérifier qu'elle renvoie 3).

Rappel actif

Rappelle-toi les points clés — puis révèle.

Sources : Programme de spécialité NSI — classe terminale (voie générale), BO spécial n° 8 du 25 juillet 2019 (Ministère de l'Éducation nationale)

Arbres binaires de recherche : propriété d'ordre, insertion, recherche#

Vertiefungeduscol-programme-nsi-terminale

Arbre binaire de recherche : propriété d'ordre et recherche de la clé 7

Fig. 4Dans un ABR, toute clé du sous-arbre gauche est plus petite que le nœud, toute clé du sous-arbre droit plus grande. Chercher 7 : on compare à chaque nœud et on descend à gauche ou à droite — chemin 8 → 3 → 6 → 7 (mis en évidence), en O(hauteur).

Un ARBRE BINAIRE DE RECHERCHE (ABR) est un arbre binaire dont les nœuds portent des clés COMPARABLES et qui respecte la PROPRIÉTÉ D'ORDRE en TOUT nœud : toutes les clés du sous-arbre GAUCHE sont strictement inférieures à la clé de la racine, et toutes les clés du sous-arbre DROIT lui sont strictement supérieures. Cette propriété doit être vraie récursivement à CHAQUE nœud, pas seulement à la racine.

Conséquence remarquable : un PARCOURS INFIXE (sous-arbre gauche, puis racine, puis sous-arbre droit) d'un ABR visite les clés dans l'ordre CROISSANT. C'est un test commode de validité : si la lecture infixe n'est pas triée, l'arbre n'est pas un ABR.

RECHERCHE d'une clé v dans un ABR : on part de la racine et on compare v à la clé courante. Si v est égale, c'est trouvé ; si v est plus petite, on descend à gauche ; si v est plus grande, on descend à droite. On répète jusqu'à trouver v ou jusqu'à atteindre un sous-arbre vide (échec). À chaque étape on ÉLIMINE tout un sous-arbre : c'est une recherche dichotomique sur la structure.

INSERTION d'une nouvelle clé v : on cherche v comme ci-dessus ; lorsque la recherche échoue sur un sous-arbre vide, c'est exactement là que la nouvelle clé doit être insérée comme nouvelle feuille, ce qui PRÉSERVE la propriété d'ordre. L'ordre d'insertion des clés détermine donc la FORME de l'arbre : insérer une suite déjà triée produit un arbre filiforme.

COMPLEXITÉ : la recherche, l'insertion (et la suppression) parcourent au plus une branche de la racine à une feuille, donc leur coût est en O(h), où h est la hauteur. Si l'arbre est ÉQUILIBRÉ, h ≈ log2(n) et la recherche est en O(log n) — très efficace. Si l'arbre est DÉGÉNÉRÉ (filiforme), h ≈ n et la recherche retombe en O(n), comme dans une liste : l'efficacité de l'ABR dépend donc entièrement de son équilibre.

L'ABR sert à maintenir un ENSEMBLE de clés triées avec recherche, insertion et suppression efficaces (par exemple un dictionnaire ordonné, un index). Il faut une RELATION D'ORDRE total sur les clés (nombres, chaînes par ordre lexicographique). On suppose en général les clés DISTINCTES (pas de doublon), ce qui justifie les inégalités strictes de la propriété d'ordre.

\forall\ g \in \text{sous-arbre gauche}(x),\ \forall\ d \in \text{sous-arbre droit}(x) : \quad \text{clé}(g) < \text{clé}(x) < \text{clé}(d)

Propriété d'ordre d'un ABR (vraie en tout nœud x)

À chaque nœud x, toute clé de son sous-arbre gauche est inférieure à la clé de x, et toute clé de son sous-arbre droit lui est supérieure. La propriété est récursive : elle doit tenir en CHAQUE nœud.

\text{coût recherche / insertion} = O(h) \quad\text{avec}\quad O(h) = \begin{cases} O(\log_2 n) & \text{ABR équilibré} \\ O(n) & \text{ABR filiforme} \end{cases}

Complexité de la recherche dans un ABR

Le coût est proportionnel à la hauteur h car on parcourt une seule branche. Équilibré, h ≈ log2(n) ; dégénéré, h ≈ n. L'efficacité de l'ABR repose donc sur son équilibre.

Exemple corrigé

Construire un ABR par insertions successives, puis y rechercher une clé

On insère dans un ABR initialement vide, et dans cet ordre, les clés : 8, 3, 10, 1, 6, 14, 4, 7, 13. (a) Décrire la construction et la structure obtenue. (b) Donner le parcours infixe et vérifier qu'il est trié. (c) Dérouler la recherche de la clé 7. (d) Indiquer le point d'insertion de la clé 5.

Insérer la racine et les premières clés
8 devient la racine. 3 < 8 → fils gauche de 8. 10 > 8 → fils droit de 8. 1 < 8 puis 1 < 3 → fils gauche de 3. 6 < 8 puis 6 > 3 → fils droit de 3.
Insérer les clés suivantes
14 > 8 puis 14 > 10 → fils droit de 10. 4 < 8, 4 > 3, 4 < 6 → fils gauche de 6. 7 < 8, 7 > 3, 7 > 6 → fils droit de 6. 13 > 8, 13 > 10, 13 < 14 → fils gauche de 14.
Parcours infixe (gauche, racine, droite)
On lit l'arbre dans l'ordre infixe à partir de la racine 8 : sous-arbre gauche trié, puis 8, puis sous-arbre droit trié.
Recherche de 7
On compare 7 successivement : 7 < 8 → gauche (vers 3) ; 7 > 3 → droite (vers 6) ; 7 > 6 → droite (vers 7) ; égalité → trouvé. Trois comparaisons descendantes.
Point d'insertion de 5
On cherche 5 : 5 < 8 → gauche (3) ; 5 > 3 → droite (6) ; 5 < 6 → gauche (4) ; 5 > 4 → droite de 4, qui est vide. 5 devient le fils droit de 4.

Résultat : (a) L'ABR a pour racine 8, sous-arbre gauche {3 → (1, 6 → (4, 7))} et sous-arbre droit {10 → (·, 14 → (13, ·))}. (b) Parcours infixe : 1, 3, 4, 6, 7, 8, 10, 13, 14 — strictement croissant, donc l'arbre est bien un ABR. (c) La recherche de 7 emprunte le chemin 8 → 3 → 6 → 7 en trois comparaisons. (d) La clé 5 s'insérerait comme fils droit de 4.

Erreurs fréquentes

Ne vérifier la propriété d'ordre qu'avec les fils immédiats : une clé du sous-arbre gauche peut être inférieure au parent direct mais supérieure à un ancêtre plus haut — il faut comparer à TOUS les ancêtres concernés. Le test du parcours infixe croissant évite ce piège.
Insérer une clé ailleurs qu'au point d'échec de la recherche : la nouvelle clé doit devenir une FEUILLE à l'endroit exact où la recherche tombe sur un sous-arbre vide, sinon la propriété d'ordre est rompue.
Croire que la recherche dans un ABR est toujours en O(log n) : ce n'est vrai que si l'arbre est équilibré. Un ABR construit à partir d'une suite triée est filiforme et la recherche y est en O(n).

Révision active

On insère successivement, dans cet ordre, les clés 8, 3, 10, 1, 6, 14, 4, 7, 13 dans un ABR initialement vide. (a) Dessiner l'ABR obtenu. (b) Donner son parcours infixe et vérifier qu'il est trié. (c) Décrire la recherche de la clé 7 : suite des comparaisons et chemin. (d) Indiquer où serait insérée la clé 5.

Rappel actif

Rappelle-toi les points clés — puis révèle.

Sources : Programme de spécialité NSI — classe terminale (voie générale), BO spécial n° 8 du 25 juillet 2019 (Ministère de l'Éducation nationale) · Programmes et ressources en numérique et sciences informatiques — voie générale (Éduscol)

Graphes : sommets, arêtes, orientation, pondération, connexité#

Standardeduscol-programme-nsi-terminale

Graphe non orienté, graphe orienté et graphe pondéré : le vocabulaire

Fig. 5Trois familles. Non orienté : les arêtes n'ont pas de sens (A–B = B–A). Orienté : les arcs ont un sens (A→B ≠ B→A). Pondéré : chaque arête porte un coût (distance, durée, débit).

Un GRAPHE modélise un ensemble d'objets et leurs relations. Il est constitué de SOMMETS (les objets, aussi appelés nœuds) et d'ARÊTES (les liens entre deux sommets). À la différence d'un arbre, un graphe peut contenir des CYCLES, plusieurs chemins entre deux sommets, et il n'a ni racine ni hiérarchie imposée : c'est la structure relationnelle la plus générale du programme.

Un graphe est NON ORIENTÉ quand ses liens sont symétriques (une arête {a, b} relie a et b dans les deux sens : une route à double sens, une amitié réciproque). Il est ORIENTÉ quand les liens ont un sens (un arc a→b va de a vers b sans impliquer b→a : une rue à sens unique, le graphe des liens d'un site web, une relation « suit » sur un réseau social).

Un graphe est PONDÉRÉ quand chaque arête porte un POIDS (un nombre : distance, durée, coût, capacité). Un graphe pondéré modélise un réseau routier avec les distances, un réseau de transport avec les temps de trajet, etc. Sans poids, on parle de graphe non pondéré : seule compte l'existence des liens.

VOCABULAIRE essentiel : deux sommets reliés par une arête sont VOISINS (ou adjacents) ; le DEGRÉ d'un sommet est son nombre de voisins (en orienté, on distingue le degré entrant et le degré sortant). Un CHEMIN est une suite de sommets reliés de proche en proche par des arêtes ; un CYCLE est un chemin qui revient à son sommet de départ sans répéter d'arête.

Un graphe non orienté est CONNEXE lorsqu'il existe un chemin entre toute paire de sommets (le graphe « tient en un seul morceau ») ; sinon il se décompose en plusieurs COMPOSANTES CONNEXES. La connexité répond à des questions concrètes : un réseau est-il entièrement joignable ? tous les ordinateurs peuvent-ils communiquer ?

MODÉLISER avec un graphe : un réseau social (sommets = personnes, arêtes = relations), un réseau routier ou de transport (sommets = lieux, arêtes pondérées = trajets), le plan d'un métro, les pages d'un site web et leurs liens (graphe orienté), un labyrinthe (sommets = cases, arêtes = passages), des dépendances entre tâches (graphe orienté). Dès qu'on a des objets ET des relations entre eux, le graphe est le bon modèle.

Exemple corrigé

Modéliser un réseau routier par un graphe et lire son vocabulaire

Quatre villes A, B, C, D sont reliées par des routes à double sens : A–B, A–C, B–C et C–D. (a) Modéliser par un graphe non orienté et donner le degré de chaque sommet. (b) Le graphe est-il connexe ? (c) Existe-t-il un cycle ? (d) Si l'on ajoute à chaque route sa longueur en kilomètres, de quel type de graphe s'agit-il ?

Choisir sommets et arêtes
On prend pour sommets les villes et pour arêtes les routes. Comme les routes sont à double sens, le graphe est NON ORIENTÉ. Les arêtes sont : {A,B}, {A,C}, {B,C}, {C,D}.
Calculer les degrés
Le degré d'un sommet est son nombre de voisins. A est relié à B et C (degré 2) ; B à A et C (degré 2) ; C à A, B et D (degré 3) ; D à C seulement (degré 1).
Vérifier la connexité
Depuis n'importe quel sommet on atteint tous les autres : par exemple D→C→A→B. Il existe donc un chemin entre toute paire de sommets : le graphe est CONNEXE (une seule composante connexe).
Chercher un cycle
Le triangle A–B–C forme un cycle : on part de A, on passe par B puis C et on revient en A sans réutiliser d'arête.
Identifier le type avec les distances
Si chaque arête porte une longueur (un nombre), le graphe devient PONDÉRÉ : c'est le modèle adapté pour calculer ensuite des plus courts chemins.

Résultat : (a) Degrés : A = 2, B = 2, C = 3, D = 1. (b) Le graphe est connexe. (c) Oui, le triangle A–B–C est un cycle. (d) Avec les distances, c'est un graphe non orienté PONDÉRÉ. Remarque : la somme des degrés vaut 2 + 2 + 3 + 1 = 8 = 2 × 4, soit deux fois le nombre d'arêtes — chaque arête comptant pour 1 à chacune de ses deux extrémités.

Erreurs fréquentes

Confondre graphe orienté et non orienté : dans un graphe orienté, l'arc a→b n'autorise pas le trajet b→a. Bien lire si la relation modélisée est symétrique (amitié, route à double sens) ou non (suit, sens unique, lien web).
Confondre un graphe avec un arbre : un arbre est un cas particulier de graphe (connexe, sans cycle, hiérarchique). Un graphe quelconque peut avoir des cycles et plusieurs chemins entre deux sommets ; ne pas lui chercher de « racine ».
Compter le degré en oubliant qu'en non orienté chaque arête contribue pour 1 au degré de CHACUNE de ses deux extrémités ; en orienté, ne pas additionner aveuglément entrant et sortant si l'énoncé demande l'un des deux.

Révision active

Quatre villes A, B, C, D sont reliées par des routes : A–B, A–C, B–C, C–D (toutes à double sens). (a) Modéliser la situation par un graphe non orienté et donner le degré de chaque sommet. (b) Le graphe est-il connexe ? (c) Citer un cycle s'il en existe un. (d) Si chaque route porte une distance en kilomètres, de quel type de graphe parle-t-on ?

Rappel actif

Rappelle-toi les points clés — puis révèle.

Sources : Programme de spécialité NSI — classe terminale (voie générale), BO spécial n° 8 du 25 juillet 2019 (Ministère de l'Éducation nationale)

Représenter un graphe : matrice et listes d'adjacence#

Vertiefungeduscol-programme-nsi-terminale

Le graphe à représenter (non orienté, sommets 0 à 3)

Fig. 6Le graphe non orienté de sommets 0, 1, 2, 3 et d'arêtes {0,1}, {0,2}, {1,2}, {2,3}. Le sommet 2 (mis en évidence) a pour voisins 0, 1 et 3 : son degré vaut 3. Voir Fig. suivante pour sa matrice d'adjacence.

Pour traiter un graphe en machine, deux représentations sont au programme. La MATRICE D'ADJACENCE d'un graphe à n sommets numérotés est un tableau carré n × n où l'élément M[i][j] vaut 1 s'il existe une arête (ou un arc) du sommet i vers le sommet j, et 0 sinon. Pour un graphe pondéré, on remplace le 1 par le POIDS de l'arête (et une valeur convenue — souvent l'infini ou 0 — pour l'absence d'arête).

Les LISTES D'ADJACENCE associent à chaque sommet la LISTE de ses voisins (ses successeurs en orienté). En machine, c'est typiquement un dictionnaire (ou un tableau de listes) : à chaque sommet correspond la liste des sommets qu'il atteint directement. Pour un graphe pondéré, chaque voisin est accompagné de son poids.

PROPRIÉTÉ de symétrie : pour un graphe NON ORIENTÉ, la matrice d'adjacence est SYMÉTRIQUE (M[i][j] = M[j][i]), car une arête {i, j} relie i et j dans les deux sens. Pour un graphe ORIENTÉ, la matrice n'est en général PAS symétrique. La diagonale est nulle s'il n'y a pas de boucle (arête d'un sommet vers lui-même).

COÛT MÉMOIRE : la matrice d'adjacence occupe toujours O(n²) cases (même si le graphe a peu d'arêtes), tandis que les listes d'adjacence occupent O(n + m) où m est le nombre d'arêtes (un emplacement par sommet et par arête). La matrice est donc coûteuse pour les grands graphes peu connectés.

COÛT DES OPÉRATIONS : tester si l'arête (i, j) existe se fait en O(1) avec la matrice (accès direct M[i][j]) mais en O(degré de i) avec les listes (il faut parcourir la liste de i). À l'inverse, énumérer tous les voisins d'un sommet est immédiat avec les listes, mais demande de balayer une ligne entière (n cases) avec la matrice.

QUEL CHOIX selon la DENSITÉ : un graphe DENSE (beaucoup d'arêtes, m proche de n²) se représente bien par une matrice d'adjacence (mémoire O(n²) de toute façon nécessaire, test d'arête en O(1)). Un graphe CREUX (peu d'arêtes, m petit devant n², cas le plus fréquent : réseaux routiers, réseaux sociaux) se représente mieux par des listes d'adjacence, bien plus économes en mémoire. Il faut savoir PASSER d'une représentation à l'autre.

M[i][j] = \begin{cases} 1 & \text{s'il existe une arête (ou un arc) de } i \text{ vers } j \\ 0 & \text{sinon} \end{cases}

Matrice d'adjacence (graphe non pondéré)

Tableau n × n indexé par les sommets. Pour un graphe pondéré, on remplace le 1 par le poids de l'arête. Non orienté ⇒ matrice symétrique : M[i][j] = M[j][i].

\text{mémoire : } \underbrace{O(n^2)}_{\text{matrice}} \;\text{ vs }\; \underbrace{O(n+m)}_{\text{listes}} \qquad \text{test d'arête : } \underbrace{O(1)}_{\text{matrice}} \;\text{ vs }\; \underbrace{O(\deg i)}_{\text{listes}}

Coûts comparés des deux représentations (n sommets, m arêtes)

La matrice est gourmande en mémoire (O(n²)) mais teste une arête en O(1) ; les listes sont économes (O(n+m)) — idéales pour les graphes creux — mais le test d'arête y coûte O(degré du sommet).

Matrice d'adjacence du même graphe (symétrique)

Fig. 7Matrice symétrique (graphe non orienté) : M[i][j] = M[j][i]. Listes d'adjacence : 0 → [1, 2], 1 → [0, 2], 2 → [0, 1, 3], 3 → [2]. Mémoire : matrice O(n²), test d'arête O(1) ; listes O(n+m), idéales pour un graphe creux.

Exemple corrigé

Matrice d'adjacence, listes d'adjacence et choix de représentation

Soit le graphe non orienté de sommets 0, 1, 2, 3 et d'arêtes {0,1}, {0,2}, {1,2}, {2,3}. (a) Écrire sa matrice d'adjacence (ordre 0,1,2,3) et vérifier qu'elle est symétrique. (b) Donner les listes d'adjacence. (c) Comparer le coût mémoire des deux représentations et choisir celle adaptée à un très grand réseau creux.

Construire la matrice ligne par ligne
Pour chaque sommet i, on met 1 en colonne j pour chaque voisin j. Sommet 0 : voisins 1 et 2. Sommet 1 : voisins 0 et 2. Sommet 2 : voisins 0, 1, 3. Sommet 3 : voisin 2. La diagonale est nulle (pas de boucle).
Vérifier la symétrie
Le graphe étant non orienté, on contrôle que M[i][j] = M[j][i] pour tout couple. Ici M[0][2] = M[2][0] = 1, M[2][3] = M[3][2] = 1, etc. : la matrice est bien symétrique par rapport à sa diagonale.
Écrire les listes d'adjacence
À chaque sommet on associe la liste de ses voisins, lue directement sur le graphe (ou sur les 1 de sa ligne dans la matrice).
Comparer les coûts mémoire
Avec n = 4 sommets, la matrice occupe n² = 16 cases, quel que soit le nombre d'arêtes. Les listes occupent de l'ordre de n + m emplacements ; avec m = 4 arêtes (comptées deux fois en non orienté, soit 8 entrées de voisins), cela reste de l'ordre de O(n + m). Pour ce petit graphe, l'écart est faible ; mais pour un grand réseau CREUX (n grand, m petit devant n²), la matrice gaspillerait O(n²) cases presque toutes nulles.

Résultat : (a) La matrice, symétrique, vaut [[0,1,1,0],[1,0,1,0],[1,1,0,1],[0,0,1,0]]. (b) Listes : 0:[1,2], 1:[0,2], 2:[0,1,3], 3:[2]. (c) La matrice coûte toujours O(n²) en mémoire et teste une arête en O(1) ; les listes coûtent O(n+m) et énumèrent les voisins immédiatement. Pour un très grand réseau CREUX, les LISTES d'adjacence sont nettement préférables ; la matrice ne se justifie que pour un graphe dense ou quand le test d'arête en O(1) est critique.

Erreurs fréquentes

Oublier la symétrie de la matrice pour un graphe non orienté : si l'arête {i, j} existe, il faut mettre 1 à la FOIS en M[i][j] ET en M[j][i]. Ne remplir qu'une moitié est une erreur classique.
Inverser le sens d'un arc dans la matrice d'un graphe orienté : M[i][j] = 1 code l'arc i→j, pas j→i. Pour un graphe orienté, la position dans la matrice porte le sens.
Affirmer que la matrice est « toujours plus efficace » : elle est en O(1) pour tester une arête mais coûte O(n²) en mémoire quel que soit le nombre d'arêtes ; pour un grand graphe creux, les listes d'adjacence (O(n+m)) sont nettement préférables.

Révision active

On considère le graphe non orienté de sommets numérotés 0, 1, 2, 3 et d'arêtes {0,1}, {0,2}, {1,2}, {2,3}. (a) Écrire sa matrice d'adjacence (ordre 0,1,2,3) et vérifier qu'elle est symétrique. (b) Donner les listes d'adjacence correspondantes. (c) Le graphe comptant 4 sommets et 4 arêtes, comparer le coût mémoire des deux représentations et indiquer laquelle conviendrait le mieux à un très grand réseau creux.

Rappel actif

Rappelle-toi les points clés — puis révèle.

Sources : Programme de spécialité NSI — classe terminale (voie générale), BO spécial n° 8 du 25 juillet 2019 (Ministère de l'Éducation nationale) · Programmes et ressources en numérique et sciences informatiques — voie générale (Éduscol)

Points clés

Lire un arbre : taille, feuilles, profondeur, hauteur et sous-arbre

Points clés

Définir récursivement la hauteur, l'appliquer et l'encadrer

Points clés

Construire un ABR par insertions successives, puis y rechercher une clé

Points clés

Modéliser un réseau routier par un graphe et lire son vocabulaire

Points clés

Matrice d'adjacence, listes d'adjacence et choix de représentation

Sources

Arbres et graphes

Points clés

Lire un arbre : taille, feuilles, profondeur, hauteur et sous-arbre

Points clés

Définir récursivement la hauteur, l'appliquer et l'encadrer

Points clés

Construire un ABR par insertions successives, puis y rechercher une clé

Points clés

Modéliser un réseau routier par un graphe et lire son vocabulaire

Points clés

Matrice d'adjacence, listes d'adjacence et choix de représentation

Sources