Bogenmatrix

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 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
	$\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.

• Voor een complete graaf bestaat de bogenmatrix uit alleen maar 1-en, behalve op de hoofddiagonaal.
• Bij een ongerichte graaf is de bogenmatrix symmetrisch.