< Retour|Suivant|Contenu >
Matrice d’adjacence: Sommet à Vertex
La famille de graphes soutient que l’une des meilleures façons de les représenter dans une matrice est de compter le nombre d’arêtes entre deux sommets adjacents.
Deux sommets sont dits adjacents ou voisins s’ils supportent au moins une arête commune.
Commençons par l’exemple
Le graphique ci-dessous a trois sommets. Ainsi, nous faisons une matrice d’adjacence de taille 3 par 3. Ensuite, nous mettons le nom des sommets sur le côté de la matrice. Regardez l’image et nous commençons par une matrice vide. Seuls les noms des sommets sont là
Pour remplir la contiguïté matrice, nous regardons le nom du sommet dans la ligne et la colonne. Si ces sommets sont reliés par une arête ou plus, nous comptons le nombre d’arêtes et mettons ce nombre comme élément de matrice.
Sommet 
et sommet 
a un bord commun, nous disons que Vertex 
et sommet 
sont adjacentes (voisines). Nous entrons le nombre d’arêtes dans la cellule matricielle qui correspondent au sommet 
et sommet 
.
Sommet 
et 
est adjacente par un bord. Ainsi, nous entrons le nombre d’arêtes dans la cellule matricielle qui correspondent au Sommet 
et 
.
De même, vertex 
et 
est reliée par un bord. Ainsi, nous entrons le nombre d’arêtes dans la cellule matricielle qui correspondent au sommet 
et 
Il n’y a pas d’autre bord sur le graphique, nous mettons donc le reste des cellules non remplies dans la matrice comme zéro
La matrice pour représenter un graphique de cette façon est appelée matrice d’adjacence.
La taille de la matrice d’adjacence est égale au nombre de sommets du graphe. C’est une matrice carrée (c’est-à-dire que le nombre de lignes est égal au nombre de colonnes).
La matrice d’adjacence d’un graphe est symétrique car elle n’a pas de direction. Deux sommets partagent la même arête peuvent être appelés du premier au second, ou du second au premier. Par exemple, Vertex 
et vertex 
a un bord commun, alors element(a, b) = 1 et element(b, a) = 1.
Essayons un autre exemple :
Pouvez-vous créer la matrice d’adjacence de ce graphique? Essayez-le d’abord avant de regarder la réponse ci-dessous.
Le graphe a 3 sommets, nous faisons donc une taille de matrice 3 par 3. Nous mettons le nom des sommets sur le côté de la matrice.
Regardez maintenant le sommet 
et sommet 
. Combien d’arêtes les deux sommets supportent-ils ? Un. Ensuite, nous mettons cette valeur dans la matrice
Regardez vertex 
et vertex 
. Combien d’arêtes ces sommets supportent-ils ? Aucun. Ensuite, nous mettons la valeur zéro dans la cellule correspondante de la matrice
Ensuite, vous regardez vertex 
et sommet 
. Combien d’arêtes ces sommets supportent-ils ? Deux. Ensuite, nous entrons la matrice dans
Comme il n’y a pas d’autre bord dans le graphique, nous pouvons remplir la cellule vide avec des zéros. Ainsi, nous avons la réponse
Certains d’entre vous peuvent poser des questions sur la partie diagonale de la matrice, ces cellules sont-elles toujours nulles? Non, si vous trouvez que le graphe a une boucle dans certains sommets, vous pouvez remplir l’élément diagonal de la matrice d’adjacence avec le nombre de boucle.
Si un graphe a un sommet qui n’est connecté à aucun autre sommet, la matrice d’adjacence correspondant à ce sommet unique est nulle.
Veuillez vous entraîner à représenter le graphique ci-dessous dans la matrice d’adjacence.
(Voir la réponse à la page précédente)
Étant donné la matrice d’adjacence, pouvez-vous dessiner le graphique?
Vérifiez l’exemple d’application de la théorie des graphes dans le tutoriel de Q-Learning
< Retour|Suivant|Contenu >