Graphes : définitions, propriétés
![]()
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
![]()
Graphe 2
|
Dans graphe 2, C est muni d’une boucle. |
► Sommets adjacents
► Graphe simple
► Degré d’un sommet
La somme des degrés de tous les sommets d’un graphe est égal au double du nombre total d’arêtes.
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
► Sous graphe
![]() Graphe 3 |
Graphe 3 est un sous graphe du graphe 2. |
► Graphe complet
![]()
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é

Attention, rien n’oblige à « circuler » sur le graphe (aller obligatoirement d’un point à un autre).
► Matrice associée à un graphe d’ordre n

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.
![]() |
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. |
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.

Fiches de cours les plus recherchées


Des profs en ligne
- 6 j/7 de 17 h à 20 h
- Par chat, audio, vidéo
- Sur les matières principales

Des ressources riches
- Fiches, vidéos de cours
- Exercices & corrigés
- Modules de révisions Bac et Brevet

Des outils ludiques
- Coach virtuel
- Quiz interactifs
- Planning de révision

Des tableaux de bord
- Suivi de la progression
- Score d’assiduité
- Un compte Parent