TechCodeview

I den här artikeln kommer vi att diskutera närliggande matris tillsammans med dess representation.

java hej-program

Adjacency matris definition

Inom grafteorin är en närliggande matris ett tätt sätt att beskriva den ändliga grafstrukturen. Det är 2D-matrisen som används för att kartlägga sambandet mellan grafnoderna.

Om en graf har n antal hörn, då är den närliggande matrisen för den grafen n x n , och varje post i matrisen representerar antalet kanter från en vertex till en annan.

En närliggande matris kallas också som anslutningsmatris . Ibland kallas det också för a Vertex matris .

Adjacency Matrix Representation

Om en oriktad graf G består av n hörn så är närliggande matris för en graf n x n matris A = [aij] och definieras av -

a_{I j}= 1 {om det finns en sökväg från V_itill V_j}

a_{I j}= 0 {annars}

Låt oss se några av de viktiga punkterna med avseende på närliggande matris.

• Om det finns en kant mellan vertex V_ioch V_j, där i är en rad och j är en kolumn, sedan värdet av a_{I j}= 1.
• Om det inte finns någon kant mellan vertex V_ioch V_j, sedan värdet av a_{I j}= 0.
• Om det inte finns några självslingor i den enkla grafen, bör vertexmatrisen (eller närliggande matris) ha nollor i diagonalen.
• En närliggande matris är symmetrisk för en oriktad graf. Den anger att värdet i i^thrad och j^thkolumnen är lika med värdet i j^thrad i^th
• Om närliggande matris multipliceras med sig själv och om det finns ett värde som inte är noll finns det i i^thrad och j^thkolumn, så finns det rutten från V_itill V_j­­med en längd som motsvarar 2. Värdet som inte är noll i närliggande matris representerar att antalet distinkta vägar finns.

Notera: I en närliggande matris representerar 0 att det inte finns någon association mellan två noder, medan 1 representerar att det finns en association mellan två noder.

Hur skapar man en närliggande matris?

Anta att det finns en graf g med n antal hörn, då ges vertexmatrisen (eller närliggande matris) av -

A = a_elvaa₁₂. . . . . a_1na_tjugoetta₂₂. . . . . a_2n. . . . . . . . . a_n1a_n2. . . . . a_nn

Där a_{I j}är lika med antalet kanter från vertex i till j. Som nämnts ovan är Adjacency-matrisen symmetrisk för en oriktad graf, så för en oriktad graf, en_{I j}= a_hee.

När graferna är enkla och det inte finns några vikter på kanterna eller flera kanter, så kommer ingångarna i angränsande matris att vara 0 och 1. Om det inte finns några självslingor, blir de diagonala ingångarna i angränsande matris 0.

Låt oss nu se närliggande matris för en oriktad graf och för riktade grafer.

selen grunderna

Adjacency-matris för en oriktad graf

I en oriktad graf är kanter inte associerade med riktningarna med dem. I en oriktad graf, om det finns en kant mellan Vertex A och Vertex B, kan hörnen överföras från A till B såväl som B till A.

Låt oss betrakta den oriktade grafen nedan och försöka konstruera dess närliggande matris.

I grafen kan vi se att det inte finns någon självslinga, så de diagonala ingångarna för den intilliggande matrisen kommer att vara 0. Närliggande matrisen i grafen ovan kommer att vara -

Adjacency-matris för en riktad graf

I en riktad graf bildar kanter ett ordnat par. Kanter representerar en specifik väg från någon vertex A till en annan vertex B. Nod A kallas initialnod, medan nod B kallas terminalnod.

Låt oss betrakta den riktade grafen nedan och försöka konstruera dess närliggande matris.

I grafen ovan kan vi se att det inte finns någon självslinga, så de diagonala ingångarna för den intilliggande matrisen kommer att vara 0. Närliggande matrisen i grafen ovan kommer att vara -

java parseint

Egenskaper för närliggande matris

Några av egenskaperna hos närliggande matris listas enligt följande:

• En närliggande matris är en matris som innehåller rader och kolumner som används för att representera en enkel märkt graf med siffrorna 0 och 1 i positionen (V_jag, I_j), beroende på villkoret om de två V_{i ­} och V_jligger intill.
• För en riktad graf, om det finns en kant mellan vertex i eller V_itill Vertex j eller V_j, sedan värdet av A[V_i][I_j] = 1, annars blir värdet 0.
• För en oriktad graf, om det finns en kant som finns mellan vertex i eller V_itill Vertex j eller V_j, sedan värdet av A[V_i][I_j] = 1 och A[V_j][I_i] = 1, annars blir värdet 0.

Låt oss se några frågor om närliggande matris. Frågorna nedan handlar om de viktade oriktade och riktade graferna.

OBS: En graf sägs vara den viktade grafen om varje kant tilldelas ett positivt tal, vilket kallas kantens vikt.

Fråga 1 - Vad blir närliggande matris för nedanstående oriktade viktade graf?

Lösning - I den givna frågan finns det ingen självslinga, så det är tydligt att de diagonala ingångarna i den intilliggande matrisen för grafen ovan kommer att vara 0. Grafen ovan är en viktad oriktad graf. Vikterna på grafens kanter kommer att representeras som ingångarna i närliggande matris.

Närliggande matris i grafen ovan kommer att vara -

vackraste leendet

Fråga 2 - Vad blir närliggande matris för den riktade viktade grafen nedan?

Lösning - I den givna frågan finns det ingen självslinga, så det är tydligt att de diagonala ingångarna i den intilliggande matrisen för ovanstående graf kommer att vara 0. Grafen ovan är en vägd riktad graf. Vikterna på grafens kanter kommer att representeras som ingångarna i närliggande matris.

Närliggande matris i grafen ovan kommer att vara -

Hoppas den här artikeln är till nytta för dig för att förstå om närliggande matris. Här har vi diskuterat närliggande matris tillsammans med dess skapelse och egenskaper. Vi har också diskuterat bildandet av närliggande matris på riktade eller oriktade grafer, oavsett om de är viktade eller inte.