Bogenmatrix

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

De bogenmatrix, verbindingsmatrix is een matrix die hoort bij een gegeven graaf. De bogen in een graaf zijn de zijden, die twee knopen met elkaar verbinden. Een bogenmatrix is een Vierkante matrix met dimensie n×n ,waarbij n het aantal knopen in de graaf is. Het element a_{ij} in de bogenmatrix A is 1 als er een boog bestaat, die van i naar j gaat en 0 als dit niet het geval is. Het is dus een binaire matrix.

Bij een bogenmatrix is de veronderstelling dat er hooguit één pad van een knoop i naar een andere knoop j gaat. Wanneer deze voorwaarde niet geldt, er verschillende zijden tussen twee knopen kunnen zijn, is het een incidentiematrix.

Gelabelde graaf Bogenmatrix
6n-graph2.svg \begin{pmatrix}
1 & 1 & 0 & 0 & 1 & 0\\
1 & 0 & 1 & 0 & 1 & 0\\
0 & 1 & 0 & 1 & 0 & 0\\
0 & 0 & 1 & 0 & 1 & 1\\
1 & 1 & 0 & 1 & 0 & 0\\
0 & 0 & 0 & 1 & 0 & 0\\
\end{pmatrix}

Is de bogenmatrix opgesteld, dan kan deze worden gebruikt om af te lezen hoeveel paden er van een knoop naar een andere zijn. Door de bogenmatrix A tot de macht n te verheffen, kan men in de s-de kolom op de t-de rij aflezen hoeveel paden er zijn van lengte n van knoop s naar knoop t.

Bij een ongerichte graaf is de bogenmatrix symmetrisch. In dat geval zijn de eigenwaarden van de bogenmatrix reëel en zijn de bijbehorende eigenvectoren orthogonaal. De verzamelde eigenwaarden van de matrix heet het spectrum van de graaf. De studie van grafen met hun eigenwaarden en eigenvectoren heet spectrale grafentheorie.