Bogenmatrix

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

De bogenmatrix, verbindingsmatrix of aangrenzendheidsmatrix is een matrix die hoort bij een gegeven graaf.

Het 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 zijde (boog) bestaat die van i naar j gaat en '0' als dit niet het geval is. Het is dus een binaire matrix.

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 gebruikt worden om af te lezen hoeveel paden er zijn van een knoop naar een andere. 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.

Zie ook[bewerken]