I denne artikkelen skal vi diskutere tilstøtningsmatrisen sammen med dens representasjon.

bord i lateks

Adjacency matrisedefinisjon

I grafteori er en tilstøtende matrise en tett måte å beskrive den endelige grafstrukturen på. Det er 2D-matrisen som brukes til å kartlegge assosiasjonen mellom grafnodene.

Hvis en graf har n antall toppunkter, så er tilstøtende matrisen til den grafen n x n , og hver oppføring av matrisen representerer antall kanter fra en toppunkt til en annen.

En tilstøtende matrise kalles også som tilkoblingsmatrise . Noen ganger kalles det også en Vertex matrise .

Adjacency Matrix Representation

Hvis en urettet graf G består av n toppunkter, er tilstøtende matrisen til en graf n x n matrise A = [aij] og definert av -

en_ij= 1 {hvis det finnes en bane fra V_Jegtil V_j}

en_ij= 0 {Ellers}

La oss se noen av de viktige punktene med hensyn til tilstøtningsmatrisen.

• Hvis det er en kant mellom toppunktet V_Jegog V_j, hvor i er en rad, og j er en kolonne, deretter verdien av a_ij= 1.
• Hvis det ikke er noen kant mellom toppunktet V_Jegog V_j, deretter verdien av en_ij= 0.
• Hvis det ikke er noen selvløkker i den enkle grafen, bør toppunktmatrisen (eller nabomatrisen) ha 0-er i diagonalen.
• En tilstøtende matrise er symmetrisk for en urettet graf. Den spesifiserer at verdien i i^thrad og j^thkolonne er lik verdien i j^thrad i^th
• Hvis tilstøtende matrisen multipliseres med seg selv, og hvis det er en verdi som ikke er null er tilstede ved i-en^thrad og j^thkolonne, så er det ruten fra V_Jegtil V_j­­med en lengde tilsvarende 2. Verdien som ikke er null i tilstøtende matrisen representerer at antallet distinkte baner er tilstede.

Merk: I en tilstøtende matrise representerer 0 at det ikke er noen assosiasjon mellom to noder, mens 1 representerer at det er en assosiasjon mellom to noder.

Hvordan lage en adjacency-matrise?

Anta at det er en graf g med n antall toppunkter, så er toppunktmatrisen (eller tilgrensningsmatrisen) gitt av -

A = a_elleveen₁₂. . . . . en_1nen_tjueenen₂₂. . . . . en_2n. . . . . . . . . en_n1en_n2. . . . . en_nn

java-streng til array

Hvor a_ijer lik antall kanter fra toppunktet i til j. Som nevnt ovenfor er Adjacency-matrisen symmetrisk for en urettet graf, så for en urettet graf, en_ij= a_hee.

Når grafene er enkle og det ikke er noen vekter på kantene eller flere kanter, vil oppføringene til tilstøtende matrisen være 0 og 1. Hvis det ikke er noen selvløkker, vil de diagonale oppføringene til tilstøtende matrisen være 0.

La oss nå se tilstøtende matrisen for en urettet graf og for rettet grafer.

Adjacency matrise for en urettet graf

I en urettet graf er ikke kanter assosiert med retningene med dem. I en urettet graf, hvis det er en kant mellom toppunkt A og toppunkt B, kan toppunktene overføres fra A til B så vel som B til A.

La oss vurdere den under-urettede grafen og prøve å konstruere den tilstøtende matrisen til den.

I grafen kan vi se at det ikke er noen selvløkke, så de diagonale oppføringene til den tilstøtende matrisen vil være 0. Tilstøtende matrisen til grafen ovenfor vil være -

postordre traversering av binært tre

Adjacency-matrise for en rettet graf

I en rettet graf danner kanter et ordnet par. Kanter representerer en spesifikk bane fra et toppunkt A til et annet toppunkt B. Node A kalles startnoden, mens node B kalles terminalnoden.

La oss vurdere den rettet grafen nedenfor og prøve å konstruere den tilstøtende matrisen til den.

I grafen ovenfor kan vi se at det ikke er noen selvløkke, så de diagonale oppføringene til den tilstøtende matrisen vil være 0. Tilstøtende matrisen til grafen ovenfor vil være -

Egenskaper til tilstøtningsmatrisen

Noen av egenskapene til tilstøtende matrisen er oppført som følger:

• En tilstøtende matrise er en matrise som inneholder rader og kolonner som brukes til å representere en enkel merket graf med tallene 0 og 1 i posisjonen til (V_Jeg, IN_j), i henhold til betingelsen om de to V_{Jeg ­} og V_jer tilstøtende.
• For en rettet graf, hvis det er en kant mellom toppunktet i eller V_Jegtil Vertex j eller V_j, deretter verdien av A[V_Jeg][I_j] = 1, ellers vil verdien være 0.
• For en urettet graf, hvis det er en kant som eksisterer mellom toppunktet i eller V_Jegtil Vertex j eller V_j, deretter verdien av A[V_Jeg][I_j] = 1 og A[V_j][I_Jeg] = 1, ellers vil verdien være 0.

La oss se noen spørsmål om tilstøtningsmatrisen. Spørsmålene nedenfor er på de vektede urettede og rettet grafene.

MERK: En graf sies å være den vektede grafen hvis hver kant er tildelt et positivt tall, som kalles vekten av kanten.

Spørsmål 1 - Hva vil være tilgrensningsmatrisen for den urettede vektede grafen nedenfor?

Løsning - I det gitte spørsmålet er det ingen selvløkke, så det er klart at de diagonale oppføringene til den tilstøtende matrisen for grafen ovenfor vil være 0. Grafen ovenfor er en vektet urettet graf. Vektene på grafkantene vil bli representert som oppføringene til tilstøtende matrisen.

Tilstøtende matrisen til grafen ovenfor vil være -

Spørsmål 2 - Hva vil være nabomatrisen for den veide grafen nedenfor?

Løsning - I det gitte spørsmålet er det ingen selvløkke, så det er klart at de diagonale oppføringene til den tilstøtende matrisen for grafen ovenfor vil være 0. Grafen ovenfor er en vektet rettet graf. Vektene på grafkantene vil bli representert som oppføringene til tilstøtende matrisen.

Tilstøtende matrisen til grafen ovenfor vil være -

Håper denne artikkelen er nyttig for deg for å forstå om tilstøtende matrise. Her har vi diskutert tilstøtningsmatrisen sammen med dens opprettelse og egenskaper. Vi har også diskutert dannelsen av tilstøtende matrise på dirigerte eller urettede grafer, enten de er vektet eller ikke.

offentlig vs privat java