Graphes et matrices

Graphes et matrices

Les images ne sont pas encore disponibles pour ce cours.

Celles présentes sont juste des « brouillons »
afin de permettre une meilleure compréhension du cours,
jusqu’à ce que les définitives soient prêtes.

Nos graphistes font tout leur possible pour les réaliser au plus vite.

😉

Introduction :

La théorie des graphes est une théorie récente de l’histoire des mathématiques, puisqu’elle est née au XIXe siècle. Elle s’intéresse aux ensembles finis d’éléments et aux relations qui existent entre eux.
Les applications sont nombreuses et parlent à tous : on utilise les graphes pour étudier les réseaux informatiques ou routiers, ou encore dans certains algorithmes.

Nous nous intéresserons, dans la première partie de ce cours, aux définitions et représentations d’un graphe non orienté ; puis nous ferons de même pour les graphes orientés dans la deuxième partie.
Enfin, nous ferons le lien entre les graphes et leur représentation sous forme de matrice dans la troisième partie.

Graphes non orientés

Graphe non orienté : définitions et vocabulaire

Prenons l’exemple d’un groupe de cinq amis : Alex, Béa, Charles, David et Émeline comparent leurs loisirs et se demandent s’ils pratiquent une activité sportive.
Dans ce groupe, Alex n’aime pas le sport et n’en fait pas. Les autres sont inscrits dans des clubs sportifs de la région.

On appelle un graphe le groupe des cinq amis et la relation « … fait du sport comme… ».

  • Cet exemple nous permet d’introduire le vocabulaire propre aux graphes.
bannière definition

Définition

Graphe non orienté et vocabulaire associé :

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é.

Nous constaterons que le vocabulaire utilisé : sommet, arête, adjacent, est largement emprunté à la géométrie.
En effet, on représente habituellement un graphe par un schéma où les sommets sont des points et les arêtes des segments ou des lignes.

bannière exemple

Exemple

Dans l’exemple ci-dessus, représentons les cinq amis par des points nommés d’après les initiales de leur prénom : AA, BB, CC, DD et EE.

  • La relation « … fait du sport comme… » est schématisée par un segment ou une ligne.

Alt texte Image temporaire

  • Dans ce graphe, il y a cinq sommets.
  • L’ordre du graphe est donc 55.
  • Il y a un sommet isolé : AA.
  • Les sommets BB et CC sont adjacents, puisqu’ils sont reliés par l’arête [BC][BC].

Nous pouvons parcourir cette arête dans les deux sens : on peut dire que Béa fait du sport comme Charles, mais aussi que Charles fait du sport comme Béa.

  • Nous pouvons compter les arêtes de ce graphe : il y en a 66.

Si Alex ne participe pas à la discussion, le graphe devient un graphe d’ordre 44 ci-dessous :

Alt texte Image temporaire

Dans ce dernier graphe, chaque sommet est adjacent à tous les autres.

  • Un tel graphe s’appelle un graphe complet. Notons-en la définition.
bannière definition

Définition

Graphe complet :

Un graphe complet est un graphe où deux sommets quelconques sont toujours adjacents.

  • Autrement dit : dans un graphe complet, chaque sommet est relié à tous les autres.

Dans le cas de nos cinq amis, nous avons dénombré facilement le nombre d’arêtes. Si on prend un graphe plus complexe comme les membres d’un même réseau social ayant un intérêt commun, cela peut s’avérer plus difficile.
Voyons donc une propriété qui permet de calculer le nombre d’arêtes.

Degré des sommets et nombre d’arêtes

Commençons par définir le degré d’un sommet.

bannière definition

Définition

Degré d’un sommet :

Soit un graphe noté GG.
Le degré d’un sommet de GG est le nombre d’arêtes qui relient ce sommet aux autres sommets du graphe.

Reprenons le graphe suivant :

Alt texte Image temporaire

Le degré de AA est 00 ; les degrés de BB, CC, DD et EE valent tous 33.

  • Additionnons les degrés : 0+3+3+3+3=120+3+3+3+3=12.
  • Nous rappelons que le nombre d’arêtes de ce graphe est 66.

Prenons maintenant un second exemple.

bannière exemple

Exemple

La région administrative du Centre-Val-de-Loire comporte 66 départements que nous avons numérotés de 11 à 66. Nous nous intéressons à la relation « … a une frontière commune avec… ».

  • À partir de la carte, nous obtenons le graphe non orienté GG.

Alt texte Image temporaire

Construisons un tableau donnant les degrés des sommets :

Sommet 11 22 33 44 55 66
Degré 22 33 33 33 22 55
  • Faisons la somme des degrés : 2+3+3+3+2+5=182+3+3+3+2+5 =18.
  • Nous comptons les arêtes : il y en a 99.

Dans les deux exemples ci-dessus, nous constatons que la somme des degrés des sommets vaut le double du nombre d’arêtes.

Donnons-en une explication.
Soit deux sommets adjacents S1S1 et S2S2 : en additionnant leurs degrés, on compte deux fois l’arête qui les relie.

  • Nous en déduisons qu’en calculant la somme de tous les degrés, nous compterons deux fois chaque arête.

Nous avons la propriété suivante.

bannière propriete

Propriété

Dans un graphe GG non orienté, la somme des degrés est égale au double du nombre d’arêtes.

Cette propriété s’avère utile quand il est difficile de dénombrer sur un graphique le nombre d’arêtes.
Prenons un autre exemple pour nous en convaincre.

bannière exemple

Exemple

Lors d’un congrès scientifique, 3131 chercheurs et chercheuses se rencontrent. Le jour de l’inauguration, ils échangent tous une poignée de mains.

Considérons qu’il s’agit d’un graphe à 3131 sommets. Les arêtes représentent la poignée de mains échangée. Chacun des 3131 chercheurs serre la main aux 3030 autres.

  • Donc le degré de chaque sommet est 3030.

La somme des degrés est 30×3130\times31.
Donc, d’après la propriété ci-dessus, le nombre d’arêtes du graphe est :

30×312=465\dfrac{30\times31}2=465

  • Nous en déduisons qu’il y a 465465 poignées de mains échangées.
bannière attention

Attention

L’erreur serait de faire le produit de 3030 par 3131 seulement : dans ce cas, on comptabiliserait deux fois chaque poignée de mains.

De la propriété ci-dessus, nous déduisons également les corollaires suivants.

bannière propriete

Propriété

Dans un graphe non orienté :

  • la somme des degrés des sommets d’un graphe est paire ;
  • il y a un nombre pair de sommets de degré impair.

Intéressons-nous maintenant aux parcours possibles dans un graphe, c’est-à-dire au moyen de passer d’un sommet à un autre.

Parcours dans un graphe non orienté

Quand nous parcourons un graphe, nous empruntons différentes arêtes. Voici le vocabulaire associé au parcours dans un graphe non orienté.

bannière definition

Définition

Chaîne dans un graphe non orienté :

GG est un graphe non orienté.
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.
bannière definition

Définition

Longueur d’une chaîne :

La longueur d’une chaîne est le nombre d’arêtes qu’elle contient.

Prenons un exemple pour illustrer les parcours dans un graphe.

bannière exemple

Exemple

Reprenons le graphe GG ci-dessus, montrant les frontières communes entre les départements du Centre-Val-de-Loire. Nous cherchons :

  • différentes chaînes qui permettent de passer du sommet 11 au sommet 66 ;
  • une chaîne qui part de 22 et revient à 22.

Alt texte Image temporaire

  • Prenons la chaîne 1261-2-6. Il y a trois sommets sur ce parcours et deux arêtes.
  • La longueur de cette chaîne est donc 22.

Citons quelques autres chaînes qui permettent de passer de 11 à 66 :

  • 1234561-2-3-4-5-6, de longueur 55 ;
  • 12361-2-3-6, de longueur 33 ;
  • 161-6, de longueur 11.

Il y en a bien sûr d’autres, car rien n’empêche d’emprunter la même arête plus d’une fois.
Nous verrons, dans la dernière partie de ce cours, une méthode pour dénombrer les chaînes de longueur donnée entre deux sommets.

  • Pour partir du sommet 22 et revenir au sommet 22, nous parcourons une chaîne fermée.

Une chaîne fermée d’origine et d’extrémité 22 est : 234622-3-4-6-2.

  • Sa longueur vaut 44.

Dans la dernière chaîne de l’exemple, nous n’avons parcouru qu’une seule fois chaque arête.

  • Cette chaîne s’appelle un cycle.
bannière definition

Définition

Cycle :

Dans un graphe non orienté, un cycle est une chaîne fermée qui ne comporte que des arêtes distinctes.

Allons un peu plus loin : quel que soit le sommet de ce graphe, on peut y accéder à partir de n’importe quel autre sommet en parcourant une chaîne.

  • On dit alors que le graphe est connexe.
bannière definition

Définition

Graphe connexe :

GG est un graphe non orienté.
Si deux sommets quelconques peuvent toujours être reliés par une chaîne, alors GG est un graphe connexe.

bannière exemple

Exemple

Illustrons ce qu’est un graphe non connexe :

Alt texte Image temporaire

Dans ce graphe, il n’est pas possible de trouver une chaîne qui relie, par exemple, les sommets AA et EE.

  • Ce graphe n’est pas connexe.

Dans cette première partie, nous avons défini le vocabulaire propre aux graphes non orientés et étudié leurs premières propriétés.
Intéressons-nous maintenant aux graphes orientés.

Graphes orientés

Définitions et vocabulaire

Un graphe orienté présente les mêmes caractéristiques qu’un graphe non orienté, à la différence que les arêtes ont un sens de parcours.

bannière definition

Définition

Graphe orienté et vocabulaire associé :

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.

Prenons un exemple simple de graphe orienté.

Alt texte Image temporaire

Ce graphe est d’ordre 44, car il a 44 sommets.
Les sommets HH et GG sont adjacents, II et GG sont également adjacents, ainsi que KK et GG.

Observons à présent le sens de parcours des arêtes :

  • il y a une arête qui part de II, mais il n’y a pas d’arête qui arrive sur II ;
  • il y a une arête qui arrive sur HH, mais pas d’arête qui part de HH ;
  • nous pouvons toutefois faire un parcours GKGG-K-G car il y a 22 arêtes, une dans chaque sens, entre ces 22 sommets.
bannière attention

Attention

La lecture du sens des arêtes est importante, car elle va déterminer les parcours possibles sur un graphe.
Dans notre exemple, il sera impossible d’effectuer le parcours KGIK-G-I puisque l’arête entre GG et II est dans le sens de II vers GG uniquement.

Enfin, nous observons pouvoir aller de KK vers KK avec une seule arête.

  • Cette arête s’appelle une boucle.
bannière definition

Définition

Boucle :

Dans un graphe orienté, une boucle est une arête orientée d’origine et d’extrémité identiques.

Prenons à présent un exemple plus complexe pour illustrer la construction d’un graphe orienté.

bannière exemple

Exemple

Nous voulons représenter par un graphe la relation « … est un diviseur de… » dans l’ensemble des entiers naturels inférieurs ou égaux à 1010.

  • Ce graphe a 1010 sommets : les nombres entiers de 11 à 1010.
  • L’ordre du graphe est donc 1010.
  • Nous savons que 55 et 1010 sont adjacents, puisque 55 divise 1010. Mais 1010 ne divise pas 55.

De manière générale, si {d divise nd<n\begin{cases} d \text{ divise } n \ d, alors nn ne divise pas dd.

  • L’arête qui relie le sommet dd au sommet nn sera parcourue dans un seul sens : de dd vers nn.
  • Nous avons donc un graphe orienté.

Pour le construire, il faut déterminer les diviseurs possibles de chaque nombre dans l’ensemble donné.
Nous savons que 11 divise tous les autres ; que 22 divise les nombres pairs, que 33 divise 66 et 99, etc.

  • Voici donc le graphe obtenu :

Alt texte Image temporaire

Le sens de parcours de chaque arête est donné par la flèche sur l’arête.
Comme pour un graphe non orienté, nous pouvons utiliser le vocabulaire que nous avons appris au paragraphe précédent.

Ainsi, ce graphe :

  • n’est pas complet : en effet, les sommets ne sont pas deux à deux adjacents : par exemple, 99 et 22 ne sont pas adjacents puisque 22 ne divise pas 99, et 99 ne divise pas 22 ;
  • ne possède pas de sommet isolé.

Chacun des entiers est divisible par lui-même : nous avons donc représenté le fait que tout entier nn admet nn comme diviseur par une boucle.

À présent, pouvons-nous parcourir le graphe du sommet 11 au sommet 1010 ?

  • Nous constatons que les parcours suivants sont possibles :

110121015101221015510\begin{aligned} &1-10 \ &1-2-10 \ &1-5-10 \ &1-2-2-10 \ &1-5-5-10 \end{aligned}

bannière astuce

Astuce

Comme dans un graphe non orienté, 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.

Voyons à présent comment comptabiliser le nombre d’arêtes qui partent ou arrivent sur un sommet.

Degré des sommets

Le degré d’un sommet a la même signification que dans un graphe non orienté.

bannière definition

Définition

Degré d’un sommet :

Soit un graphe orienté noté GG.
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.

bannière attention

Attention

Soit GG un graphe et SS un de ses sommets.
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.
bannière exemple

Exemple

Reprenons l’exemple du graphe des diviseurs.

  • Le degré du sommet 11 est 1111 : en effet, du sommet 11 partent 99 arêtes vers les autres sommets, et la boucle sur 11 compte pour 22 arêtes.
  • Le degré du sommet 44 est 55 : 22 arêtes qui arrivent, 11 arête qui part et une boucle.
  • Le degré du sommet 66 est 55 : 33 arêtes qui arrivent et une boucle.

La propriété qui s’applique sur la somme de degrés pour un graphe non orienté est encore valable.

bannière propriete

Propriété

Dans un graphe GG orienté, la somme des degrés est égale au double du nombre d’arêtes.

Nous pourrons nous en servir également pour déterminer le nombre d’arêtes d’un sommet, mais sans pouvoir distinguer celles qui y arrivent ou en repartent.

Dans cette partie, nous avons défini les graphes orientés et montré comment on les représente. Ils seront largement utilisés dans le chapitre suivant sur les chaînes de Markov.
Dans la troisième partie de ce chapitre, nous allons étudier la représentation d’un graphe par une matrice.

Matrices d’adjacence d’un graphe

Matrice d’adjacence d’un graphe non orienté

Soit GG un graphe non orienté d’ordre nn.
Il possède nn sommets S1S1, S2S2, …, Sn1S{n-1}, SnSn.

  • Nous allons associer à ce graphe une matrice AA.

Faisons d’abord quelques rappels utiles.

bannière rappel

Rappel

Une matrice carrée d’ordre nn est une matrice qui a le même nombre de lignes et de colonnes.

  • On note : ai,ja{i,j}, ou (A)i,j(A){i,j} le coefficient de la matrice situé à la i-eˋmei\text{-ème} ligne et la j-ieˋmej \text{-ième} colonne.
bannière definition

Définition

Matrice d’adjacence d’un graphe non 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.

bannière exemple

Exemple

Reprenons le graphe non orienté que nous avons vu en première partie pour construire sa matrice d’adjacence.

Alt texte Image temporaire

bannière à retenir

À retenir

Méthodologie :

Pour construire une matrice d’adjacence :

  • 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.

Appliquons cette méthode au graphe.
Nous pouvons naturellement classer les sommets par ordre alphabétique :

AA BB CC DD EE
11 22 33 44 55
  • L’ordre du graphe est 55, donc nous devons écrire une matrice carrée d’ordre 55.
  • La 1re1^{\text{re}} ligne concerne le 1er1^{\text{er}} sommet AA, donc nous y indiquons le nombre d’arêtes qui relient :
  • AA à AA : a1,1=0\textcolor{#3CB371}{a_{1,1}=0} ;
  • AA à BB : a1,2=0\textcolor{#3CB371}{a_{1,2}=0} ;
  • AA à CC : a1,3=0\textcolor{#3CB371}{a_{1,3}=0} ;
  • AA à DD : a1,4=0\textcolor{#3CB371}{a_{1,4}=0} ;
  • AA à EE : a1,5=0\textcolor{#3CB371}{a_{1,5}=0}.
  • La 2e2^{\text{e}} ligne concerne le 2e2^\text{e} sommet BB, donc nous y indiquons le nombre d’arêtes qui relient :
  • BB à AA : a2,1=0\textcolor{#FFA500}{a_{2,1}=0} ;
  • BB à BB : a2,2=0\textcolor{#FFA500}{a_{2,2}=0} ;
  • BB à CC : a2,3=1\textcolor{#FFA500}{a_{2,3}=1} ;
  • BB à DD : a2,4=1\textcolor{#FFA500}{a_{2,4}=1} ;
  • BB à EE : a2,5=1\textcolor{#FFA500}{a_{2,5}=1}.
  • Voici donc la matrice avec ses deux premières lignes :

(0000000111000000000000000)\begin{pmatrix} \textcolor{#3CB371}0 & \textcolor{#3CB371}0 & \textcolor{#3CB371}0 & \textcolor{#3CB371}0 & \textcolor{#3CB371}0 \ \textcolor{#FFA500}0 & \textcolor{#FFA500}0 & \textcolor{#FFA500}1 & \textcolor{#FFA500}1 & \textcolor{#FFA500}1 \ \phantom{0} & \phantom{0} & \phantom{0} & \phantom{0} & \phantom{0} \ \phantom{0} & \phantom{0} & \phantom{0} & \phantom{0} & \phantom{0} \ \phantom{0} & \phantom{0} & \phantom{0} & \phantom{0} & \phantom{0} \end{pmatrix}

  • Nous poursuivons ainsi pour les 33 autres sommets pour obtenir la matrice d’adjacence de ce graphe :

(0000000111010110110101110)\begin{pmatrix} 0 & 0 & 0 & 0 & 0 \ 0 & 0 & 1 & 1 & 1 \ 0 & 1 & 0 & 1 & 1 \ 0 & 1 & 1 & 0 & 1 \ 0 & 1 & 1 & 1 & 0 \end{pmatrix}

bannière astuce

Astuce

Faisons une remarque supplémentaire sur cette matrice : matérialisons, avec des couleurs, la diagonale et observons les coefficients de part et d’autre de cette diagonale.

(0000000111010110110101110)\begin{pmatrix} \red 0 & \textcolor{#3CB371}0 & \textcolor{#3CB371}0 & \textcolor{#3CB371}0 & \textcolor{#3CB371}0 \ \textcolor{#3CB371}0 & \red 0 & \textcolor{#FFA500}1 & \textcolor{#FFA500}1 & \textcolor{#FFA500}1 \ \textcolor{#3CB371}0 & \textcolor{#FFA500}1 & \red 0 & \textcolor{#9400D3}1 & \textcolor{#9400D3}1 \ \textcolor{#3CB371}0 & \textcolor{#FFA500}1 & \textcolor{#9400D3}1 & \red 0 & \textcolor{#1E90FF}1 \ \textcolor{#3CB371}0 & \textcolor{#FFA500}1 & \textcolor{#9400D3}1 & \textcolor{#1E90FF}1 & \red 0 \end{pmatrix}

Nous observons les mêmes groupes de coefficients de part et d’autre de la diagonale, en symétrie.
Pour l’expliquer, intéressons-nous aux coefficients de la matrice.

Soit ii et jj deux entiers de {1,,n}\lbrace 1,\,…,\,n \rbrace.
Comparons ai,ja{i,j} et aj,ia{j,i}.

  • ai,ja{i,j} est le nombre d’arêtes entre le sommet SiSi et le sommet SjS_j.
  • aj,ia{j,i} est le nombre d’arêtes entre le sommet SjSj et le sommet SiS_i : ces deux nombres sont donc les mêmes !
  • Ainsi, quels que soient ii et jj de {1,,n}\lbrace 1,\,…,\,n\rbrace, on a : ai,j=aj,ia{i,j}=a{j,i}.

On dit que la matrice AA est une matrice symétrique.
Ceci nous aidera à distinguer les matrices d’adjacence des graphes non orientés de celles correspondant à un graphe orienté, que nous verrons dans le prochain paragraphe.

Prenons maintenant un deuxième exemple pour illustrer comment on obtient un graphe à partir d’une matrice d’adjacence.

bannière exemple

Exemple

Considérons un graphe GG, dont la matrice d’adjacence est :

(0011001011011010)\begin{pmatrix} 0 & 0 & 1 & 1 \ 0 & 0 & 1 & 0 \ 1 & 1 & 0 & 1 \ 1 & 0 & 1 & 0 \end{pmatrix}

  • Nous cherchons à représenter GG.
bannière à retenir

À retenir

Méthodologie :

  • 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.

Appliquons cette méthode.

  • La matrice est d’ordre 44, donc il y a 44 sommets dans ce graphe.
  • Appelons les 44 sommets dans cet ordre : AA, BB, CC et DD.
  • La 1re1^{\text{re}} ligne nous donne le nombre d’arêtes qui relient le sommet 11, soit AA, aux autres :

a1,1=0a{1,1}=0 a1,2=0a{1,2}=0 a1,3=1a{1,3}=1 a1,4=1a{1,4}=1
AA n’est pas relié à lui-même AA n’est pas relié à BB AA est relié à CC AA est relié à DD
  • Nous pouvons donc commencer à faire le graphe :

Alt texte Image temporaire

  • Puis nous le complétons en procédant de même avec les autres lignes.

Alt texte Image temporaire

bannière astuce

Astuce

Nous l’avons dit plus haut, la matrice d’adjacence d’un graphe non orienté est symétrique. Nous pouvons donc ne nous intéresser qu’aux coefficients de la diagonale et à ceux « au-dessous » ou « au-dessus ».

Nous avons vu comment représenter une matrice d’adjacence d’un graphe non orienté. Qu’en est-il maintenant pour un graphe orienté ?

Matrice d’adjacence d’un graphe orienté

Soit GG un graphe orienté d’ordre nn : il possède nn sommets S1S1, S2S2, …, Sn1S{n-1}, SnSn.

  • Nous allons associer à ce graphe une matrice AA.
bannière definition

Définition

Matrice d’adjacence d’un graphe orienté :

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 les entiers 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.

bannière à retenir

À retenir

Méthodologie :

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.
bannière exemple

Exemple

Prenons l’exemple des 88 groupes sanguins humains, avec leur rhésus, et la relation « … est donneur pour le groupe… ».
Ils sont représentés par le graphe ci-dessous.

Alt texte Image temporaire

Notons les groupes dans cet ordre :

O+\text O+ O\text O- A+\text A+ A\text A- B+\text B+ B\text B- AB+\text{AB}+ AB\text{AB}-
11 22 33 44 55 66 77 88
  • Le graphe est d’ordre 88, donc nous devons construire une matrice carrée AA d’ordre 88.

Pour construire la matrice, nous serons attentifs au sens de parcours des arêtes.

  • Détaillons la 1re1^\text{re} ligne de la matrice AA.

Du sommet O+\text O+, partent 44 arêtes, vers O+\text O+, A+\text A+, B+\text B+ et AB+\text AB+. Donc :

  • a1,1=a1,3=a1,5=a1,7=1\textcolor{#3CB371}{a{1,1}=a{1,3}=a{1,5}=a{1,7}=1} ;
  • les autres coefficients sont nuls.
  • De même, intéressons-nous à la 2e2^\text{e} ligne de AA.

Du sommet O\text{O}- partent des arêtes vers tous les autres sommets, y compris O\text{O}-.

  • Pour tout jj, a2,j=1 \textcolor{#FFA500}{a_{2,j}=1}.
  • Nous procédons ainsi ligne par ligne, et nous obtenons la matrice :

(1010101011111111001000100011001100001010000011110000001000000011)\begin{pmatrix} \textcolor{#3CB371}1 & 0 & \textcolor{#3CB371}1 & 0 & \textcolor{#3CB371}1 & 0 & \textcolor{#3CB371}1 & 0 \ \textcolor{#FFA500}1 & \textcolor{#FFA500}1 & \textcolor{#FFA500}1 & \textcolor{#FFA500}1 & \textcolor{#FFA500}1 & \textcolor{#FFA500}1 & \textcolor{#FFA500}1 & \textcolor{#FFA500}1 \ 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 \ 0 & 0 & 1 & 1 & 0 & 0 & 1 & 1 \ 0 & 0 & 0 & 0 & 1 & 0 & 1 & 0 \ 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 \ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 \end{pmatrix}

  • Nous observons que cette matrice n’est pas symétrique, contrairement aux matrices d’adjacence d’un graphe non orienté.

Voyons maintenant comment représenter un graphe dont on connaît la matrice d’adjacence.

bannière exemple

Exemple

Nous cherchons le graphe associé à la matrice suivante :

A=(111010110)A=\begin{pmatrix} 1 & 1 & 1 \ 0 & 1 & 0 \ 1 & 1 & 0 \end{pmatrix}

  • Cette matrice est d’ordre 33, donc le graphe dont elle est la matrice d’adjacence est d’ordre 33 : il y a trois sommets, que l’on notera 11, 22 et 33.
  • En observant la 1re1^\text{re} ligne, nous déduisons que du sommet 11 partent trois arêtes vers les sommets 11, 22 et 33.
  • En observant la 2e2^\text{e} ligne, nous déduisons que du sommet 22 part une arête vers 22 – c’est donc une boucle. Il n’y a pas d’arête vers le sommet 11 : nous en déduisons qu’il s’agit d’un graphe orienté.

Nous aurions pu également le déduire en observant la matrice et en constatant qu’elle n’est pas symétrique.

  • Voici donc le graphe orienté obtenu :

Alt texte Image temporaire

Nous allons maintenant nous servir des matrices d’adjacence pour déterminer le nombre de chaînes ou de chemins de longueur donnée entre deux sommets.

Nombre de chemins de longueur nn entre deux sommets

Prenons l’exemple d’un parcours sportif où il y a plusieurs ateliers : un saut de haies, des barres parallèles, des espaliers et un saute-mouton.

  • Les parcours conseillés entre les différents ateliers sont schématisés par les arêtes du graphe orienté ci-dessous.

Alt texte Image temporaire

Départ Barres parallèles Espaliers Saut de haies Saute-mouton Arrivée
DD PP EE HH SS AA

Alex, qui vient de commencer le sport mais aime la variété, cherche le nombre de parcours de longueur 33 entre le départ DD et l’arrivée AA, bien sûr en respectant les sens conseillés.
Pour trouver ce nombre, nous allons utiliser la propriété suivante.

bannière propriete

Propriété

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.
bannière demonstration

Démonstration

Considérons un graphe GG d’ordre nn de sommets S1S1, S2S2, …, Sn1S{n-1}, SnSn, et AA sa matrice d’adjacence.
SiSi et SjSj sont deux sommets quelconques de ce graphe.

Quel que soit mNm\in \mathbb N^*, on note : PmPm la propriété : « (Am)i,j(A^m ){i,j} est le nombre de chaînes de longueur mm entre SiSi et SjSj ».

  • Nous allons démontrer cette propriété par récurrence.
  • Initialisation : démontrons P1P_1.

(A1)i,j=(A)i,j(A^1 ){i,j} = (A){i,j} est le coefficient ai,ja{i,j} de la matrice AA.
D’après la définition de la matrice d’adjacence, ai,ja
{i,j} est le nombre d’arêtes qui relient SiSi et SjSj ; c’est donc le nombre de chaînes de longueur 11 entre SiSi et SjSj.

  • P1P_1 est donc vraie.
  • Hérédité : supposons qu’il existe mNm\in \mathbb N^* tel que PmP_m soit vraie.

Nous supposons donc que (Am)i,j(A^m ){i,j} est le nombre de chaînes de longueur mm entre SiSi et SjSj, quels que soient les sommets SiSi et SjS_j.

Considérons une chaîne de longueur m+1m+1.
Nous pouvons la décomposer en deux chaînes consécutives :

  • une chaîne de longueur mm qui part du sommet SiSi jusqu’à un sommet quelconque, que l’on notera SkSk ;
  • puis une chaîne de longueur 11 qui part de SkSk jusqu’à SjSj.

Dénombrons ces chaînes.

  • D’après l’hypothèse de récurrence PmPm, le nombre de chaînes de longueur mm entre SiSi et SkSk est (Am)i,k(A^m ){i,k} , le coefficient de la matrice AmA^m placé en i-eˋmei\text{-ème} ligne et k-ieˋmek\text{-ième} colonne.

Pour chacune de ces chaînes de longueur mm, il y a ak,ja{k,j} arêtes entre SkSk et SjSj, donc il y a ak,ja{k,j} chaînes de longueur 11.
Donc le nombre de chaînes de longueur m+1m+1 qui passent par SkSk au bout de mm arêtes est (Am)i,k×ak,j(A^m ){i,k}\times a_{k,j}

  • Pour avoir le nombre total de ces chaînes de longueur m+1m+1, nous devons donc faire la somme sur l’ensemble des sommets SkS_k possibles.

Ainsi le nombre de chaînes de longueur m+1m+1 entre SiSi et SjSj est :

(Am)i,1×a1,j+(Am)i,2×a2,j++(Am)i,n×an,j(A^m){i,1}\times a{1,j}+(A^m ){i,2}\times a{2,j}+…+ (A^m ){i,n} \times a{n,j}

Nous nous rappelons que c’est le coefficient placé sur la ligne ii et la colonne jj, obtenu en multipliant la matrice AmA^m par la matrice AA :

Am×A=Am+1A^m\times A=A^{m+1}

Nous avons donc montré que (Am+1)i,j(A^{m+1}){i,j} est le nombre de chaînes de longueur m+1m+1 entre SiSi et SjS_j.

  • Pm+1P_{m+1} est vraie.
  • Conclusion : la propriété PmPm : « (Am)i,j(A^m){i,j} est le nombre de chaînes de longueur mm entre SiSi et SjSj », est vraie pour tout mNm\in \mathbb N^*.

Remarque :
Cette démonstration est juste que le graphe soit orienté ou non.

bannière exemple

Exemple

Reprenons l’exemple du début de ce paragraphe :

Alt texte Image temporaire

bannière à retenir

À retenir

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é.

Appliquons cette méthode ici.

  • La matrice d’adjacence de ce graphe est une matrice carrée AA d’ordre 66 puisqu’il y a 66 sommets.

Écrivons cette matrice en utilisant la méthode que nous avons vue au point b : nous ordonnons les sommets dans l’ordre où ils sont écrits :

Départ Barres parallèles Espaliers Saut de haies Saute-mouton Arrivée
DD PP EE HH SS AA
11 22 33 44 55 66
bannière attention

Attention

Comme c’est un graphe orienté, nous ne comptons que les arêtes qui partent du sommet vers un autre.

A=(011100000001000111010000000101000000)A=\begin{pmatrix} 0 & 1 & 1 & 1 & 0 & 0 \ 0 & 0 & 0 & 0 & 0 & 1 \ 0 & 0 & 0 & 1 & 1 & 1 \ 0 & 1 & 0 & 0 & 0 & 0 \ 0 & 0 & 0 & 1 & 0 & 1 \ 0 & 0 & 0 & 0 & 0 & 0 \end{pmatrix}

  • Calculons maintenant A3A^3, puisque nous cherchons les chemins de longueur 33.

À l’aide de la calculatrice, nous obtenons :

A3=(010102000000010001000000000001000000)A^3=\begin{pmatrix} 0 & \purple 1 & 0 & \textcolor{#FFA500}1 & 0 & \red 2 \ 0 & 0 & 0 & 0 & 0 & 0 \ 0 & 1 & 0 & 0 & 0 & \green 1 \ 0 & 0 & 0 & 0 & 0 & 0 \ 0 & 0 & 0 & 0 & 0 & \blue 1 \ 0 & 0 & 0 & 0 & 0 & 0 \end{pmatrix}

Le coefficient cherché est le coefficient (A3)1,6(A^3){1,6} puisqu’on cherche le nombre de chemins de longueur 33 qui partent de DD (1re1^\text{re} ligne) vers AA (6e6^\text{e} colonne).
Nous lisons dans la matrice que (A3)1,6=2\red{(A^3 )
{1,6}= 2}.

  • Cela signifie qu’il n’y a que 2\red 2 chemins de longueur 33 qui partent de DD vers AA.

Si Alex voulait parcourir d’autres chemins de longueur 33 et terminer tout de même à l’arrivée, il pourrait tricher en partant des espaliers, car il existe entre EE et AA 1\green 1 chemin de longueur 33, ou en commençant par le saute-mouton, puisque là aussi il existe 1\blue 1 chemin de longueur 33 qui mène de SS à AA.

Remarquons enfin que, s’il respecte le départ et souhaite se limiter à un chemin de longueur 33, il peut aussi s’arrêter aux barres parallèles (1\purple 1 chemin entre DD et PP) ou au saut de haies (1\textcolor{#FFA500}1 chemin aussi entre DD et HH).

Dans cet exemple, nous avons pris un graphe d’ordre 66.
Mais les applications dans les réseaux routiers ou les interactions entre membres d’un même réseau social peuvent impliquer plusieurs centaines de sommets et des chemins plus longs à trouver.
L’utilisation de cette propriété et des moyens de traitement informatiques permettent d’optimiser les chemins entre deux sommets d’un graphe.

Conclusion :

Dans ce cours, nous avons défini ce que sont un graphe non orienté et un graphe orienté. Ils permettent de modéliser de manière géométrique et matricielle un ensemble d’éléments et une relation qui les lie. On les utilise dans de nombreuses applications.
Dans un prochain cours, nous étudierons une application importante des graphes pondérés.