ČO JE MATICA SUSEDNOSTI

V tomto článku budeme diskutovať o matici susednosti spolu s jej reprezentáciou.

np.linspace

Definícia matice susednosti

V teórii grafov je matica susednosti hustým spôsobom popisu konečnej štruktúry grafu. Je to 2D matica, ktorá sa používa na mapovanie asociácie medzi uzlami grafu.

Ak má graf n počet vrcholov, potom je matica susednosti tohto grafu n x n a každý záznam matice predstavuje počet hrán z jedného vrcholu do druhého.

Matica susedstva sa tiež nazýva ako spojovacia matica . Niekedy sa nazýva aj a Vertexová matica .

Znázornenie matice susedstva

Ak sa neorientovaný graf G skladá z n vrcholov, potom matica susednosti grafu je n x n matica A = [aij] a definovaná ako -

a_ij= 1 {ak existuje cesta z V_ido V_j}

a_ij= 0 {Inak}

Pozrime sa na niektoré dôležité body s ohľadom na maticu susednosti.

Ak medzi vrcholom V existuje hrana_ia V_j, kde i je riadok a j je stĺpec, potom hodnota a_ij= 1.
Ak medzi vrcholom V nie je žiadna hrana_ia V_j, potom hodnota a_ij= 0.
Ak v jednoduchom grafe nie sú žiadne vlastné slučky, potom matica vrcholov (alebo matica susednosti) by mala mať na diagonále 0.
Matica susednosti je pre neorientovaný graf symetrická. Špecifikuje, že hodnota v i^thriadok a j^thstĺpec sa rovná hodnote v j^thriadok i^th
Ak je matica susednosti vynásobená sama osebe a ak existuje nenulová hodnota, na i^thriadok a j^thstĺpec, potom je trasa z V_ido V_js dĺžkou ekvivalentnou 2. Nenulová hodnota v matici susednosti predstavuje, že je prítomný počet odlišných dráh.

Poznámka: V matici susednosti 0 znamená, že medzi dvoma uzlami neexistuje žiadne spojenie, zatiaľ čo 1 znamená, že medzi dvoma uzlami existuje spojenie.

Ako vytvoriť maticu susednosti?

Predpokladajme, že existuje graf g s n počet vrcholov, potom je matica vrcholov (alebo matica susednosti) daná -

A = a_jedenásťa₁₂. . . . . a_1na_{dvadsaťjeden}a₂₂. . . . . a_2n. . . . . . . . . a_n1a_n2. . . . . a_nn

Kde a_ijsa rovná počtu hrán od vrcholu i po j. Ako bolo uvedené vyššie, matica susednosti je symetrická pre neorientovaný graf, takže pre neorientovaný graf je_ij= a_hee.

Keď sú grafy jednoduché a na hranách alebo viacerých hranách nie sú žiadne váhy, potom položky matice susednosti budú 0 a 1. Ak neexistujú žiadne vlastné slučky, potom položky diagonálnej matice susednosti budú 0.

aké sú rozmery obrazovky môjho počítača

Teraz sa pozrime na maticu susednosti pre neorientovaný graf a pre orientované grafy.

Matica susedstva pre neorientovaný graf

V neorientovanom grafe nie sú hrany spojené so smermi s nimi. Ak v neorientovanom grafe existuje hrana medzi Vertexom A a Vertexom B, potom sa vrcholy môžu preniesť z A do B, ako aj z B do A.

Uvažujme nižšie neorientovaný graf a pokúsme sa skonštruovať jeho maticu susednosti.

V grafe vidíme, že neexistuje žiadna vlastná slučka, takže diagonálne vstupy susednej matice budú 0. Matica susednosti vyššie uvedeného grafu bude -

Matica susednosti pre orientovaný graf

V orientovanom grafe tvoria hrany usporiadaný pár. Hrany predstavujú špecifickú cestu z niektorého vrcholu A do iného vrcholu B. Uzol A sa nazýva počiatočný uzol, zatiaľ čo uzol B sa nazýva koncový uzol.

Uvažujme nižšie nasmerovaný graf a skúsme z neho zostaviť maticu susednosti.

stiahnite si prehrávač médií youtube vlc

Vo vyššie uvedenom grafe vidíme, že neexistuje žiadna vlastná slučka, takže diagonálne vstupy susednej matice budú 0. Matica susednosti vyššie uvedeného grafu bude -

Vlastnosti matice susednosti

Niektoré z vlastností matice susednosti sú uvedené takto:

Matica susedstva je matica, ktorá obsahuje riadky a stĺpce používané na znázornenie jednoduchého označeného grafu s číslami 0 a 1 na pozícii (V_ja, V_j), podľa podmienky, či dvaja V_ia V_jsusedia.
V prípade orientovaného grafu, ak medzi vrcholom i alebo V existuje hrana_ido Vertexu j alebo V_j, potom hodnota A[V_i][V_j] = 1, inak bude hodnota 0.
V prípade neorientovaného grafu, ak medzi vrcholom i alebo V existuje hrana_ido Vertexu j alebo V_j, potom hodnota A[V_i][V_j] = 1 a A[V_j][V_i] = 1, inak bude hodnota 0.

Pozrime sa na niektoré otázky matice susednosti. Nižšie uvedené otázky sa týkajú vážených neorientovaných a orientovaných grafov.

POZNÁMKA: Graf sa považuje za vážený graf, ak je každej hrane priradené kladné číslo, ktoré sa nazýva váha hrany.

Otázka 1 - Aká bude matica susednosti pre nižšie uvedený neorientovaný vážený graf?

Riešenie - V danej otázke nie je žiadna vlastná slučka, takže je jasné, že diagonálne vstupy susednej matice pre vyššie uvedený graf budú 0. Vyššie uvedený graf je vážený neorientovaný graf. Váhy na okrajoch grafu budú reprezentované ako vstupy matice susednosti.

abstraktné metódy

Matica susedstva vyššie uvedeného grafu bude -

Otázka 2 - Aká bude matica susednosti pre nižšie orientovaný vážený graf?

Riešenie - V danej otázke neexistuje žiadna samoslučka, takže je jasné, že diagonálne vstupy susednej matice pre vyššie uvedený graf budú 0. Uvedený graf je vážený orientovaný graf. Váhy na okrajoch grafu budú reprezentované ako vstupy matice susednosti.