Incidensmatris

Incidensmatrisen är en av grafrepresentationsformerna , där länkarna mellan de infallande elementen i grafen (kant (båge) och vertex) indikeras . Matriskolumner motsvarar kanter, rader motsvarar hörn. Ett värde som inte är noll i en matriscell indikerar förhållandet mellan en vertex och en kant (deras förekomst ).

I fallet med en riktad graf placeras varje båge <x,y> i motsvarande kolumn: "1" i raden av x-vertexen och "-1" i raden av vertexen y; om det inte finns någon koppling mellan spetsen och kanten, sätts "0" i motsvarande cell.

Exempel

Graf	Incidensmatris
	${\begin{pmatrix}1&0&0&0&1&0&0\\\1&1&0&0&0&1&0\\0&1&1&0&0&0&0\\0&0&1&1&1&0&0&1\\0&0&0&1&1&1&0\\\\\\\\0&0&0&0&0&0)\end{1&pmatrix$

Rader motsvarar hörn från 1 till 6, och kolumner motsvarar kanterna e1–e7. Till exempel betyder de i den andra kolumnen i 2:a och 3:e raden att kanten e2 förbinder hörn 2 och 3.

Funktioner i denna representation

Används för alla grafer, även om det finns en loop.
Varje kolumn måste innehålla högst två 1:or (om denna kant är en slinga, placeras 1:an mittemot den spets som slingan faller mot). I fallet med en riktad graf bör kolumnen innehålla 1 och -1.
Kan användas för att representera hypergrafer (i vilket fall kolumnen kan innehålla fler än två 1:or)

Incidensmatris

Exempel

Funktioner i denna representation

Se även

Anteckningar

Litteratur