Médaille
N°1 pour apprendre & réviser du collège au lycée.

Graphes et matrices

Déjà plus de

1 million

d'inscrits !

Graphes non orientés

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

Alt texte Exemple de graphe non orienté (image temporaire)

  • 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 GG est le nombre d’arêtes qui relient ce sommet aux autres sommets du graphe.
  • Dans un graphe GG 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 GG 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 GG est un graphe connexe.

Graphes orientés

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

Alt texte Exemple de graphe orienté (image temporaire)

  • 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 GG est le nombre d’arêtes qui relient ce sommet aux autres sommets du graphe, quel que soit leur sens de parcours.
  • Soit SS un des sommets de GG.
  • Une boucle sur un sommet SS est considérée comme deux arêtes : en effet, elle part de SS et elle arrive vers SS. Elle sera comptée 22 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 GG un graphe non orienté d’ordre nn.
La matrice d’adjacence de GG est la matrice carrée AA d’ordre nn définie par :

Pour tous ii et jj de {1,,n}\lbrace 1,\,…,\,n\rbrace, le coefficient ai,ja{i,j} est égal au nombre d’arêtes qui relient SiSi et SjS_j.

Soit GG un graphe orienté d’ordre nn.
La matrice d’adjacence de GG est la matrice carrée AA d’ordre nn définie par :

Pour tous ii et jj de {1,,n}\lbrace 1,\, …,\,n\rbrace, le coefficient ai,ja{i,j} est égal au nombre d’arêtes qui partent de SiSi vers SjS_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 ii, le nombre d’arêtes qui relient le sommet SiSi aux autres sommets SjSj dans l’ordre : de 11 à nn.

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 ii, le nombre d’arêtes qui partent du sommet SiSi vers les autres sommets SjSj, dans l’ordre : de 11 à nn.

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 ai,ja_{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 ai,ja{i,j} donne le nombre d’arête(s) qui part(ent) du sommet SiSi vers le sommet SjS_j.

  • Soit mNm\in \mathbb N^*, GG un graphe d’ordre nn, de sommets S1S1, S2S2, …, Sn1S{n-1}, SnSn, et AA sa matrice d’adjacence.
  • Pour tous entiers ii et jj : le nombre de chemins – ou chaînes – de longueur mm entre SiSi et SjSj est (Am)i,j(A^m )_{i,j}.
    C’est-à dire le coefficient de la matrice AmA^m situé à la i-eˋmei\text{-ème} ligne et la j-ieˋmej\text{-ième} colonne.
  • Méthodologie pour déterminer le nombre de chemins de longueur mm entre deux sommets SiSi et SjSj :
  • trouver la matrice d’adjacence AA du graphe ;
  • calculer à la main, ou à la calculatrice, la matrice AmA^m ;
  • trouver le coefficient situé à la ligne ii et la colonne jj de cette matrice.
  • Ce sera le nombre de chemins cherché.