Anslutningsmatris

En anslutningsmatris är inom matematik, specifikt grafteori, en matris som beskriver vilka noder i en graf bågarna är kopplade till.

Även grannmatriser är matriser som beskriver grafer.

Definition

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.

Oriktad anslutningsmaris

För en oriktad graf G med nodmängd $N = \{v_1, v_2, ..., v_n\}$ och bågmängd $B = \{e_1, e_2, ..., e_b\}$ så är den oriktade anslutningsmatrisen A en matris av storlek n × b där elementet $a_{ij} = 1$ om noden $v_i$ är kopplad till bågen $e_j$ och noll annars.

Riktad anslutningsmatris

Den riktade anslutningsmatrisen A för en riktad graf G med noder och riktade bågar som ovan, är n × b-matrisen med elementen $a_{ij}$ som är 1 om bågen $e_j$ går till noden $v_i$, -1 om bågen går från $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.

Hypergrafer

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 flertalet noder, så att en kolonn kan ha flertalet nollskilda element i sin oriktade anslutningsmatris.

Exempel

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
	$\begin{pmatrix} 1 & 1 & 1 & 0 \\ 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 1 \end{pmatrix}$	$\begin{pmatrix} 1 & 1 & -1 & 0 \\ -1 & 0 & 0 & 0 \\ 0 & -1 & 0 & 1 \\ 0 & 0 & 1 & -1 \end{pmatrix}$
	Ej tillämpbart.	$\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}$
	$\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.

Egenskaper

Om G är en oriktad graf med oriktad anslutningsmatris A och linjegraf L så är $A^TA = 2I + G_L$, där $G_L$ är grannmatrisen till L.

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

Referenser

• 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