Anslutningsmatris

Från Wikipedia
Hoppa till: navigering, sök

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.

Definition[redigera | redigera wikitext]

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[redigera | redigera wikitext]

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[redigera | redigera wikitext]

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[redigera | redigera wikitext]

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[redigera | redigera wikitext]

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
Labeled undirected graph.svg \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}
Directed graph with labeled edges 5n 7e.png 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}
Hypergraph.gif \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[redigera | redigera wikitext]

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[redigera | redigera wikitext]

  • 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