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 och bågmängd E definieras som n × n-matrisen med element givna av:

Med andra ord är matriselementet i kolonn i och rad j ett om det finns en båge mellan noderna och 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 och går åt båda håll.

Exempel[redigera | redigera wikitext]

Graf Grannmatris
6n-graf.svg

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 i matrisen antalet vägar av längd k mellan noderna och . För ses detta genom att betrakta matrismultiplikationen komponentvis:

om och endast om det finns en väg mellan och och en väg mellan och , 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 och nod om och endast om elementet i matrisen

ä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 och med grannmatriser och är isomorfa om och endast om det finns en permutationsmatris P sådan att , 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]