Graphes et matrices

Graphes non orientés

Dans cette partie, nous considérons $G$, un graphe non orienté.

$Un graphe non orienté$ Un graphe non orienté

On appelle graphe non orienté un ensemble fini d’éléments, reliés ou non par une propriété commune.
Les éléments s’appellent les sommets du graphe.
Le nombre de sommets s’appelle l’ordre du graphe.
La relation entre deux éléments est appelée une arête. Les arêtes peuvent se parcourir dans les deux sens.
S’ils sont reliés entre eux par une arête, deux sommets sont adjacents.
Si un sommet n’est relié à aucun autre, on dit que c’est un sommet isolé.
Un graphe complet est un graphe où deux sommets quelconques sont toujours adjacents.
Dans un graphe complet, chaque sommet est relié à tous les autres.
Le degré d’un sommet de $G$ est le nombre d’arêtes qui relient ce sommet aux autres sommets du graphe.
Dans un graphe $G$ non orienté, la somme des degrés est égale au double du nombre d’arêtes et est paire.
Il y a un nombre pair de sommets de degré impair.
Une chaîne de $G$ est une suite d’arêtes consécutives.
Si les deux extrémités de la chaîne sont le même sommet, la chaîne est fermée.
La longueur d’une chaîne est le nombre d’arêtes qu’elle contient.
Dans un graphe non orienté, un cycle est une chaîne fermée qui ne comporte que des arêtes distinctes.
Si deux sommets quelconques peuvent toujours être reliés par une chaîne, alors $G$ est un graphe connexe.

Graphes orientés

Dans cette partie, nous considérons $G$, un graphe orienté.

$Un graphe orienté$ Un graphe orienté

Un graphe orienté est constitué de sommets.
Le nombre de sommets s’appelle l’ordre du graphe.
Certains sommets sont reliés par des arêtes qui sont orientées : elles ne peuvent être parcourues que dans un seul sens.
La lecture du sens des arêtes est importante, car elle va déterminer les parcours possibles sur un graphe.
Dans un graphe orienté, une boucle est une arête orientée d’origine et d’extrémité identiques.
Le vocabulaire est proche de celui pour les graphes non orientés :
on parle de chaîne pour un parcours constitué d’arêtes consécutives ;
nous trouverons dans certains exercices le mot chemin quand le parcours est orienté ;
si la chaîne ou le chemin a une origine et une extrémité identiques, alors on dira que c’est une chaîne fermée, ou un chemin fermé ;
s’il existe un chemin fermé qui n’emprunte qu’une seule fois une arête nous parlerons parfois de circuit pour un graphe orienté (le mot est équivalent à cycle) ;
notons enfin que les arêtes, dans un graphe orienté, sont parfois appelées arcs.
Le degré d’un sommet de $G$ est le nombre d’arêtes qui relient ce sommet aux autres sommets du graphe, quel que soit leur sens de parcours.
Soit $S$ un des sommets de $G$.
Une boucle sur un sommet $S$ est considérée comme deux arêtes : en effet, elle part de $S$ et elle arrive vers $S$. Elle sera comptée $2$ fois dans le calcul du degré d’un sommet.
Dans un graphe orienté, la somme des degrés est égale au double du nombre d’arêtes.

Matrices d’adjacence d’un graphe

Graphe non orienté

Graphe orienté

Soit $G$ un graphe non orienté d’ordre $n$.
La matrice d’adjacence de $G$ est la matrice carrée $A$ d’ordre $n$ définie par :

Pour tous $i$ et $j$ de $\lbrace 1,\,…,\,n\rbrace$, le coefficient $a_{i,j}$ est égal au nombre d’arêtes qui relient $S_i$ et $S_j$.

Soit $G$ un graphe orienté d’ordre $n$.
La matrice d’adjacence de $G$ est la matrice carrée $A$ d’ordre $n$ définie par :

Pour tous $i$ et $j$ de $\lbrace 1,\, …,\,n\rbrace$, le coefficient $a_{i,j}$ est égal au nombre d’arêtes qui partent de $S_i$ vers $S_j$.

Pour construire la matrice d’adjacence d'un graphe non orienté :

• on choisit d’ordonner les sommets, notamment quand ils ne sont pas représentés par des nombres ;

• l’ordre du graphe est l’ordre de la matrice, donc on connaît la taille de la matrice à écrire ;

• on indique, sur chaque ligne $i$, le nombre d’arêtes qui relient le sommet $S_i$ aux autres sommets $S_j$ dans l’ordre : de $1$ à $n$.

Pour construire la matrice d’adjacence d’un graphe orienté :

• on choisit un ordre pour les sommets ; quand ils ne sont pas représentés par des nombres, on doit fixer un ordre ;

• l’ordre du graphe est l’ordre de la matrice, donc on connaît la taille de la matrice à écrire ;

• on indique, sur chaque ligne $i$, le nombre d’arêtes qui partent du sommet $S_i$ vers les autres sommets $S_j$, dans l’ordre : de $1$ à $n$.

Pour obtenir un graphe à partir d’une matrice d’adjacence :

• l’ordre de la matrice carrée donne l’ordre du graphe, donc le nombre de sommets ;

• on schématise les sommets par des points que l’on nomme avec des lettres ou des chiffres, ou en suivant les consignes de l’énoncé ;

• on utilise les coefficients $a_{i,j}$ pour relier les sommets par des arêtes, en n'oubliant pas, pour aller plus vite, que la matrice d’adjacence d'un graphe non orienté est symétrique.

Pour obtenir un graphe à partir d’une matrice d’adjacence :

• l’ordre de la matrice carrée donne l’ordre du graphe, donc le nombre de sommets ;

• on schématise les sommets par des points que l’on nomme avec des lettres ou des chiffres, ou en suivant les consignes de l’énoncé ;

• le coefficient $a_{i,j}$ donne le nombre d’arête(s) qui part(ent) du sommet $S_i$ vers le sommet $S_j$.

Soit $m\in \mathbb N^*$, $G$ un graphe d’ordre $n$, de sommets $S_1$, $S_2$, …, $S_{n-1}$, $S_n$, et $A$ sa matrice d’adjacence.
Pour tous entiers $i$ et $j$ : le nombre de chemins – ou chaînes – de longueur $m$ entre $S_i$ et $S_j$ est $(A^m )_{i,j}$.
C’est-à dire le coefficient de la matrice $A^m$ situé à la $i\text{-ème}$ ligne et la $j\text{-ième}$ colonne.
Méthodologie pour déterminer le nombre de chemins de longueur $m$ entre deux sommets $S_i$ et $S_j$ :
trouver la matrice d’adjacence $A$ du graphe ;
calculer à la main, ou à la calculatrice, la matrice $A^m$ ;
trouver le coefficient situé à la ligne $i$ et la colonne $j$ de cette matrice.
Ce sera le nombre de chemins cherché.

Ce contenu est réservé à nos inscrits. Il reste 50% à lire.

Inscrivez-vous gratuitement pour lire la suite

Inscrivez-vous pour lire la suite et accéder à nos vidéos, quiz, exercices, méthodes… Tout ce qu’il faut pour augmenter sa moyenne. 😉

Déjà un compte ? Je me connecte