Les graphes peuvent être représentés de trois façons : la première c’est ce qu’on a déjà vu, la représentation graphique. Elle est très utile pour comprendre les relations et pour les pouvoir voir visuellement, néanmoins quand il y a un nombre très élevé de connexion c’est plus difficile de faire une représentation qui puisse se comprendre. C’est à cause de cela qu’il est très utile d'utiliser des matrices pour représenter des graphes. De cette façon, on peut savoir plus rapidement si deux sommets sont communiqués ou quel est le chemin le plus court.

 

Il y a différentes types de matrices:

• Matrices d’incidence→  soit un graphe G = (V, E) avec n sommets {A, B, ..., n} et v arêtes {AB, BC, ...,v} et sa matrice d’incidence M=(mAn) c’est la matrice d'ordre n × v, qui donne information sur les connexions entre sommets et arêtes. 

• mAn= 1 si AB est incident en A

• mAn=0 si AB n’est pas incident en A

 

• Matrices de distances→ comme son nom l'indique, ce type de matrice donne information sur la longueur des arêtes. Cela veut dire que les graphes qui sont représentés pour ces matrices doivent être obligatoirement étiquetés. Soit un graphe G=(V,E) avec n sommets {A,B,, ..., n} sa matrice d’adjacence M=(mAn) c’est la matrice d'ordre n × n, qui donne information sur les distances entre sommets. 

• mAn= k si A et B sont adjacents, soit k le poids de l'étiquette

• mAn=0 si A et B ne sont pas adjacents

 

• Matrices d'adjacence→  soit un graphe G = (V, E) avec n sommets {A,B,, ..., n} sa matrice d’adjacence M=(mAn) c’est la matrice d'ordre n × n, qui donne information sur les connexions entre sommets.

• mAn= 1 si A et B sont adjacents

• mAn=0 si A et B ne sont pas adjacents

 

On va se centrer dans ce dernier type, bien que sont les plus utilisés car elles peuvent s’utiliser pour tout type de graphes, bien pondérés ou pas. En addition, elles servent à trouver le nombre de chemins de la longueur qu’on veut, en multipliant la matrice. On va voir un exemple:

 

Ce graphe G est formé par:

 

• V=[A,B,C,D,E] → #V=5

• E=[AB,AC,BC,CD,DE,EA] → #E=6

Donc sa représentation matriarcale est la suivante:

 

     

 

Avec cette première matrice on peut voir si les sommets sont adjacents ou non. Comme le graphe est non dirigé, et les arêtes  non pas de direction, aucune arête entre deux sommets sera une connexion qu’on identifiera dans la matrice comme un 1. Cette représentation nous donne des informations sur la quantité de chemins de longueur 1 entre deux sommets. 

 

Si on multiplie cette même matrice par elle même, on trouvera la quantité de chemins de longueur 2 qu’il y a entre les sommets:

 

 

 

​

​

​

Par exemple, si on regarde les connexions entre les sommets A et D, théoriquement il y a deux chemins de longueur 2 qui les unissent et en revanche il n’y a aucun de longueur 1.

 

 

 

 

 

 

De la même façon qu’on a trouvé la matrice du graphe G des chemins de longueur 2, donc M2, on peut trouver la matrice des chemins de toutes les longueurs possibles. La seule chose qu’il faut faire c’est multiplier la matrice résultant par l’originale, donc si on veut calculer Mnon devra multiplier Mn-1· M. On a vu que les matrices ne sont seulement binaires bien que dépendant de la quantité de chemins, on pourra trouver numéros plus grands que 1, vu dans l’exemple de la M2, où on a apprécié quelques connexions de longueur 2 qui avaient 3 options différentes.