Bogenmatrix

Uit Wikipedia, de vrije encyclopedie
Naar navigatie springen Naar zoeken springen

De bogenmatrix of verbindingsmatrix is een matrix die hoort bij een enkelvoudige, eindige graaf, en die aangeeft of een knoop in de graaf vebonden is met een andere knoop. De bogen in een graaf zijn de zijden die twee knopen met elkaar verbinden. Een bogenmatrix is een binaire, vierkante matrix met dimensie , waarin het aantal knopen in de graaf is. Het element in de bogenmatrix is 1 als er een boog bestaat die van naar gaat en 0 als dit niet het geval is. De bogenmatrix is een manier om een enkelvoudige, eindige graaf weer te geven.

Gelabelde graaf Bogenmatrix
6n-graph2.svg

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 tot de macht te verheffen, kan men in de -de kolom op de -de rij aflezen hoeveel paden er zijn van lengte van knoop naar knoop .

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.