Bogenmatrix
Uit Wikipedia, de vrije encyclopedie
De bogenmatrix of een verbindingsmatrix van 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 aij 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.
| Gelabelde graaf | Bogenmatrix |
|---|---|
 |
 |
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.
- Voor een complete graaf bestaat de bogenmatrix uit alleen maar 1-en, behalve op de hoofddiagonaal.
- Bij een ongerichte graaf is de bogenmatrix symmetrisch.
