Représentations matricielles des graphes, cas général et cas particuliers
Définition :
La matrice B est la matrice Booléenne associée à un graphe donné de n points si et seulement si elle comporte n lignes et n colonnes contenant des valeurs booléennes et B(i,j)="vrai" si et seulement si l'arc (i,j) existe.
Définition :
La matrice B est la matrice en variables 0-1 associée à un graphe donné de n points si et seulement si elle comporte n lignes et n colonnes et B(i,j)=1 si l'arc (i,j) existe et 0 sinon.
Matrice booléenne ou matrice en variables 0-1 d'un graphe
Ces deux représentations sont totalement équivalentes (si ce n'est le type des éléments de la matrice).
La matrice en variable 0-1 est la représentation le plus souvent utilisée tout au long du module.
Avec la matrice Booléenne comme les éléments possèdent les valeurs "vrai" et "faux", on peut effectuer des opérations booléennes sur les matrices.
Avec la matrice en variable 0-1, en considérant, par convention, que 0 représente "faux" et 2 représente "vrai", on peut indifféremment effectuer des opérations booléennes ou des opérations sur des entiers.
Cliquez sur les flèches devant Suivant ou derrière Précédent pour faire tourner les exemples.
Matrice en variables 0-1 des graphes bi-partis
Cliquez sur les flèches devant Suivant ou derrière Précédent pour faire tourner les exemples.
On peut remarquer que de nombreuses lignes et de nombreuses colonnes ne contiennent que des 0.
Pour les graphes bi-partis, on peut donc limiter la représentation de la matrice en variable 0-1 à la seule partie utile, c'est-à-dire les lignes qui correspondent à E1 et les colonnes qui correspondent à E2.
Restriction à la partie utile pour les graphes bi-partis
Cliquez sur les flèches devant Suivant ou derrière Précédent pour faire tourner les exemples.
Il est à noter que lorsqu'il y a des points isolés, ils sont mis arbitrairement dans E1 ou dans E2. Ce qui donne plusieurs solutions possibles pour la partie utile du graphe. Nous avons retenu ici les mêmes sous-ensemble E1 et E2 pour la représentation graphique et pour la représentation simplifiée matricielle.
Matrice en variables 0-1 des arborescences et des forêts
Cliquez sur les flèches devant Suivant ou derrière Précédent pour faire tourner les exemples.
On peut remarquer que de très nombreux éléments de la matrice ne contiennent que des 0.
Pour les forêts et les arborescences, une matrice très concentrée de seulement n lignes et 2 colonnes a été proposée, elle est appelée la matrice d'enchaînement.
Définition : Matrice d'enchaînement
Une forêt peut être représentée par sa matrice d'enchaînement composée de 2 tableaux de n éléments.
Le premier tableau, noté FILS contient le numéro du premier fils de chaque point (le premier fils est le premier successeur).
Le deuxième tableau, noté SUIVANT contient le numéro du frère suivant de chaque point, les frères sont considérés dans l'ordre des numéros des successeurs du seul prédécesseur du point (ou père du point) ou la racine de l'arborescence suivante si le point est une racine.
Si un point n'a pas de fils (ou successeurs) ou n'a pas de suivant (c'est le frère cadet du père), alors on met la valeur NIL généralement implémentée dans les algorithmes par la valeur -1 (les numéros de lignes allant de 1 à n).
Par convention, s'il n'y a qu'une seule arborescence, on donne à la racine le numéro 1 et la racine est donc sur la première ligne.
Pour une arborescence, il est intéressant d'ajouter un point fictif que l'on numérote 0, dont le premier fils est la première arborescence et qui n'a pas de frère.
Matrice d'enchaînement pour les forêts et les arborescences
Cliquez sur les flèches devant Suivant ou derrière Précédent pour faire tourner les exemples.
Vous pouvez constater que cette représentation minimise la mémoire utilisée pour représenter les forêts ou les arborescences.
Parfois, pour les points qui n'ont pas de fils, on remplace le -1 par - le numéro de la racine de l'arborescence. Ceci peut être intéressant dans certains algorithmes (quand on arrive à une feuille, on peut retourner directement à la racine).
Définition : Avantages et inconvénients de la matrice d'enchaînement
La matrice d'enchaînement est idéal pour les algorithmes où on parcourt l'arborescence en partant de la racine.
Elle ne convient pas si on veut cheminer des feuilles vers les racines.
Si on veut pouvoir parcourir les chemins dans les deux sens, en descendant dans l'arborescence et en remontant dans l'arborescence, il suffit d'ajouter un tableau PERE où à chaque point on associe son seul prédécesseur.
On a alors à la fois l'arborescence et l'anti-arborescence dans la représentation à trois tableaux.
Définition :
La matrice A est dite matrice associée à un graphe donné de n points, si une valeur particulière attribuée à A(i,j) permet de reconnaître qu'un arc n'existe pas, alors que la valeur est un attribut de l'arc lorsque l'arc existe.
Par exemple, la matrice associée A peut contenir des valeurs positives avec la convention que 0 signifie que l'arc n'existe pas. si A(i,j) est strictement positif, A(i,j) représente la longueur de l'arc qui existe.
On peut également prendre des valeurs positive sou nulles pour les arcs qui existent et -1 pour indiquer les arcs qui n'existe pas.
La matrice associée permet en fait de représenter deux informations avec une seule matrice : existence ou non de l'arc et valeur de l'arc.
Nous ne fournissons pas d'animation pour la matrice associée, il y en a à plusieurs reprises dans ce module de base. La seule différence par rapport à la matrice booléenne et que l'on met des valeurs sur les arcs pour la représentation graphique associée.
Avantages des matrices booléennes, en variables 0-1 ou associées
On a un accès direct à la connaissance de l'existence des arcs.
On peut effectuer des calculs matriciels avec des opérations booléennes pour effectuer, par exemple des unions, des intersections ou des produits de graphes.
Inconvénients des matrices booléennes, en variables 0-1 ou associées
Si l'on souhaite, par exemple, visiter les successeurs d'un point, il faut balayer toute la ligne correspondant à ce point en ignorant les points qui ne sont pas des successeurs.
Par ailleurs, si le graphe contient beaucoup de points et peu d'arcs, ces matrices prennent beaucoup de places en mémoire.
C'est par exemple le cas pour un GPS qui travaille sur un réseau routier pour calculer les itinéraires entre deux points très éloignés, alors qu'il n'y a que des arcs qu'entre des points géographiquement proches.
IMPLÉMENTATION / Graphe dense
Pour les graphes denses, on utilise toujours une matrice booléenne ou une matrice d'entiers.
En cas de problèmes de mémoire, on peut travailler au niveau des "bits", avec des fonctions qui positionnent le bit pour déclarer un arc ou qui lisent un bit pour savoir si l'arc existe.
IMPLÉMENTATION / Graphe peu dense
Pour les graphes très pauvres en arcs, il peut être préférable d'utiliser des listes de prédécesseurs et/ou des listes de successeurs.
Comme présenté lors de la représentation des graphes par des listes, on peut les implémenter de manière contiguë ou de manière chaînée.
Si on représente les graphes de manière chaînée et que plusieurs informations sont liées à chaque arc et que l'on souhaite gérer ces informations de manière fiable (les modifier de manière identique dans la liste de prédécesseurs et dans celle des successeurs), dans ce cas, il faut utiliser une liste doublement chaînée, derrière les valeurs associées à tout arc, un premier pointeur permet d'aller de successeur en successeur alors que le deuxième pointeur permet d'aller de prédécesseur en prédécesseur. A chaque point est associé un pointeur vers son premier successeur et un pointeur vers son premier prédécesseur. Par convention, "NIL" représente la fin des listes chaînées.
La représentation chaînée est préférable à la représentation contiguë lorsque le graphe est modifié au cours de l'algorithme (il gagne ou perd des arcs au fur et à mesure des itérations).
