Incidentiematrix

De incidentiematrix is een matrix, die in onder andere de projectieve meetkunde kan worden gebruikt om een projectief vlak mee te beschrijven.

Een incidentiematrix kan in de informatica een compacte voorstelling van een graaf vormen. De incidentiematrix van een graaf met n knopen en p kanten heeft ${\displaystyle {\mathcal {O}}(n\cdot p)}$ geheugenplaatsen nodig. Voor 'ijle' grafen, grafen met veel knopen maar relatief weinig kanten, dus p veel kleiner dan n, kan dit een voordeel zijn boven een voorstelling als bogenmatrix, die ${\displaystyle {\mathcal {O}}(n^{2})}$ geheugen inneemt.

Projectieve meetkunde[bewerken | brontekst bewerken]

Er kan voor een projectief vlak, bijvoorbeeld voor het Fano-vlak, met een incidentiematrix worden aangegeven welke punten op welke lijnen liggen. Punten en lijnen moeten daartoe worden genummerd, een één op plaats ( i , j ) betekent dat het punt met rijnummer i op de lijn met kolomnummer j ligt, een nul dat dat niet het geval is. De incidentiematrix is voor het Fano-vlak symmetrisch, punten en lijnen kunnen worden verwisseld.

Ongerichte graaf[bewerken | brontekst bewerken]

Incidentiematrices kunnen in de grafentheorie worden gebruikt om een graaf te beschrijven. Voor een ongerichte, niet-gewogen graaf met n knopen en p bogen, is de incidentiematrix een n bij p matrix waarin het element op de i-de rij en j-de kolom gelijk is aan:

• 1 wanneer knoop ${\displaystyle v_{i}}$ een uiteinde is van de boog ${\displaystyle x_{j}}$;
• 2 wanneer de boog ${\displaystyle x_{j}}$ een lus is van knoop ${\displaystyle v_{i}}$ naar ${\displaystyle v_{i}}$;
• 0 in het andere geval.

Voorbeeld: stel dat de bogen in onderstaande graaf als volgt zijn genummerd:

1. tussen 1 en 1
2. tussen 1 en 2
3. tussen 1 en 5
4. tussen 2 en 5
5. tussen 2 en 3
6. tussen 5 en 4
7. tussen 3 en 4
8. tussen 4 en 6

dan ziet de incidentiematrix eruit als volgt:

Gelabelde graaf	Incidentiematrix
	${\displaystyle {\begin{pmatrix}2&1&1&0&0&0&0&0\\0&1&0&1&1&0&0&0\\0&0&0&0&1&0&1&0\\0&0&0&0&0&1&1&1\\0&0&1&1&0&1&0&0\\0&0&0&0&0&0&0&1\\\end{pmatrix}}}$

De som van elke kolom is gelijk aan 2, omdat elke boog twee knopen verbindt.

De som van de i-de rij in de incidentiematrix is de graad van de knoop i, dit is het aantal bogen dat in die knoop samenkomt. Een lus wordt twee keer geteld. De graadmatrix van de graaf is de n bij n-diagonaalmatrix met op de diagonaal de graad van elke knoop, dit is hier de matrix:

${\displaystyle D={\begin{pmatrix}4&0&0&0&0&0\\0&3&0&0&0&0\\0&0&2&0&0&0\\0&0&0&3&0&0\\0&0&0&0&3&0\\0&0&0&0&0&1\\\end{pmatrix}}}$

Gerichte graaf[bewerken | brontekst bewerken]

Voor een gerichte graaf, waarin elke boog een begin- en een eindknoop heeft, is het element op de i-de rij en j-de kolom in de incidentiematrix gelijk aan:

• 1 wanneer knoop ${\displaystyle v_{i}}$ de beginknoop is van de boog ${\displaystyle x_{j}}$;
• -1 wanneer knoop ${\displaystyle v_{i}}$ de eindknoop is van de boog ${\displaystyle x_{j}}$;
• 0 in het andere geval.

Soms wordt het omgekeerd gezegd, -1 als de boog de knoop verlaat en +1 als de boog in de knoop aankomt.

De som van een kolom in de incidentiematrix is nu steeds gelijk aan nul. Als er in een gerichte graaf een lus voorkomt bestaat de corresponderende kolom geheel uit nullen.