Ebben a cikkben a szomszédsági mátrixot és annak ábrázolását fogjuk tárgyalni.

fatérkép

Szomszédsági mátrix meghatározása

A gráfelméletben a szomszédsági mátrix a véges gráfszerkezet sűrű leírásának módja. Ez a 2D mátrix, amelyet a gráf csomópontjai közötti asszociáció leképezésére használnak.

Ha egy grafikonnak van n csúcsok száma, akkor az adott gráf szomszédsági mátrixa az n x n , és a mátrix minden egyes bejegyzése az egyik csúcstól a másikig terjedő élek számát jelenti.

A szomszédsági mátrixot más néven kapcsolódási mátrix . Néha más néven a Vertex mátrix .

Szomszédsági mátrixábrázolás

Ha egy irányítatlan G gráf n csúcsból áll, akkor a gráf szomszédsági mátrixa n x n mátrix A = [aij] és a következővel definiálható:

a_ij= 1 {ha van út létezik V-ből_énV-nek_j}

a_ij= 0 {egyébként}

Lássunk néhány fontos pontot a szomszédsági mátrix tekintetében.

• Ha van él az V csúcs között_énés V_j, ahol i egy sor, j pedig egy oszlop, akkor az a értéke_ij= 1.
• Ha nincs él az V csúcs között_énés V_j, akkor az a értéke_ij= 0.
• Ha az egyszerű gráfban nincsenek önhurkok, akkor a csúcsmátrix (vagy szomszédsági mátrix) átlójában 0-nak kell lennie.
• A szomszédsági mátrix szimmetrikus egy irányítatlan gráfra. Meghatározza, hogy az i-ben lévő érték^thsor és j^thoszlop egyenlő a j értékével^thi. sor^th
• Ha a szomszédsági mátrixot megszorozzuk önmagával, és ha van nem nulla érték, akkor az i^thsor és j^thoszlop, akkor ott van az útvonal V_énV-nek_j­­2-vel egyenértékű hosszúsággal. A szomszédsági mátrix nullától eltérő értéke azt jelenti, hogy a különböző útvonalak száma jelen van.

Megjegyzés: Egy szomszédsági mátrixban a 0 azt jelenti, hogy nincs kapcsolat két csomópont között, míg az 1 azt jelenti, hogy van kapcsolat két csomópont között.

Hogyan készítsünk szomszédsági mátrixot?

Tegyük fel, hogy van egy grafikon g val vel n csúcsok számát, akkor a csúcsmátrixot (vagy szomszédsági mátrixot) a -

A = a_tizenegya₁₂. . . . . a_1na_huszonegya₂₂. . . . . a_2n. . . . . . . . . a_n1a_n2. . . . . a_nn

Ahol az a_ijegyenlő az i-től j-ig tartó élek számával. Ahogy fentebb említettük, az Adjacency mátrix egy irányítatlan gráf esetén szimmetrikus, így irányítatlan gráf esetén a_ij= a_hé.

Ha a gráfok egyszerűek, és nincs súlyozás az éleken vagy több élen, akkor a szomszédsági mátrix bejegyzései 0 és 1 lesznek. Ha nincs önhurok, akkor a szomszédsági mátrix átlós bejegyzései 0 lesznek.

Most lássuk a szomszédsági mátrixot irányítatlan és irányított gráfokhoz.

Szomszédsági mátrix irányítatlan gráfhoz

Egy irányítatlan gráfban az élek nincsenek a hozzájuk tartozó irányokhoz társítva. Egy irányítatlan gráfban, ha van él az A és B csúcs között, akkor a csúcsok átvihetők A-ból B-be, valamint B-ből A-ba.

hogyan szünteted meg a kijelölést a gimpben

Tekintsük az alábbi irányítatlan gráfot, és próbáljuk meg megszerkeszteni a szomszédsági mátrixát.

A grafikonon láthatjuk, hogy nincs önhurok, így a szomszédos mátrix átlós bejegyzései 0 lesznek. A fenti gráf szomszédsági mátrixa:

Irányított gráf szomszédsági mátrixa

Egy irányított gráfban az élek rendezett párt alkotnak. Az élek egy adott útvonalat jelentenek valamelyik A csúcstól egy másik B csúcsig. Az A csomópontot kezdeti csomópontnak, míg a B csomópontot terminális csomópontnak nevezzük.

Tekintsük az alábbi irányított gráfot, és próbáljuk meg megszerkeszteni a szomszédsági mátrixát.

A fenti grafikonon azt láthatjuk, hogy nincs önhurok, így a szomszédos mátrix átlós bejegyzései 0 lesznek. A fenti gráf szomszédsági mátrixa -

A szomszédsági mátrix tulajdonságai

A szomszédsági mátrix néhány tulajdonsága az alábbiak szerint van felsorolva:

mesterséges intelligencia és intelligens ügynökök

• A szomszédsági mátrix olyan mátrix, amely sorokat és oszlopokat tartalmaz, amelyek egy egyszerű címkézett gráf ábrázolására szolgálnak, ahol a 0 és 1 számok (V)_én, BAN BEN_j), attól függően, hogy a két V_{én ­} és V_jszomszédosak.
• Irányított gráf esetén, ha van él az i vagy a V csúcs között_énj vagy V csúcshoz_j, akkor az A[V_én][BAN BEN_j] = 1, ellenkező esetben az érték 0 lesz.
• Irányítatlan gráf esetén, ha van él az i vagy a V csúcs között_énj vagy V csúcshoz_j, akkor az A[V_én][BAN BEN_j] = 1 és A[V_j][BAN BEN_én] = 1, ellenkező esetben az érték 0 lesz.

Lássuk a szomszédsági mátrix néhány kérdését. Az alábbi kérdések a súlyozott irányítatlan és irányított grafikonokra vonatkoznak.

MEGJEGYZÉS: A gráfot súlyozott gráfnak nevezzük, ha minden élhez pozitív szám van hozzárendelve, amelyet az él súlyának nevezünk.

1. kérdés - Mi lesz az alábbi irányítatlan súlyozott gráf szomszédsági mátrixa?

Megoldás - Az adott kérdésben nincs önhurok, így egyértelmű, hogy a szomszédos mátrix átlós bejegyzései a fenti gráfhoz 0 lesznek. A fenti gráf egy súlyozott irányítatlan gráf. A gráf élein lévő súlyok a szomszédsági mátrix bejegyzéseiként jelennek meg.

A fenti gráf szomszédsági mátrixa a következő lesz:

2. kérdés - Mi lesz a szomszédsági mátrix az alábbi irányított súlyozott gráfhoz?

konvertálás stringből int-be java-ban

Megoldás - Az adott kérdésben nincs önhurok, így egyértelmű, hogy a szomszédos mátrix átlós bejegyzései a fenti gráfhoz 0 lesznek. A fenti gráf egy súlyozott irányított gráf. A gráf élein lévő súlyok a szomszédsági mátrix bejegyzéseiként jelennek meg.

A fenti gráf szomszédsági mátrixa a következő lesz:

Reméljük, hogy ez a cikk hasznos az Ön számára, hogy megértse a szomszédsági mátrixot. Itt tárgyaltuk a szomszédsági mátrixot, annak létrehozásával és tulajdonságaival együtt. Megbeszéltük továbbá a szomszédsági mátrix képzését irányított vagy irányítatlan gráfokon, függetlenül attól, hogy súlyozottak-e vagy sem.