Grannmatris
From Wikipedia, the free encyclopedia
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 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.