Grannmatris

En grannmatris eller närhetsmatris ä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 ${\displaystyle V=\{v_{1},v_{2},...,v_{n}\}}$ och bågmängd E definieras som n × n-matrisen med element ${\displaystyle a_{ij}}$ givna av:

${\displaystyle 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 ${\displaystyle v_{i}}$ och ${\displaystyle 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 ${\displaystyle v_{i}}$ och ${\displaystyle v_{j}}$ går åt båda håll.

Exempel

Graf	Grannmatris
	${\displaystyle {\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 ${\displaystyle b_{ij}}$ i matrisen ${\displaystyle B=A^{k}}$ antalet vägar av längd k mellan noderna ${\displaystyle v_{i}}$ och ${\displaystyle v_{j}}$. För ${\displaystyle k=2}$ ses detta genom att betrakta matrismultiplikationen komponentvis:

${\displaystyle b_{ij}=\sum _{k=1}^{n}a_{ik}a_{kj}}$

då ${\displaystyle a_{ik}a_{kj}=1}$ om och endast om det finns en väg mellan ${\displaystyle v_{i}}$ och ${\displaystyle v_{k}}$ och en väg mellan ${\displaystyle v_{k}}$ och ${\displaystyle 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 ${\displaystyle v_{i}}$ och nod ${\displaystyle v_{j}}$ om och endast om elementet ${\displaystyle c_{ij}}$ i matrisen

${\displaystyle 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 ${\displaystyle G_{1}}$ och ${\displaystyle G_{2}}$ med grannmatriser ${\displaystyle A_{1}}$ och ${\displaystyle A_{2}}$ är isomorfa om och endast om det finns en permutationsmatris P sådan att ${\displaystyle PA_{1}P^{-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