Bogenmatrix

De bogenmatrix of verbindingsmatrix is een matrix die hoort bij een enkelvoudige, eindige graaf, en die aangeeft of een knoop in de graaf verbonden 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 ${\displaystyle n\times n}$, waarin ${\displaystyle n}$ het aantal knopen in de graaf is. Het element ${\displaystyle a_{ij}}$ in de bogenmatrix ${\displaystyle A}$ is 1 als er een boog bestaat die van ${\displaystyle i}$ naar ${\displaystyle j}$ 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
	${\displaystyle {\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 ${\displaystyle A}$ tot de macht ${\displaystyle n}$ te verheffen, kan men in de ${\displaystyle k}$-de kolom op de ${\displaystyle r}$-de rij aflezen hoeveel paden er zijn van lengte ${\displaystyle n}$ van knoop ${\displaystyle k}$ naar knoop ${\displaystyle r}$.

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.