Szomszédsági mátrix

A szomszédsági mátrix az egyik módja annak, hogy egy gráfot mátrixként ábrázoljunk.

Definíció

A véges számú (1-től számozott ) csúcsú gráf szomszédsági mátrixa egy méretű négyzetes egész mátrix , amelyben az elem értéke megegyezik a gráf th csúcsától a th csúcsig tartó élek számával . $G$ $n$ $n$ ${\mathbf A}$ $n\szer n$ $a_{i,j}$ $én$ $j$

Néha, különösen irányítatlan gráf esetén, egy hurok (egy él a -edik csúcstól önmagába) két élnek számít, vagyis az átlós elem értéke ebben az esetben megegyezik a körülötte lévő hurkok számának kétszeresével. a -edik csúcs. $én$ ${\displaystyle a_{i,i))$ $én$

Egy egyszerű gráf szomszédsági mátrixa (amely nem tartalmaz hurkokat vagy több élt) egy bináris mátrix , és nullákat tartalmaz a főátlón .

Kétrészes gráf szomszédsági mátrixa

Egy kétrészes gráf szomszédsági mátrixa , amelynek részei is rendelkeznek csúcsokkal , a következő formában írhatók fel ${\mathbf A}$ $r$ $s$

\mathbf {A} ={\begin{pmatrix}\mathbf {0} _{r,r}&\mathbf {B} \\\mathbf {B} ^{T}&\mathbf {0} _ {s,s}\end{pmatrix}},

ahol egy mátrix, és és nulla mátrix . Ebben az esetben a kisebb mátrix egyedileg reprezentálja a gráfot, és a mátrix többi része eldobható. néha bisz-szomszédsági mátrixnak is nevezik. $\mathbf {B}$ $r\times$ ${\displaystyle \mathbf {0} _{r,r))$ $\mathbf {0} _{s,s}$ $r\times r$ $s\time s$ $\mathbf {B}$ ${\mathbf A}$ $\mathbf {B}$

Formálisan legyen egy kétrészes gráf részekkel és . A bikonjugált mátrix egy 0-1 mátrix , amelyben akkor és csak akkor, ha . $G=(U,V,E)$ $U=\{u_{1},\dots ,u_{r}\}$ $V=\{v_{1},\dots ,v_{s}\}$ $r\times$ $\mathbf {B}$ $b_{i,j}=1$ $(u_{i},v_{j})\in E$

Ha egy bipartit multigráf vagy egy súlyozott gráf, akkor az elemek a csúcsok közötti élek száma vagy az élek súlya lesz . $G$ ${\displaystyle b_{i,j))$ $(u_{i},v_{j})$

Példák

Az alábbiakban egy példát mutatunk be egy irányítatlan gráfra és a hozzá tartozó szomszédsági mátrixra . Ez a gráf tartalmaz egy hurkot az 1. csúcs körül, és a konkrét alkalmazásoktól függően egy elemet egyenlőnek tekinthetünk eggyel (lásd alább), vagy kettőt. ${\mathbf A}$ $a_{1,1}$

Grafikon	Szomszédsági mátrix
	${\displaystyle {\begin{pmatrix}1&1&0&0&1&0\\1&0&1&0&1&0\\0&1&0&1&0&0\\0&0&1&0&1&1\\1&1&0&1&0&0\\0&0&0&1&0&0\end){pmátrix)$

$a_{i,j}$ a csúcsokat és a csúcsokat összekötő élek száma , és bizonyos alkalmazásokban minden hurkot (néhánynál élt ) kétszer számolnak. $v_{i}$ $v_{j}$ $\{v_{i},v_{i}\}$ $én$

Egy éleket nem tartalmazó üres gráf szomszédsági mátrixa minden nullából áll.

Tulajdonságok

Egy irányítatlan gráf szomszédsági mátrixa szimmetrikus , ami azt jelenti, hogy valódi sajátértékekkel és sajátvektorok ortogonális bázisával rendelkezik. Sajátértékeinek halmazát a gráf spektrumának nevezik, és a spektrális gráfelmélet fő vizsgálati tárgya .

Két gráf szomszédsági mátrixokkal és akkor és csak akkor izomorf , ha létezik olyan permutációs mátrix , $G_{1}$ $G_{2}$ $\mathbf {A} _{1}$ ${\displaystyle \mathbf {A} _{2))$ $\mathbf {P}$

{\displaystyle \mathbf {P} \mathbf {A} _{1}\mathbf {P} ^{-1}=\mathbf {A} _{2))

Ebből következik, hogy a és mátrixok hasonlóak , ezért azonos sajátérték-, determináns- és karakterisztikus polinomhalmazaik vannak. Ennek fordítottja azonban nem mindig igaz - két hasonló szomszédsági mátrixú grafikon nem izomorf (ez akkor történik, ha a mátrix nem permutálható, például a mátrixok és hasonlóak, de a megfelelő gráfok nem izomorfok). $\mathbf {A} _{1}$ ${\displaystyle \mathbf {A} _{2))$ $\mathbf {P}$ ${\begin{pmatrix}0&1\\0&0\end{pmatrix}}$ ${\begin{pmatrix}0&2\\0&0\end{pmatrix}}$

Mátrix erők

Ha a gráf szomszédsági mátrixa , akkor a mátrixnak a következő tulajdonsága van: a -edik sorban, -edik oszlopban lévő elem egyenlő a -edik csúcstól a -edikig tartó utak számával , amely pontosan élekből áll. ${\mathbf A}$ $G$ $\mathbf {A} ^{m}$ $én$ $j$ $én$ $j$ $m$

Adatstruktúra

A szomszédsági mátrix és a szomszédsági listák a fő adatszerkezetek , amelyeket a számítógépes programokban a gráfok ábrázolására használnak.

A szomszédsági mátrix használata csak nagy számú élű, nem ritka gráfok esetén célszerű, mivel minden elemhez egy bit adatot kell tárolni. Ha a gráf ritka, akkor a memória nagy része a nullák tárolására vész el, de nem ritka gráfok esetén a szomszédsági mátrix meglehetősen kompaktan ábrázolja a gráfot a memóriában, körülbelül egy kis memória felhasználásával, ami lehet sorrend nagyságrenddel jobb, mint a szomszédsági listák. $n^{2}$

A súlyozott gráfokkal működő algoritmusokban (például a Floyd-Warshall algoritmusban ) a szomszédsági mátrix elemei az él meglétét vagy hiányát jelző 0 és 1 számok helyett gyakran az élek súlyát is tartalmazzák. maguk. Ugyanakkor a hiányzó élek helyére valamilyen speciális határérték ( angol sentinel ) kerül , a megoldandó feladattól függően, általában 0 vagy . $\infty$

Lásd még

Irodalom

Kormen, T. , Leizerson, C. , Rivest, R. , Stein, K. Algorithms: construction and analysis = Introduction to Algorithms / Szerk. I. V. Krasikova. - 2. kiadás - M. : Williams, 2005. - 1296 p. — ISBN 5-8459-0857-4 .

Linkek

Grafikon szomszédsági mátrixa. Programkód Pascal és C++ nyelven