Grannmatris

Från Wikipedia
Hoppa till: navigering, sök

En grannmatris är inom matematik, specifikt grafteori, en matris som beskriver en graf genom att ange vilka noder som har bågar mellan sig. En annan sorts matriser som beskriver grafer är anslutningsmatriser.

Grannmatrisen A till en (enkel) graf G med nodmängd V = \{v_1, v_2, ..., v_n\} och bågmängd E definieras som n × n-matrisen med element a_{ij} givna av:

a_{ij} = 
\begin{cases} 
1 & \mathrm{om} ~~ \{v_i, v_j\} \in E \\
0 & \mathrm{annars}
\end{cases}

Med andra ord är matriselementet i kolonn i och rad j ett om det finns en båge mellan noderna v_i och v_j och noll annars.

För en multigraf är elementen i grannmatrisen antalet bågar mellan två noder. I grannmatriser för enkla grafer är diagonalen alltid noll, något som inte gäller för multigrafers grannmatriser.

För en viktad graf sätts matriselementet aij vanligtvis till vikten på bågen mellan noderna i och j, om en sådan båge finns. Om det inte finns en båge sätts matriselementet till 0.

I programmeringssammanhang sätts ofta oanslutna noders gemensamma matriselement till oändligheten. När anslutningsmatriser implementeras som datastrukturer används ett stort tal istället för oändligheten. Utseendet av grannmatrisen beror på hur noderna är numrerade, om man byter numrering permuteras raderna. I en oriktad graf är grannmatrisen alltid symmetrisk, eftersom en båge mellan v_i och v_j går åt båda håll.

Exempel[redigera | redigera wikitext]

Graf Grannmatris
6n-graf.svg \begin{pmatrix}
0 & 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{pmatrix}

Grannmatrisen till en komplett graf har ettor överallt utom i diagonalen.

Egenskaper[redigera | redigera wikitext]

Grannmatrisen till en oriktad enkel graf är symmetrisk och har därmed endast reella egenvärden och en bas av ortonormerade egenvektorer (enligt spektralsatsen). Egenvärdena till grannmatrisen kallas grafens spektrum. Man kan genom att beräkna potenser av en grannmatris få viktig information om grafen; om G är en oriktad enkel graf med grannmatris A så är värdet på elementet b_{ij} i matrisen B = A^k antalet vägar av längd k mellan noderna v_i och v_j. För k=2 ses detta genom att betrakta matrismultiplikationen komponentvis:

b_{ij} = \sum_{k=1}^n a_{ik}a_{kj}

a_{ik}a_{kj}=1 om och endast om det finns en väg mellan v_i och v_k och en väg mellan v_k och v_j, som då har längd 2. Genom induktion får man resultatet för godtyckliga k. En följd av detta är att det finns en väg mellan nod v_i och nod v_j om och endast om elementet c_{ij} i matrisen

C = \sum_{k=1}^{n-1} A^k

är nollskilt. Som en följd ser man att grafen är sammanhängande om och endast om C endast har nollskilda element.

Två riktade eller oriktade grafer G_1 och G_2 med grannmatriser A_1 och A_2 är isomorfa om och endast om det finns en permutationsmatris P sådan att PA_1P^{-1}=A_2, specifikt är grannmatriserna similära, så de delar exempelvis egenvärden, determinant och matrisspår, så dessa är invarianta under grafisomorfier.

Referenser[redigera | redigera wikitext]