Ressources · Terminale · Maths expertes (option Tle)

Fiche de révision : vocabulaire et propriétés

Graphes : sommets, arêtes, ordre, sommets adjacents, graphe complet ; degré et lemme des poignées de main ; graphes orientés, chemins et circuits ; chaînes, cycles et connexité ; chaînes et cycles eulériens, théorème d’Euler.

Télécharger la fiche PDF

benprofparticulier.frMaths expertes (option Tle) · Terminale

Graphes : vocabulaire et propriétés

Fiche méthode

(Maths expertes Terminale · Graphes et matrices)

La démarche face à un graphe

1. Je modélise : ce que sont les sommets, ce que représente une arête (ou un arc, si les liaisons ont un sens).

2. Je dresse le tableau des degrés et je le contrôle avec le lemme des poignées de main : somme des degrés $= 2 m$ .

3. J’étudie la connexité en reliant chaque sommet à un même sommet par une chaîne.

4. Je conclus en citant le résultat utilisé : « d’après le lemme des poignées de main », « d’après le théorème d’Euler, le graphe étant connexe ».

Le réflexe — une réponse « oui » ou « non » ne rapporte rien sans le comptage qui la justifie : somme des degrés, nombre de sommets de degré impair, chaîne écrite en entier.

Cas 1 · Modéliser et compter les arêtes

Réflexe — sommets et arêtes nommés ; chaque liaison comptée une seule fois ; Kₙ a n(n − 1)/2 arêtes.

Exemple. Question type : « Donner l’ordre et le nombre d’arêtes ; le graphe est-il complet ? » Exemple : les sommets sont les entiers de $1$ à $6$ , deux entiers sont adjacents quand l’un divise l’autre.

Ordre $6$ . Arêtes : 1–2, 1–3, 1–4, 1–5, 1–6, 2–4, 2–6, 3–6, soit $8$ arêtes.

Le graphe n’est pas complet : 2 et 3 ne sont pas adjacents ( $K_{6}$ aurait $\frac{6 \times 5}{2} = 15$ arêtes).

Attention — A–B et B–A sont la même arête : on ne la compte pas deux fois.

Cas 2 · Lemme des poignées de main

Réflexe — somme des degrés ; impaire : le graphe n’existe pas ; paire : m = somme ÷ 2.

Exemple. Question type : « Déterminer le nombre d’arêtes » ou « Ce graphe peut-il exister ? » Exemple : un graphe d’ordre $10$ a $4$ sommets de degré $5$ et $6$ sommets de degré $2$ .

Somme des degrés : $4 \times 5 + 6 \times 2 = 20 + 12 = 32$ .

Elle est paire ; d’après le lemme des poignées de main, $2 m = 32$ , donc le graphe a $m = 16$ arêtes.

Attention — une boucle compte pour 2 dans le degré ; une somme paire ne garantit pas l’existence d’un graphe simple.

1 / 2

benprofparticulier.frMaths expertes (option Tle) · Terminale

Cas 3 · Graphe orienté

Réflexe — degrés sortants et entrants ; chaque somme vaut le nombre d’arcs ; un chemin suit les flèches.

Exemple. Question type : « Donner les degrés entrants et sortants ; trouver un circuit ». Exemple : arcs P → Q, Q → R, R → P et R → S.

$d^{+}$ : P $1$ , Q $1$ , R $2$ , S $0$ ; $d^{-}$ : P $1$ , Q $1$ , R $1$ , S $1$ . Les deux sommes valent $4$ , le nombre d’arcs.

P → Q → R → P est un circuit de longueur $3$ . Comme $d^{+} (S) = 0$ , aucun chemin ne part de S.

Attention — la somme des degrés entrants vaut le nombre d’arcs, pas son double.

Cas 4 · Chaînes et connexité

Réflexe — connexe : je relie chaque sommet à un même sommet ; non connexe : un groupe de sommets d’où aucune arête ne sort.

Exemple. Question type : « Le graphe est-il connexe ? Justifier. » Exemple : sommets $1$ à $6$ , arêtes 1–3, 3–5, 5–1, 2–4 et 4–6.

Aucune arête ne relie un nombre impair à un nombre pair : aucune chaîne ne va de 1 à 2.

Le graphe n’est pas connexe ; il a deux composantes connexes, {1, 3, 5} et {2, 4, 6}.

Attention — la longueur d’une chaîne est son nombre d’arêtes, pas de sommets.

Cas 5 · Chaîne ou cycle eulérien

Réflexe — connexe ? nombre de sommets impairs : 0, cycle ; 2, chaîne entre eux ; plus, rien. Puis je construis et je vérifie les m arêtes.

Exemple. Question type : « Peut-on emprunter chaque arête une fois et une seule ? En donner un parcours. » Exemple : arêtes V–W, W–X, X–Y, Y–Z, Z–V et V–X.

Le graphe est connexe : la chaîne V–W–X–Y–Z passe par tous les sommets. $d (V) = 3$ , $d (W) = 2$ , $d (X) = 3$ , $d (Y) = 2$ , $d (Z) = 2$ : exactement deux sommets impairs, V et X.

D’après le théorème d’Euler, il existe une chaîne eulérienne de V à X : V–W–X–Y–Z–V–X emprunte V–W, W–X, X–Y, Y–Z, Z–V puis V–X, les $6$ arêtes une fois chacune.

Attention — tous les degrés pairs ne suffisent pas : il faut aussi la connexité.

Les pièges

Kₙ a n(n − 1)/2 arêtes, pas n² ni n(n − 1).
Un croisement de deux arêtes sur le dessin n’est pas un sommet.
Une chaîne simple peut repasser par un sommet ; elle ne réemprunte pas une arête.
Eulérien : chaque arête une fois, pas chaque sommet une fois.
Le théorème d’Euler suppose le graphe connexe.
Graphe orienté : A → B ne permet pas d’aller de B à A.

Ce document est la propriété intellectuelle de Ben, professeur particulier (benprofparticulier.fr), protégée par le Code de la propriété intellectuelle (art. L. 111-1 et L. 122-4). Il est mis à disposition pour un usage personnel de révision. Toute reproduction, diffusion, mise en ligne ou revente, totale ou partielle, sans autorisation écrite est interdite et constitue une contrefaçon (art. L. 335-2).

2 / 2

À propos de cette page

Cette fiche méthode donne la démarche face à un graphe, puis un exemple rédigé par cas : compter les arêtes d’un graphe défini par une règle, appliquer le lemme des poignées de main, lire les degrés d’un graphe orienté, prouver qu’un graphe n’est pas connexe, construire une chaîne eulérienne.

Bloqué sur ce chapitre ?

Moi c'est Ben, j'ai créé ce site pour aider le plus d'élèves possible, partout en France. Je peux aussi reprendre avec toi ce qui coince en cours particulier : en visio, ou à domicile si tu es à Marseille.

Réserver un 1^er cours → Voir les tarifs

Soutien scolaire à Marseille · Cours particuliers au collège · Aide aux devoirs