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 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 geheugen inneemt.

Projectieve meetkundeBewerken

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 graafBewerken

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   een uiteinde is van de boog  ;
  • 2 wanneer de boog   een lus is van knoop   naar  ;
  • 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
   

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:

 

Gerichte graafBewerken

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   de beginknoop is van de boog  ;
  • -1 wanneer knoop   de eindknoop is van de boog  ;
  • 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.