Dans cet article, nous allons discuter de la matrice d'adjacence ainsi que de sa représentation.

Définition de la matrice de contiguïté

En théorie des graphes, une matrice d'adjacence est une manière dense de décrire la structure finie d'un graphe. C'est la matrice 2D qui est utilisée pour cartographier l'association entre les nœuds du graphe.

Si un graphique a n nombre de sommets, alors la matrice de contiguïté de ce graphe est nxn , et chaque entrée de la matrice représente le nombre d'arêtes d'un sommet à l'autre.

Une matrice de contiguïté est également appelée matrice de connexion . Parfois, on l'appelle aussi un Matrice de sommets .

Représentation matricielle de contiguïté

Si un graphe non orienté G se compose de n sommets alors la matrice de contiguïté d'un graphe est la matrice n x n A = [aij] et définie par -

un _je = 1 {s'il existe un chemin à partir de V _je à V _j }

un _je = 0 {Sinon}

Voyons quelques-uns des points importants concernant la matrice de contiguïté.

• S'il existe une arête entre le sommet V _je et V _j , où i est une ligne et j est une colonne, alors la valeur de a _je = 1.
• S'il n'y a pas d'arête entre le sommet V _je et V _j , alors la valeur d'un _je = 0.
• S'il n'y a pas de boucles automatiques dans le graphe simple, alors la matrice de sommets (ou matrice de contiguïté) doit avoir des 0 dans la diagonale.
• Une matrice de contiguïté est symétrique pour un graphe non orienté. Il précise que la valeur dans le i ^ème rangée et j ^ème la colonne est égale à la valeur en j ^ème rangée je ^ème
• Si la matrice de contiguïté est multipliée par elle-même, et s'il y a une valeur non nulle est présente au i ^ème rangée et j ^ème colonne, alors il y a la route de V _je à V _{j ­ ­} avec une longueur équivalente à 2. La valeur non nulle dans la matrice de contiguïté représente que le nombre de chemins distincts est présent.

Remarque : Dans une matrice de contiguïté, 0 représente qu'il n'existe aucune association entre deux nœuds, tandis que 1 représente qu'il existe une association entre deux nœuds.

Comment créer une matrice de contiguïté ?

Supposons qu'il existe un graphique g avec n nombre de sommets, alors la matrice de sommets (ou matrice de contiguïté) est donnée par -

UNE = une _onze un ₁₂ . . . . . un _1n un _vingt-et-un un ₂₂ . . . . . un _2n . . . . . . . . . un _n1 un _n2 . . . . . un _nn

Où le un _je est égal au nombre d'arêtes du sommet i à j. Comme mentionné ci-dessus, la matrice d'adjacence est symétrique pour un graphe non orienté, donc pour un graphe non orienté, un _je = un _hé .

Lorsque les graphiques sont simples et qu'il n'y a pas de poids sur les arêtes ou sur plusieurs arêtes, alors les entrées de la matrice de contiguïté seront 0 et 1. S'il n'y a pas d'auto-boucles, alors les entrées diagonales de la matrice de contiguïté seront 0.

Voyons maintenant la matrice d'adjacence pour un graphe non orienté et pour les graphes orientés.

Matrice de contiguïté pour un graphe non orienté

Dans un graphe non orienté, les arêtes ne sont pas associées aux directions qui leur sont associées. Dans un graphe non orienté, s'il existe une arête entre le sommet A et le sommet B, alors les sommets peuvent être transférés de A à B ainsi que de B à A.

Considérons le graphe non orienté ci-dessous et essayons d'en construire la matrice de contiguïté.

Dans le graphique, nous pouvons voir qu'il n'y a pas d'auto-boucle, donc les entrées diagonales de la matrice adjacente seront 0. La matrice de contiguïté du graphique ci-dessus sera -

Matrice de contiguïté pour un graphe orienté

Dans un graphe orienté, les arêtes forment une paire ordonnée. Les arêtes représentent un chemin spécifique d'un sommet A à un autre sommet B. Le nœud A est appelé nœud initial, tandis que le nœud B est appelé nœud terminal.

Considérons le graphe orienté ci-dessous et essayons d'en construire la matrice de contiguïté.

Dans le graphique ci-dessus, nous pouvons voir qu'il n'y a pas d'auto-boucle, donc les entrées diagonales de la matrice adjacente seront 0. La matrice de contiguïté du graphique ci-dessus sera -

Propriétés de la matrice de contiguïté

Certaines des propriétés de la matrice de contiguïté sont répertoriées comme suit :

• Une matrice de contiguïté est une matrice qui contient des lignes et des colonnes utilisées pour représenter un graphique simple étiqueté avec les nombres 0 et 1 à la position de (V _je , DANS _j ), selon la condition de savoir si les deux V _{je ­} et V _j sont adjacents.
• Pour un graphe orienté, s'il existe une arête entre le sommet i ou V _je au sommet j ou V _j , alors la valeur de A[V _je ][DANS _j ] = 1, sinon la valeur sera 0.
• Pour un graphe non orienté, s'il existe une arête entre le sommet i ou V _je au sommet j ou V _j , alors la valeur de A[V _je ][DANS _j ] = 1 et A[V _j ][DANS _je ] = 1, sinon la valeur sera 0.

Voyons quelques questions de la matrice de contiguïté. Les questions ci-dessous portent sur les graphiques pondérés non orientés et orientés.

REMARQUE : Un graphique est dit pondéré si chaque arête se voit attribuer un nombre positif, appelé poids de l’arête.

Question 1 - Quelle sera la matrice de contiguïté pour le graphique pondéré non orienté ci-dessous ?

Solution - Dans la question donnée, il n’y a pas d’auto-boucle, il est donc clair que les entrées diagonales de la matrice adjacente pour le graphique ci-dessus seront 0. Le graphique ci-dessus est un graphique non orienté pondéré. Les poids sur les bords du graphique seront représentés comme les entrées de la matrice de contiguïté.

La matrice de contiguïté du graphique ci-dessus sera -

Question 2 - Quelle sera la matrice de contiguïté pour le graphique pondéré dirigé ci-dessous ?

Solution - Dans la question donnée, il n’y a pas d’auto-boucle, il est donc clair que les entrées diagonales de la matrice adjacente pour le graphique ci-dessus seront 0. Le graphique ci-dessus est un graphique orienté pondéré. Les poids sur les bords du graphique seront représentés comme les entrées de la matrice de contiguïté.

La matrice de contiguïté du graphique ci-dessus sera -

J'espère que cet article vous sera utile afin de comprendre la matrice de contiguïté. Ici, nous avons discuté de la matrice de contiguïté ainsi que de sa création et de ses propriétés. Nous avons également discuté de la formation de matrices d'adjacence sur des graphes orientés ou non, qu'ils soient pondérés ou non.