I denne artikel skal vi diskutere tilstødende matrix sammen med dens repræsentation.

borde i latex

Adjacency matrix definition

I grafteori er en tilstødende matrix en tæt måde at beskrive den endelige grafstruktur på. Det er 2D-matrixen, der bruges til at kortlægge sammenhængen mellem grafknuderne.

Hvis en graf har n antal hjørner, så er nabomatrixen for denne graf n x n , og hver indgang i matricen repræsenterer antallet af kanter fra et toppunkt til et andet.

En adjacency matrix kaldes også som forbindelsesmatrix . Nogle gange kaldes det også en Vertex matrix .

Adjacency Matrix Repræsentation

Hvis en udirigeret graf G består af n hjørner, er nabomatrixen af ​​en graf n x n matrix A = [aij] og defineret ved -

-en_ij= 1 {hvis der findes en sti fra V_jegtil V_j}

-en_ij= 0 {Ellers}

Lad os se nogle af de vigtige punkter med hensyn til tilstødende matrix.

• Hvis der er en kant mellem top V_jegog V_j, hvor i er en række, og j er en kolonne, derefter værdien af ​​a_ij= 1.
• Hvis der ikke er nogen kant mellem top V_jegog V_j, så værdien af ​​en_ij= 0.
• Hvis der ikke er nogen selvløkker i den simple graf, så skal vertexmatricen (eller tilstødende matrix) have 0'er i diagonalen.
• En tilstødende matrix er symmetrisk for en urettet graf. Det specificerer, at værdien i i^thrække og j^thkolonne er lig med værdien i j^thrække i^th
• Hvis tilstødende matrix ganges med sig selv, og hvis der er en værdi, der ikke er nul, er til stede ved i^thrække og j^thkolonne, så er der ruten fra V_jegtil V_j­­med en længde svarende til 2. Værdien, der ikke er nul, i tilstødende matrix repræsenterer, at antallet af distinkte veje er til stede.

Bemærk: I en tilstødende matrix repræsenterer 0, at der ikke er nogen tilknytning mellem to noder, mens 1 repræsenterer, at der er en tilknytning mellem to noder.

Hvordan opretter man en adjacency matrix?

Antag, at der er en graf g med n antal hjørner, så er toppunktsmatrixen (eller tilstødende matrix) givet ved -

A = a_elleve-en₁₂. . . . . -en_1n-en_enogtyve-en₂₂. . . . . -en_2n. . . . . . . . . -en_n1-en_n2. . . . . -en_nn

java initialize array

Hvor a_ijer lig med antallet af kanter fra toppunktet i til j. Som nævnt ovenfor er Adjacency-matricen symmetrisk for en urettet graf, så for en urettet graf, en_ij= a_hee.

Når graferne er enkle, og der ikke er vægte på kanterne eller flere kanter, så vil indgangene i tilstødende matrix være 0 og 1. Hvis der ikke er nogen selvløkker, så vil de diagonale indgange af tilstødende matrix være 0.

Lad os nu se tilstødende matrix for en urettet graf og for rettede grafer.

Adjacency matrix for en urettet graf

I en urettet graf er kanter ikke forbundet med retningerne med dem. I en urettet graf, hvis der er en kant mellem toppunkt A og toppunkt B, så kan toppunkterne overføres fra A til B såvel som B til A.

Lad os overveje nedenstående urettede graf og forsøge at konstruere den tilstødende matrix af den.

I grafen kan vi se, at der ikke er nogen selvløkke, så de diagonale indtastninger af den tilstødende matrix vil være 0. Den tilstødende matrix af ovenstående graf vil være -

postorder traversering af binært træ

Adjacency matrix for en rettet graf

I en rettet graf danner kanter et ordnet par. Kanter repræsenterer en specifik vej fra et eller andet toppunkt A til et andet toppunkt B. Node A kaldes den indledende node, mens node B kaldes terminalknudepunktet.

Lad os overveje nedenstående rettede graf og forsøge at konstruere den tilstødende matrix af den.

I ovenstående graf kan vi se, at der ikke er nogen selvløkke, så de diagonale indtastninger af den tilstødende matrix vil være 0. Den tilstødende matrix af ovenstående graf vil være -

Egenskaber for tilstødende matrix

Nogle af egenskaberne for tilstødende matrix er angivet som følger:

• En tilstødende matrix er en matrix, der indeholder rækker og kolonner, der bruges til at repræsentere en simpel mærket graf med tallene 0 og 1 i positionen (V_jeg, IN_j), i henhold til betingelsen om, hvorvidt de to V_{jeg ­} og V_jer tilstødende.
• For en rettet graf, hvis der er en kant mellem vertex i eller V_jegtil vertex j eller V_j, derefter værdien af ​​A[V_jeg][I_j] = 1, ellers vil værdien være 0.
• For en urettet graf, hvis der er en kant, der eksisterer mellem vertex i eller V_jegtil vertex j eller V_j, derefter værdien af ​​A[V_jeg][I_j] = 1 og A[V_j][I_jeg] = 1, ellers vil værdien være 0.

Lad os se nogle spørgsmål om tilstødende matrix. Nedenstående spørgsmål er på de vægtede urettede og rettede grafer.

BEMÆRK: En graf siges at være den vægtede graf, hvis hver kant er tildelt et positivt tal, som kaldes kantens vægt.

Spørgsmål 1 - Hvad vil den tilstødende matrix være for nedenstående urettede vægtede graf?

Løsning - I det givne spørgsmål er der ingen selvløkke, så det er klart, at de diagonale indgange i den tilstødende matrix for ovenstående graf vil være 0. Ovenstående graf er en vægtet urettet graf. Vægtene på grafkanterne vil blive repræsenteret som indtastningerne af tilstødende matrix.

Tilstødende matrix af ovenstående graf vil være -

Spørgsmål 2 - Hvad vil være naboskabsmatricen for den nedenstående vejede graf?

Løsning - I det givne spørgsmål er der ingen selvløkke, så det er klart, at de diagonale indtastninger af den tilstødende matrix for ovenstående graf vil være 0. Ovenstående graf er en vægtet rettet graf. Vægtene på grafkanterne vil blive repræsenteret som indtastningerne af tilstødende matrix.

Tilstødende matrix af ovenstående graf vil være -

Håber denne artikel er gavnlig for dig for at forstå om tilstødende matrix. Her har vi diskuteret tilstødende matrix sammen med dens oprettelse og egenskaber. Vi har også diskuteret dannelsen af ​​tilstødende matrix på rettede eller urettede grafer, uanset om de er vægtet eller ej.

java erstatte alt