Lycée > Terminale L > Mathématiques > Graphes : définitions, propriétés

Graphes : définitions, propriétés

Fiche de cours Vidéos Quiz Profs en ligne Télécharger
le pdf

Objectif(s)

Connaître le vocabulaire des graphes : sommets, sommets adjacents, arêtes, degré d’un sommet, ordre d’un graphe, chaîne, longueur d’une chaîne, graphe complet, graphe connexe, chaîne eulérienne, matrice d’adjacence associée à un graphe.

Toutes les définitions sont à connaître. Certaines seront plus souvent utilisées dans le cours « Recherche du plus court chemin » ou dans le cours « Graphe probabiliste à 2 ou 3 sommets ».

1. Définitions

► Graphe, sommet, arête

Un graphe est un schéma contenant des points nommés sommets, reliés ou non par des segments appelés arêtes.

Graphe 1

A est un sommet, le segment [AB] est une arête reliant A à B (ou B à A).
D est un sommet isolé, non relié à un autre sommet.

► Boucle

Une boucle est une arête reliant deux fois le même sommet.

Graphe 2

Dans graphe 2, C est muni d’une boucle.

► Sommets adjacents

Deux sommets sont adjacents lorsqu’ils sont reliés par une arête.

Dans l’exemple précédent (Graphe 2), A et B sont adjacents, A et E ne le sont pas.

► Graphe simple

Un graphe est simple s’il ne comporte aucune boucle et que deux arêtes ne relient jamais la même paire de sommets.

Le graphe 1 est simple, le graphe 2 ne l’est pas.

► Degré d’un sommet

Le degré d’un sommet est égal au nombre d’arêtes qui le relient aux autres sommets.

Dans l’exemple précédent, A est de degré 2, B de degré 2, D de degré 0.

Propriété :
La somme des degrés de tous les sommets d’un graphe est égal au double du nombre total d’arêtes.

• Pour le graphe 1, le degré de chaque sommet est A(2), B(2), C(1), D(0), E(2), F(1), la somme vaut 2 + 2 + 1 + 0 + 2 + 1 = 8.
Le nombre d’arêtes étant 4, la somme est bien le double du nombre total d’arêtes.

• Pour le graphe 2, le degré de chaque sommet est A(2), B(2), C(3) car la boucle correspond à deux liaisons, D(0), E(2), F(1), la somme vaut 2 + 2 + 3 + 0 + 2 + 1 = 10.
Le nombre d’arêtes étant 5, la somme est bien le double du nombre total d’arêtes.

Dans ces cas simples, le calcul n’a que peu d’intérêt. Avec des graphes plus compliqués, cela peut être utile.

► Ordre d’un graphe

C’est le nombre total de sommets.

Les graphes 1 et 2 sont d’ordre 6.

► Sous graphe

Un sous graphe d’un autre graphe est un graphe composé de certains de ses sommets avec toutes les arêtes qui les relient.

Graphe 3

Graphe 3 est un sous graphe du graphe 2.

► Graphe complet

Un graphe est complet si tous les sommets sont adjacents les uns avec les autres.

Graphe 4

Ci-contre, graphe 4 est un graphe complet d’ordre 4.

Le graphe 1 n’est pas complet car par exemple B et C ne sont pas reliés.

► Graphe orienté

Un graphe orienté est un graphe dont les arêtes sont orientées. Elles ont une origine et une extrémité. Elles ne peuvent être parcourues que dans un sens.

Attention, rien n’oblige à « circuler » sur le graphe (aller obligatoirement d’un point à un autre).

► Matrice associée à un graphe d’ordre n

La matrice associée de n lignes et n colonnes est la matrice où le terme à l’intersection de la i^e ligne et de la j^e colonne est égal au nombre d’arêtes reliant les sommets i et j.

Pour graphe 4, on numérote les sommets dans l’ordre alphabétique, 1 pour A, 2 pour B, 3 pour C et 4 pour D.
Pour la 1^ère ligne, A n’est pas en relation avec lui-même (pas de boucle), donc 1^ère ligne, 1^ère colonne on met 0.
Pour les colonnes suivantes (toujours en 1^ère ligne), le graphe est simple, complet et A est adjacent à chaque autre sommet une seule fois. D’où les 1 qui complètent la ligne.

2. Exemples d’utilisations

a. Les ponts de Königsberg

La ville de Königsberg (aujourd’hui Kaliningrad en Russie) sur la rivière Pregolia (Pregolya) comporte deux îles. Sept ponts relient les îles entre elles ou aux rives.

Les habitants se posaient la question de savoir s’il existait une promenade permettant de passer une fois et une seule sur chaque pont pour revenir au point de départ.

Euler résolut par la négative ce problème.
La cause en est que de chaque île et de chaque rive partent un nombre impair de ponts.

La modélisation de ce problème (graphe ci-contre) a l’intérêt de se généraliser, c'est l'un des points de départ de la théorie des graphes.

Pour que l’on puisse faire une promenade ramenant le promeneur au point de départ, il faudrait que le nombre de ponts pour chaque île et chaque rive soit pair.
Si on enlève la contrainte de revenir au point de départ, il faudrait que deux des sommets au plus (le départ et l’arrivée) aient un nombre impair de ponts.

Le problème des sept ponts de Königsberg est l’exemple type de graphe eulérien.

b. Le problème du voyageur de commerce

L'énoncé du problème du voyageur de commerce est simple : étant donné n villes (que l’on représentera par des points) et les chemins (routes pouvant être uniques ou multiples, affectées de longueurs ou non) séparant chaque ville, trouver un chemin de longueur totale minimale qui passe exactement une fois (seulement) par chaque ville et revienne au point de départ.

Pour 3 ou 4 villes c’est facile mais le total des possibilités peut être supérieur à 360 000 trajets différents pour 10 villes !

Pour le graphe ci-dessus, plusieurs chemins sont possibles.
• Par exemple : A - 3 - B - 2 - D - 4 - C - 5 - E - 4 - F - 3 - A, la longueur totale est égale à 21.
• Le plus court, il est possible de changer certaines parties du parcours sans en changer la longueur : A - 2 - D - 2 - B - 3 - C - 5 - E - 4 - F - 3 - A, la longueur totale est égale à 19.