V tomto článku budeme diskutovat o matici sousednosti spolu s její reprezentací.

třídit haldy

Definice matice sousedství

V teorii grafů je matice sousednosti hustým způsobem popisu konečné struktury grafu. Je to 2D matice, která se používá k mapování asociace mezi uzly grafu.

Pokud má graf n počet vrcholů, pak je matice sousednosti tohoto grafu n x n a každý záznam matice představuje počet hran z jednoho vrcholu do druhého.

Matice sousedství se také nazývá jako spojovací matice . Někdy se také nazývá a Vertexová matice .

Znázornění matice sousedství

Pokud se neorientovaný graf G skládá z n vrcholů, pak matice sousednosti grafu je n x n matice A = [aij] a je definována jako -

A_ij= 1 {pokud existuje cesta z V_ik V_j}

A_ij= 0 {Jinak}

Podívejme se na některé důležité body s ohledem na matici sousedství.

• Pokud mezi vrcholem V existuje hrana_ia V_j, kde i je řádek a j je sloupec, pak hodnota a_ij= 1.
• Pokud mezi vrcholem V není žádná hrana_ia V_j, pak hodnota a_ij= 0.
• Pokud v jednoduchém grafu nejsou žádné vlastní smyčky, pak by matice vrcholů (nebo matice sousednosti) měla mít na diagonále 0s.
• Matice sousedství je pro neorientovaný graf symetrická. Specifikuje, že hodnota v i^čtřádek a j^čtsloupec se rovná hodnotě v j^čtřada i^čt
• Pokud je matice sousedství vynásobena sama sebou a pokud existuje nenulová hodnota, je přítomna na i^čtřádek a j^čtsloup, pak je tu trasa z V_ik V_j­­s délkou ekvivalentní 2. Nenulová hodnota v matici sousednosti představuje, že je přítomen počet odlišných cest.

Poznámka: V matici sousednosti 0 znamená, že mezi dvěma uzly neexistuje žádná asociace, zatímco 1 znamená, že mezi dvěma uzly existuje asociace.

Jak vytvořit matici sousedství?

Předpokládejme, že existuje graf G s n počet vrcholů, pak je matice vrcholů (nebo matice sousednosti) dána -

A = a_jedenáctA₁₂. . . . . A_1nA_{dvacet jedna}A₂₂. . . . . A_2n. . . . . . . . . A_n1A_n2. . . . . A_nn

Kde a_ijse rovná počtu hran od vrcholu i do j. Jak bylo uvedeno výše, matice sousedství je symetrická pro neorientovaný graf, takže pro neorientovaný graf je_ij= a_hee.

Když jsou grafy jednoduché a na hranách nebo více hranách nejsou žádné váhy, pak vstupy matice sousednosti budou 0 a 1. Pokud neexistují žádné samosmyčky, pak budou diagonální položky matice sousedství 0.

odhlaste se z účtu Google na Androidu

Nyní se podívejme na matici sousednosti pro neorientovaný graf a pro orientované grafy.

Matice sousedství pro neorientovaný graf

V neorientovaném grafu nejsou hrany spojeny se směry s nimi. Pokud v neorientovaném grafu existuje hrana mezi vrcholem A a vrcholem B, pak lze vrcholy přenést z A do B a také z B do A.

Uvažujme níže neorientovaný graf a pokusme se zkonstruovat jeho matici sousednosti.

V grafu vidíme, že neexistuje žádná vlastní smyčka, takže diagonální položky sousední matice budou 0. Matice sousednosti výše uvedeného grafu bude -

Matice sousedství pro orientovaný graf

V orientovaném grafu tvoří hrany uspořádaný pár. Hrany představují specifickou cestu z některého vrcholu A do jiného vrcholu B. Uzel A se nazývá počáteční uzel, zatímco uzel B se nazývá koncový uzel.

Uvažujme níže orientovaný graf a pokusme se z něj sestrojit matici sousednosti.

java webové služby

Ve výše uvedeném grafu vidíme, že neexistuje žádná vlastní smyčka, takže diagonální položky sousední matice budou 0. Matice sousednosti výše uvedeného grafu bude -

Vlastnosti matice sousednosti

Některé z vlastností matice sousedství jsou uvedeny takto:

• Matice sousedství je matice, která obsahuje řádky a sloupce používané k reprezentaci jednoduchého označeného grafu s čísly 0 a 1 na pozici (V_já, V_j), podle podmínky, zda dva V_{i ­} a V_jsousedí.
• Pro orientovaný graf, pokud existuje hrana mezi vrcholem i nebo V_ina Vertex j nebo V_j, pak hodnota A[V_i][V_j] = 1, jinak bude hodnota 0.
• U neorientovaného grafu, pokud existuje hrana mezi vrcholem i nebo V_ina Vertex j nebo V_j, pak hodnota A[V_i][V_j] = 1 a A[V_j][V_i] = 1, jinak bude hodnota 0.

Podívejme se na některé otázky matice sousedství. Níže uvedené otázky se týkají vážených neřízených a řízených grafů.

POZNÁMKA: O grafu se říká, že je váženým grafem, pokud je každé hraně přiřazeno kladné číslo, které se nazývá váha hrany.

Otázka 1 - Jaká bude matice sousedství pro níže uvedený neorientovaný vážený graf?

Řešení - V dané otázce není žádná vlastní smyčka, takže je jasné, že diagonální vstupy sousední matice pro výše uvedený graf budou 0. Výše ​​uvedený graf je vážený neorientovaný graf. Váhy na okrajích grafu budou reprezentovány jako vstupy matice sousednosti.

jak aktualizovat v Javě

Matice sousedství výše uvedeného grafu bude -

Otázka 2 - Jaká bude matice sousednosti pro níže orientovaný vážený graf?

Řešení - V dané otázce není žádná vlastní smyčka, takže je jasné, že diagonální vstupy sousední matice pro výše uvedený graf budou 0. Výše ​​uvedený graf je vážený orientovaný graf. Váhy na okrajích grafu budou reprezentovány jako vstupy matice sousednosti.

Matice sousedství výše uvedeného grafu bude -

Doufám, že tento článek je pro vás přínosem, abyste porozuměli matici sousedství. Zde jsme diskutovali o matici sousednosti spolu s jejím vytvořením a vlastnostmi. Diskutovali jsme také o tvorbě matice sousednosti na řízených nebo neorientovaných grafech, ať už jsou vážené nebo ne.