Anslutningsmatris

En anslutningsmatris (eller incidensmatris) är inom matematik, specifikt grafteori, en matris som beskriver vilka noder i en graf bågarna är kopplade till. Inom projektiv geometri beskriver den vilka punkter som är incidenta med vilka linjer.

Även grannmatriser är matriser som beskriver grafer.

Inom grafteori finns flera olika anslutningsmatriser, en typ som bara kan användas på oriktade grafer och en som används för riktade grafer och kan anpassas till oriktade grafer.

För en oriktad graf G med nodmängd ${\displaystyle N=\{v_{1},v_{2},...,v_{n}\}}$ och bågmängd ${\displaystyle B=\{e_{1},e_{2},...,e_{b}\}}$ så är den oriktade anslutningsmatrisen A en matris av storlek n × b där elementet ${\displaystyle a_{ij}=1}$ om noden ${\displaystyle v_{i}}$ är kopplad till bågen ${\displaystyle e_{j}}$ och noll annars.

Den riktade anslutningsmatrisen A för en riktad graf G med noder och riktade bågar som ovan, är n × b-matrisen med elementen ${\displaystyle a_{ij}}$ som är 1 om bågen ${\displaystyle e_{j}}$ går till noden ${\displaystyle v_{i}}$, -1 om bågen går från ${\displaystyle v_{i}}$ och 0 annars.

För riktade grafer kan man definiera en riktad anslutningsmatris helt enkelt genom att välja en riktning för alla bågar i grafen. En oriktad graf har alltså flera riktade anslutningsmatriser.

I en vanlig graf kan en båge endast vara ansluten till två noder, så i varje kolonn i en anslutningsmatris kan det bara finnas två nollskilda element. I en hypergraf kan en båge vara ansluten till flera noder, så att en kolonn kan ha flera nollskilda element i sin oriktade anslutningsmatris.

Anslutningsmatriser kan läsas kolonnvis då man läser vilka noder som är direkt anslutna med en båge, eller radvis, då man läser vilka bågar som är ansluten till en specifik nod.

Graf/hypergraf	Oriktad anslutningsmatris	Riktad anslutningsmatris
	${\displaystyle {\begin{pmatrix}1&1&1&0\\1&0&0&0\\0&1&0&1\\0&0&1&1\end{pmatrix}}}$	${\displaystyle {\begin{pmatrix}1&1&-1&0\\-1&0&0&0\\0&-1&0&1\\0&0&1&-1\end{pmatrix}}}$
	Ej tillämpbart.	${\displaystyle {\begin{pmatrix}-1&-1&0&0&0&0&0\\1&0&-1&0&0&0&0\\0&1&0&-1&1&0&1\\0&0&1&1&-1&-1&0\\0&0&0&0&0&1&-1\end{pmatrix}}}$
	${\displaystyle {\begin{pmatrix}1&0&0&0\\1&1&0&0\\1&1&1&0\\0&0&0&1\\0&0&1&0\\0&0&1&0\\0&0&0&0\end{pmatrix}}}$	Ej tillämpbart.

Om G är en oriktad graf med oriktad anslutningsmatris A och linjegraf L så är ${\displaystyle A^{T}A=2I+G_{L}}$, där ${\displaystyle G_{L}}$ är grannmatrisen till L.

Den riktade anslutningsmatrisen till en riktad graf är fullständigt unimodulär.

• Godsil, Chris; Gordon Royle (2001). Algebraic Graph Theory. Springer Verlag. ISBN 0-387-95241-1 
• Lundgren, Jan; Peter Värbrand, Mikael Rönnqvist (2008). Optimeringslära. Studentlitteratur. ISBN 9789144053141