1

GRAPHES – Chapitre 1/2

Partie 1 : Le vocabulaire des graphes

Exemple :
Le schéma suivant s'appelle un graphe.
Il possède 4 sommets ; on dit qu'il est d'ordre 4.
Les sommets A et C sont adjacents car ils sont reliés
par une arête.
Le sommet C est de degré 3 car 3 arêtes partent de C.
Le sommet A possède une boucle.

Définitions : - On appelle graphe non orienté un ensemble de points, appelés sommets,

reliés par des lignes, appelées arêtes.
- L'ordre du graphe est le nombre de sommets.
- Le degré d'un sommet est le nombre d'arêtes partant de ce sommet.
- Deux sommets reliés par une arête sont adjacents.
- Une boucle est une arête dont les extrémités ont le même sommet.

Exemple :
La carte ci-contre représente le réseau de tramway de la ville de
Strasbourg.
Il s'agit d'un graphe dont les sommets sont les stations.

Définition : Un graphe est dit complet si deux sommets quelconques sont adjacents.

Exemple :
Le réseau d'ordinateur représenté ci-contre est un graphe complet
en effet tous les sommets sont reliés deux à deux.

Définition : Un graphe est dit simple s’il ne possède ni boucle, ni arête multiple*.
* S’il y a plusieurs arêtes entre deux sommets, on parle d’arêtes multiples.

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

Yvan Monka – Académie de Strasbourg – [Link]

 2

Démonstration : Chaque arête est comptée exactement deux fois lorsqu'on fait la somme
des degrés, une fois pour chaque sommet.

Méthode : Appliquer la propriété de la somme des degrés

Vidéo [Link]

a) Un hectogone est un polygone à 100 côtés. Avec toutes ses diagonales, l'hectogone forme
un graphe.
Combien la figure possède-t-elle de segments ?
b) Cinq jeunes souhaitent organiser un tournoi de ping-pong où chaque joueur rencontre
trois autres joueurs.
Est-ce possible ?

Correction
a) En chaque sommet, le graphe possède 99 arêtes. Le graphe possède 100 sommets donc la
somme des degrés de tous les sommets est égale à 99 x 100 = 9 900.
D'après la propriété de la somme des degrés, le graphe possède 9 900 : 2 = 4 950 arêtes (ou
segments si l'on considère la figure géométrique).

b) L'organisation du tournoi peut se représenter par un graphe d'ordre 5 où chaque sommet

possède 3 arêtes.
La somme des degrés est égale à 3 + 3 + 3 + 3 + 3 = 15. Donc d'après la propriété de la
somme des degrés, le graphe possède 15 : 2 = 7,5 arêtes. Ce qui est impossible donc la
situation du tournoi n'est pas réalisable.

Définitions : - Dans un graphe non orienté, une chaîne est une succession d'arêtes mises
bout à bout.
- La longueur de la chaîne est le nombre d'arêtes qui la composent.
- On dit qu'une chaîne est fermée si ses extrémités coïncident.
- Un cycle est une chaîne fermée dont les arêtes sont toutes distinctes.

Exemple :
Vidéo [Link]

Dans le graphe ci-contre,

• A – B – C – D – E est une chaîne de longueur 4.
• A – B – E – D – B – A est une chaîne fermée de longueur
5.
• B – C – D – E – B est un cycle de longueur 4.

Définition : Un graphe 𝐺 est connexe si chaque couple de sommets est relié par une chaîne.

Yvan Monka – Académie de Strasbourg – [Link]

 3

Exemples :

Graphe connexe Graphe non connexe, les sommets C et E, par

exemple, ne peuvent être reliés.

Partie 2 : Matrice d’adjacence associée à un graphe

Définition : Soit un graphe 𝐺 non orienté d'ordre 𝑛 dont les sommets sont numérotés de 1 à
𝑛.
La matrice d'adjacence associée à 𝐺 est la matrice carrée de taille 𝑛 dont chaque terme 𝑎!"
est égal au nombre d’arêtes reliant les sommets 𝑖 et 𝑗.

Exemples :
Vidéo [Link]

a) La matrice d'adjacence associée au graphe ci-contre

est :
0 1 1 𝟎 0
⎛ 1 0 1 1 1⎞
𝐴 = ⎜ 1 1 0 1 0⎟
0 𝟏 1 0 1
⎝ 0 1 0 1 0⎠

Par exemple, le coefficient 𝑎#$ marqué en rouge est égal à 0 car aucune arête ne relie les
sommets 1 et 4.
Le coefficient 𝑎$% marqué en vert est égal à 1 car une arête relie les sommets 4 et 2.

On constate que la diagonale est formée de 0 car aucun sommet n'est relié avec lui-même.
On constate également que la matrice est symétrique par rapport à la diagonale car 𝑎!" =
𝑎"! .

1 2
b) La matrice d'adjacence associée au graphe ci-dessous est 𝐵 = 4 6
2 0

Propriété : Soit une matrice d'adjacence 𝐴 d'un graphe 𝐺 non orienté d'ordre 𝑝 dont les
sommets sont numérotés de 1 à 𝑝.
Le nombre de chaînes de longueur 𝑛 reliant le sommet 𝑖 au sommet 𝑗 est égal au coefficient
𝑎!" de la matrice 𝐴& , 𝑛 ∈ ℕ∗ .

Yvan Monka – Académie de Strasbourg – [Link]

 4

Démonstration au programme :
On démontre cette propriété par récurrence.
• Initialisation : Les chaînes de longueur 1 qui joignent le sommet 𝑖 au sommet 𝑗
correspondent directement au coefficient (𝑎# )!" de la matrice d'adjacence 𝐴 = 𝐴# .
• Hérédité :
- Hypothèse de récurrence :
Supposons qu'il existe un entier 𝑘 tel que la propriété soit vraie :
Le nombre de chaînes de longueur 𝑘 reliant le sommet 𝑖 au sommet 𝑗 est égal au coefficient
(𝑎( )!" de la matrice d'adjacence 𝐴( .
- Démontrons que : La propriété est vraie au rang 𝑘 + 1 :
Le nombre de chaînes de longueur 𝑘 + 1 reliant le sommet 𝑖 au sommet 𝑗 est égal au
coefficient (𝑎()# )!" de la matrice d'adjacence 𝐴()# .
Soit un troisième sommet 𝑙 quelconque.
Le nombre de chaînes de longueur 𝑘 + 1 allant de 𝑖 à 𝑗, tels que la première arête soit {𝑖 ; 𝑙}
correspond au nombre de chaînes de longueur 1 allant de 𝑖 à 𝑙 multiplié par le nombre de
chaînes de longueur 𝑘 allant de 𝑙 à 𝑗, soit :
𝑐* = (coefficient (𝑎# )!* de la matrice 𝐴) × (coefficient (𝑎( )*" de la matrice 𝐴( )
Ainsi, le nombre de chaînes de longueur 𝑘 + 1 qui joignent deux sommets 𝑖 à 𝑗 est égal à la
somme des termes 𝑐* pour tous les sommets 𝑙, soit le coefficient (𝑎()# )!" de la matrice
𝐴()# .
• Conclusion :
La propriété est vraie pour 𝑛 = 1 et héréditaire à partir de ce rang. D'après le principe de
récurrence, elle est vraie pour tout entier naturel 𝑛.

Exemple :
Vidéo [Link]
On reprend l'exemple a) précédent.
On cherche le nombre de chaînes de longueur 4 reliant les sommets 1 et 3.
A l'aide de la calculatrice, on calcule la matrice 𝐴$ .

$
0 1 1 0 0 11 13 11 14 9
⎛1 0 1 1 1⎞ ⎛13 26 19 19 13⎞
𝐴$ = ⎜1 1 0 1 0⎟ = ⎜11 19 19 14 14⎟
0 1 1 0 1 14 19 14 19 11
⎝0 1 0 1 0⎠ ⎝ 9 13 14 11 11⎠

Le nombre de chaînes de longueur 4 reliant le sommet 1 au sommet 3 est égal au coefficient

𝑎#+ ou 𝑎+# de la matrice 𝐴$ .
Ainsi, il existe 11 chaînes de longueur 4 reliant les sommets 1 et 3.
Par exemple : 1 – 2 – 5 – 4 – 3 ou encore 1 – 2 – 3 – 2 – 3.

Hors du cadre de la classe, aucune reproduction, même partielle, autres que celles prévues à l'article L 122-5 du
code de la propriété intellectuelle, ne peut être faite de ce site sans l'autorisation expresse de l'auteur.
[Link]/[Link]/mentions-legales

Yvan Monka – Académie de Strasbourg – [Link]