VAD ÄR EN ADJACENCY-MATRIS

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_jmed 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_ioch 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.