Incidensmatrix

Incidensmatricen er en af grafrepræsentationsformerne , hvor forbindelserne mellem grafens indfaldende elementer (kant (bue) og toppunkt) er angivet . Matrixkolonner svarer til kanter, rækker svarer til toppunkter. En ikke-nul værdi i en matrixcelle angiver forholdet mellem et toppunkt og en kant (deres forekomst ).

I tilfælde af en rettet graf placeres hver bue <x,y> i den tilsvarende kolonne: "1" i rækken af x-toppunktet og "-1" i rækken af toppunktet y; hvis der ikke er nogen forbindelse mellem toppunktet og kanten, sættes "0" i den tilsvarende celle.

Eksempel

Kurve	Incidensmatrix
	${\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){1&pmatrix$

Rækker svarer til hjørner fra 1 til 6, og søjler svarer til kanter e1–e7. For eksempel betyder dem i anden kolonne i 2. og 3. række, at kanten e2 forbinder hjørne 2 og 3.

Funktioner af denne repræsentation

Bruges til alle grafer, også selvom der er en løkke.
Hver søjle må højst indeholde to 1'ere (hvis denne kant er en løkke, placeres 1'eren modsat det toppunkt, som løkken falder ind i). I tilfælde af en rettet graf skal kolonnen indeholde 1 og -1.
Kan bruges til at repræsentere hypergrafer (i hvilket tilfælde kolonnen kan indeholde mere end to 1'ere)

Incidensmatrix

Eksempel

Funktioner af denne repræsentation

Se også

Noter

Litteratur