Grannmatris

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 a_ij 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

Graf	Grannmatris
	$\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

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}$

då $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

• Godsil, Chris; Gordon Royle (2001). Algebraic Graph Theory. Springer Verlag. ISBN 0-387-95241-1 
• Bollobás, Béla (2002). Modern Graph Theory. Springer Verlag. ISBN 978-0387984889