Incidentiematrix

Uit Wikipedia, de vrije encyclopedie
Ga naar: navigatie, zoeken

De incidentiematrix is een matrix die in de grafentheorie gebruikt wordt om een graaf te beschrijven.

Incidentiematrix van een ongerichte graaf[bewerken]

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 v_i een uiteinde is van de boog x_j;
  • 2 wanneer de boog x_j een lus is van knoop v_i naar 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
6n-graph2.svg \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 tweemaal 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:

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}

Incidentiematrix van een gerichte graaf[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 v_i de beginknoop is van de boog x_j;
  • -1 wanneer knoop v_i de eindknoop is van de boog x_j;
  • 0 in het andere geval.

Soms wordt de omgekeerde conventie gebruikt (-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.

Gebruik[bewerken]

De incidentiematrix wordt in de spectrale grafentheorie gebruikt om eigenschappen van de grafen af te leiden uit de matrices die ermee verwant zijn.

In de informatica kan de incidentiematrix een compacte voorstelling van een graaf vormen. De incidentiematrix van een graaf met n knopen en p kanten benodigt \mathcal{O}(n\cdot p) geheugenplaatsen. Voor "ijle" grafen met veel knopen maar relatief weinig kanten (dus p veel kleiner dan n) kan dit een voordeel zijn t.o.v. een voorstelling als bogenmatrix, die \mathcal{O}(n^2) geheugen inneemt.