Ressources · Terminale · Maths expertes (option Tle)

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.

À propos de cette page

Ce cours de maths expertes de Terminale pose le vocabulaire des graphes en cinq parties : sommets, arêtes, ordre et graphe complet Kₙ ; degré et lemme des poignées de main, démontré ; graphes orientés, degrés entrants et sortants, chemins et circuits ; chaînes, cycles et connexité ; chaînes et cycles eulériens avec le théorème d’Euler et le problème des ponts de Königsberg.

Graphes : sommets, arêtes, graphe complet

Ce qu’il faut savoir

Graphe. Un graphe (non orienté) est formé d’un ensemble fini et non vide de sommets et d’arêtes ; chaque arête relie deux sommets, appelés ses extrémités. L’ordre du graphe est son nombre de sommets.

Sommets adjacents. Deux sommets reliés par une arête sont adjacents (ou voisins) ; on dit que l’arête est incidente à chacun d’eux. L’arête qui relie A et B se note A–B, ou B–A : c’est la même arête.

Boucle, arêtes multiples. Une arête qui relie un sommet à lui-même est une boucle. Deux sommets peuvent être reliés par plusieurs arêtes (arêtes multiples) : on parle alors de multigraphe. Un graphe sans boucle ni arête multiple est un graphe simple ; sauf mention contraire, les graphes de ce chapitre sont simples.

Trois façons de donner un graphe : un dessin, la liste des arêtes, ou le tableau des voisins de chaque sommet. Sur un dessin, seules comptent les liaisons : la position des sommets, la longueur et la forme des arêtes n’ont aucune importance, et un croisement de deux arêtes n’est pas un sommet.

Graphe complet. Un graphe est complet lorsque deux sommets distincts quelconques sont toujours adjacents. Le graphe complet d’ordre $n$ se note $K_{n}$ ; il possède $\frac{n (n - 1)}{2}$ arêtes, c’est-à-dire autant que de paires de sommets.

Exemples

Lire un graphe. Voici un graphe $G$ et le tableau de ses voisins.

Sommet	Voisins
A	B, C, D
B	A, C, D
C	A, B, E
D	A, B
E	C

$G$ est d’ordre $5$ . En lisant le tableau sans compter deux fois la même liaison, ses arêtes sont A–B, A–C, A–D, B–C, B–D et C–E : il en a $6$ . Il n’est pas complet, car D et E ne sont pas adjacents. Les sommets A, B et C sont deux à deux adjacents : ils forment un triangle.

Nombre d’arêtes de $K_{n}$ . Pour choisir une arête de $K_{n}$ , on choisit une extrémité ( $n$ choix) puis l’autre ( $n - 1$ choix) ; chaque arête est ainsi obtenue deux fois (A puis B, ou B puis A). Donc $K_{n}$ a $\frac{n (n - 1)}{2}$ arêtes, autant que de parties à $2$ éléments d’un ensemble à $n$ éléments : $(\binom{n}{2})$ .

Modéliser. Une ligue de volley compte $10$ clubs, et chaque club rencontre une fois chacun des autres. On prend pour sommets les clubs, et une arête pour chaque match : on obtient $K_{10}$ , donc la ligue organise $\frac{10 \times 9}{2} = 45$ matchs.

Réflexe — Pour modéliser une situation, j’écris ce que sont les sommets et ce que représente une arête. Pour compter les arêtes à partir d’un tableau de voisins, je ne compte chaque liaison qu’une fois : A–B et B–A sont la même arête.

Attention — $K_{n}$ a $\frac{n (n - 1)}{2}$ arêtes, et non $n^{2}$ ni $n (n - 1)$ : une arête relie une paire de sommets, comptée une seule fois. Et deux arêtes qui se croisent sur le dessin ne se rencontrent pas en un sommet.

1 / 5

Degré et lemme des poignées de main

Ce qu’il faut savoir

Degré. Le degré d’un sommet $s$ , noté $d (s)$ , est le nombre d’arêtes incidentes à $s$ ; une boucle compte pour $2$ . Dans un graphe simple, $d (s)$ est le nombre de voisins de $s$ , donc $0 ⩽ d (s) ⩽ n - 1$ si le graphe est d’ordre $n$ . Un sommet de degré $0$ est dit isolé.

Lemme des poignées de main. Dans un graphe qui possède $m$ arêtes, la somme des degrés de tous les sommets vaut $2 m$ : $\sum_{s} d (s) = 2 m .$

Conséquences. La somme des degrés est toujours paire, et le nombre de sommets de degré impair est toujours pair. Dans $K_{n}$ , chaque sommet est de degré $n - 1$ .

Exemples

Démonstration du lemme (à savoir refaire). Quand on additionne les degrés de tous les sommets, chaque arête est comptée exactement deux fois : une fois à chacune de ses extrémités (une boucle est comptée deux fois au même sommet, d’où la convention). La somme des degrés vaut donc $2 m$ .

Démonstration de la conséquence. On sépare la somme des degrés en deux : la somme des degrés pairs et la somme des degrés impairs. La première est paire, et la somme totale $2 m$ est paire ; par différence, la somme des degrés impairs est paire. Or une somme de nombres impairs n’est paire que si elle compte un nombre pair de termes : le nombre de sommets de degré impair est pair.

Vérifier sur le graphe $G$ de la partie précédente : $d (A) = 3$ , $d (B) = 3$ , $d (C) = 3$ , $d (D) = 2$ et $d (E) = 1$ . La somme vaut $12 = 2 \times 6$ : on retrouve les $6$ arêtes. Les sommets de degré impair sont A, B, C et E : ils sont $4$ , un nombre pair.

Un graphe peut-il exister ? Un graphe d’ordre $5$ dont les degrés seraient $4$ , $4$ , $3$ , $1$ et $1$ aurait une somme des degrés égale à $13$ , impaire : ce graphe n’existe pas. Un graphe dont $14$ sommets sont tous de degré $3$ a une somme des degrés égale à $42$ , donc $\frac{42}{2} = 21$ arêtes.

Retrouver le nombre d’arêtes de $K_{n}$ . Ses $n$ sommets sont de degré $n - 1$ : la somme des degrés vaut $n (n - 1) = 2 m$ , d’où $m = \frac{n (n - 1)}{2}$ .

Réflexe — Devant un graphe décrit par ses degrés, je calcule d’abord leur somme. Impaire : le graphe ne peut pas exister. Paire : le nombre d’arêtes est la moitié de la somme.

Attention — Une somme paire ne prouve pas qu’un graphe simple existe : aucun graphe simple d’ordre $4$ n’a pour degrés $3$ , $3$ , $1$ et $1$ (les deux sommets de degré $3$ seraient voisins de tous les autres, et les deux derniers sommets auraient alors au moins deux voisins). Et une boucle compte pour $2$ dans le degré.

2 / 5

Graphes orientés

Ce qu’il faut savoir

Graphe orienté. Quand les liaisons ont un sens, ce sont des arcs : l’arc A → B va de son origine A vers son extrémité B, et il ne se parcourt que dans ce sens. A → B et B → A sont deux arcs différents.

Degrés. Le degré sortant $d^{+} (s)$ est le nombre d’arcs qui partent de $s$ ; le degré entrant $d^{-} (s)$ est le nombre d’arcs qui arrivent en $s$ . Chaque arc part d’un sommet et arrive en un sommet, donc $\sum_{s} d^{+} (s) = \sum_{s} d^{-} (s) = nombre d’arcs .$

Chemin, circuit. Un chemin est une suite de sommets dans laquelle chaque sommet est relié au suivant par un arc dans le bon sens ; sa longueur est son nombre d’arcs. Un circuit est un chemin fermé (il revient à son départ), de longueur non nulle, qui n’emprunte pas deux fois le même arc.

Si l’on oublie le sens des arcs, on obtient un graphe non orienté, et le degré de chaque sommet vaut $d^{+} (s) + d^{-} (s)$ .

Exemples

Sur un réseau social, cinq comptes A, B, C, D, E ; l’arc X → Y signifie « X suit Y ».

Compte	A	B	C	D	E
$d^{+}$	$2$	$1$	$2$	$1$	$2$
$d^{-}$	$2$	$2$	$2$	$2$	$0$

Les degrés sortants ont pour somme $2 + 1 + 2 + 1 + 2 = 8$ , les degrés entrants aussi : le graphe a $8$ arcs. A → B → C → A est un circuit de longueur $3$ , et A → D → B → C → A un circuit de longueur $4$ . D → B → C → A est un chemin de longueur $3$ de D vers A. Comme $d^{-} (E) = 0$ , aucun arc n’arrive en E : aucun chemin ne mène d’un autre compte à E.

Réflexe — Je lis chaque arc dans son sens : un chemin suit les flèches. Pour contrôler un tableau de degrés, je vérifie que la somme des degrés sortants est égale à celle des degrés entrants.

Attention — Dans un graphe orienté, la somme des degrés entrants est égale au nombre d’arcs, et non à son double. Et un chemin de A vers B ne donne pas de chemin de B vers A.

3 / 5

Chaînes, cycles et connexité

Ce qu’il faut savoir

Chaîne. Une chaîne est une suite de sommets dans laquelle deux sommets consécutifs sont adjacents. Sa longueur est le nombre d’arêtes qu’elle emprunte. Une chaîne est fermée si elle revient à son sommet de départ, et simple si elle n’emprunte pas deux fois la même arête (elle peut repasser par un même sommet).

Cycle. Un cycle est une chaîne fermée, simple et de longueur non nulle. Dans un graphe simple, un cycle a une longueur au moins égale à $3$ .

Connexité. Un graphe est connexe lorsque deux sommets quelconques sont reliés par au moins une chaîne. Sinon, il se partage en composantes connexes : des groupes de sommets reliés entre eux par des chaînes, sans aucune arête d’un groupe à un autre.

Exemples

Dans le graphe $G$ de la première partie (arêtes A–B, A–C, A–D, B–C, B–D, C–E) :

• E–C–A–D est une chaîne simple de longueur $3$ qui relie E à D ;
• E–C–A–B–C est une chaîne simple de longueur $4$ : elle repasse par C, mais elle emprunte quatre arêtes différentes ;
• A–B–A n’est pas un cycle : elle emprunte deux fois l’arête A–B ;
• A–B–D–A est un cycle de longueur $3$ , et A–C–B–D–A un cycle de longueur $4$ .

Plus courte chaîne de E à D. Le seul voisin de E est C, et C n’est pas adjacent à D : aucune chaîne de longueur $1$ ou $2$ ne relie E à D. La chaîne E–C–A–D, de longueur $3$ , est donc la plus courte.

$G$ est connexe. Chaque sommet est relié à A : A–B, A–C, A–D et A–C–E. Deux sommets quelconques sont donc reliés par une chaîne qui passe par A.

Un graphe non connexe. Le graphe de sommets P, Q, R, S, T, U, V et d’arêtes P–Q, Q–R, R–P, S–T, U–V a trois composantes connexes : {P, Q, R}, {S, T} et {U, V}. Aucune arête ne sort de {S, T}, donc aucune chaîne ne relie S à P.

Réflexe — Pour prouver qu’un graphe est connexe, je relie chaque sommet à un même sommet par une chaîne. Pour prouver qu’il ne l’est pas, je montre un groupe de sommets d’où aucune arête ne sort vers les autres.

Attention — La longueur d’une chaîne compte les arêtes, pas les sommets : la chaîne E–C–A–D a quatre sommets et une longueur $3$ . Et « simple » interdit de réemprunter une arête, pas de repasser par un sommet.

4 / 5

Chaînes et cycles eulériens

Ce qu’il faut savoir

Chaîne et cycle eulériens. Une chaîne eulérienne est une chaîne qui emprunte chaque arête du graphe une fois et une seule. Si elle est fermée, c’est un cycle eulérien. Sa longueur est le nombre d’arêtes du graphe.

Théorème d’Euler. Soit $G$ un graphe connexe.
• $G$ admet un cycle eulérien si et seulement si tous ses sommets sont de degré pair.
• $G$ admet une chaîne eulérienne non fermée si et seulement s’il a exactement deux sommets de degré impair ; ces deux sommets sont alors les extrémités de la chaîne.

Le nombre de sommets de degré impair est pair : s’il ne vaut ni $0$ ni $2$ , il vaut au moins $4$ , et le graphe n’a ni cycle ni chaîne eulérienne. Le sens « condition nécessaire » se démontre ci-dessous ; la réciproque est admise.

Exemples

Pourquoi la condition est nécessaire. Suivons une chaîne eulérienne. Chaque fois qu’elle traverse un sommet, elle y arrive par une arête et en repart par une autre : les arêtes de ce sommet sont utilisées deux par deux. Un sommet qui n’est pas une extrémité de la chaîne a donc un degré pair. Si la chaîne est fermée, le départ et l’arrivée se compensent aussi : tous les degrés sont pairs. Si elle n’est pas fermée, seules ses deux extrémités ont un degré impair.

Les ponts de Königsberg. En 1735, Leonhard Euler présente à l’Académie de Saint-Pétersbourg sa solution d’une énigme : peut-on se promener dans Königsberg (aujourd’hui Kaliningrad) en traversant chacun des sept ponts sur la Pregel une fois et une seule ? On modélise : les deux rives A et B et les deux îles C et D sont les sommets, les ponts sont les arêtes (c’est un multigraphe).

Les degrés valent $d (A) = 3$ , $d (B) = 3$ , $d (C) = 5$ et $d (D) = 3$ : les quatre sommets sont de degré impair. La promenade est impossible. La réciproque du théorème n’a été publiée qu’en 1873, par Carl Hierholzer.

Modifier un graphe. Ajouter ou supprimer une arête change la parité du degré de ses deux extrémités, et d’elles seules. Si l’on construisait à Königsberg un huitième pont entre A et B, seuls C et D resteraient de degré impair : une promenade de C à D, empruntant chaque pont une fois, deviendrait possible.

Construire une chaîne eulérienne. Le graphe d’arêtes M–N, N–O, O–M, M–T et T–N est connexe ; $d (M) = 3$ , $d (N) = 3$ , $d (O) = 2$ et $d (T) = 2$ . Il a exactement deux sommets de degré impair, M et N : il admet une chaîne eulérienne de M à N, par exemple M–T–N–O–M–N, qui emprunte M–T, T–N, N–O, O–M puis M–N, soit les $5$ arêtes, chacune une fois.

Réflexe — 1. Je vérifie que le graphe est connexe. 2. Je compte les sommets de degré impair. 3. Je conclus : $0$ , cycle eulérien ; $2$ , chaîne eulérienne entre ces deux sommets ; plus de $2$ , ni l’un ni l’autre. 4. Si l’on m’en demande une, je la construis en partant d’un sommet impair et je vérifie qu’elle emprunte les $m$ arêtes.

Attention — La connexité est une hypothèse du théorème : un triangle et un cycle de longueur $4$ sans arête entre eux ont tous leurs degrés pairs, mais aucun cycle eulérien, car aucune chaîne ne passe de l’un à l’autre. Et une chaîne eulérienne passe une fois par chaque arête, pas par chaque sommet : elle peut repasser plusieurs fois par le même sommet.

5 / 5

Pour aller plus loin

Matrice d’adjacence et chemins. On range un graphe dans un tableau de nombres, sa matrice d’adjacence $M$ ; le coefficient de $M^{n}$ situé ligne $i$ et colonne $j$ donne le nombre de chemins de longueur $n$ de $i$ vers $j$ . La plus courte chaîne entre deux sommets (leur distance) et le diamètre d’un graphe sont traités dans le chapitre Matrice d’adjacence et chemins.

Graphes pondérés. Quand chaque arc porte une probabilité, le graphe décrit une chaîne de Markov : chapitre Graphes probabilistes et chaînes de Markov.

Pour aller plus loin (hors programme de maths expertes). Colorer un graphe, c’est donner une couleur à chaque sommet de façon que deux sommets adjacents n’aient jamais la même couleur ; le plus petit nombre de couleurs possible est le nombre chromatique $χ$ . Par exemple, un cycle de longueur $5$ ne se colore pas avec deux couleurs alternées (il est de longueur impaire) et il en faut $3$ . Un graphe obtenu en ne gardant qu’une partie des sommets, avec toutes les arêtes entre eux, s’appelle un sous-graphe.

À retenir

Un graphe : des sommets et des arêtes ; ordre = nombre de sommets ; $K_{n}$ , graphe complet d’ordre $n$ , a $\frac{n (n - 1)}{2}$ arêtes.
Lemme des poignées de main : la somme des degrés vaut $2 m$ ; elle est paire, et le nombre de sommets de degré impair est pair.
Graphe orienté : la somme des degrés sortants et celle des degrés entrants valent le nombre d’arcs ; un chemin suit le sens des arcs, un circuit est un chemin fermé.
Chaîne : longueur = nombre d’arêtes ; cycle = chaîne fermée simple ; connexe = deux sommets quelconques reliés par une chaîne.
Théorème d’Euler (graphe connexe) : $0$ sommet impair, cycle eulérien ; $2$ sommets impairs, chaîne eulérienne entre eux ; sinon, ni l’un ni l’autre.

Questions fréquentes

Qu’est-ce qu’un graphe complet et combien a-t-il d’arêtes ?

Un graphe est complet lorsque deux sommets distincts quelconques sont reliés par une arête. Le graphe complet à n sommets, noté Kₙ, a n(n − 1)/2 arêtes : une par paire de sommets. Par exemple, K₁₀ a 45 arêtes.

Que dit le lemme des poignées de main ?

Dans tout graphe, la somme des degrés des sommets est égale au double du nombre d’arêtes, car chaque arête est comptée une fois à chacune de ses extrémités. Conséquences : cette somme est paire, et le nombre de sommets de degré impair est pair.

Comment calcule-t-on les degrés dans un graphe orienté ?

Chaque sommet a un degré sortant (nombre d’arcs qui en partent) et un degré entrant (nombre d’arcs qui y arrivent). La somme des degrés sortants et celle des degrés entrants sont toutes deux égales au nombre d’arcs.

Quelle est la différence entre une chaîne, une chaîne simple et un cycle ?

Une chaîne est une suite de sommets où deux sommets consécutifs sont adjacents ; sa longueur est son nombre d’arêtes. Elle est simple si elle n’emprunte pas deux fois la même arête, mais elle peut repasser par un sommet. Un cycle est une chaîne simple fermée de longueur non nulle.

Que dit le théorème d’Euler sur les graphes ?

Pour un graphe connexe : il admet un cycle eulérien (qui emprunte chaque arête une fois et revient au départ) si et seulement si tous ses sommets sont de degré pair ; il admet une chaîne eulérienne non fermée si et seulement s’il a exactement deux sommets de degré impair, qui en sont les extrémités.

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

Prof de maths à Marseille · Cours particuliers au lycée · Aide aux devoirs