Voorbeeld

Stel de bij deze graaf passende verbindingsmatrix C op en laat door berekening zien dat in C² nog wel nullen voorkomen, maar in C + C² niet meer. Beredeneer ook waarom dit zo is. Hoeveel bedraagt de graad van verbinding en wat betekent dit getal?

Antwoord

Met de knooppunten van links naar rechts en van boven naar beneden in alfabetische volgorde geldt:
C = $\left(\begin{array}{ccccc}0& 0& 0& 0& 1\\ 0& 0& 1& 1& 1\\ 0& 1& 0& 0& 1\\ 0& 1& 0& 0& 1\\ 1& 1& 1& 1& 0\end{array}\right)$, C² = $\left(\begin{array}{ccccc}1& 1& 1& 1& 0\\ 1& 3& 1& 1& 2\\ 1& 1& 2& 2& 1\\ 1& 1& 2& 2& 1\\ 0& 2& 1& 1& 4\end{array}\right)$  en C + C² = $\left(\begin{array}{ccccc}1& 1& 1& 1& 1\\ 1& 3& 2& 2& 3\\ 1& 2& 2& 2& 2\\ 1& 2& 2& 2& 2\\ 1& 3& 2& 2& 4\end{array}\right)$

Elk kental van C² stelt het aantal verbindingen tussen twee knooppunten voor met precies één tussenstation, het aantal tweestapsverbindingen tussen twee punten dus. Tussen E en A bestaat geen twee stapsverbinding. In C + C² komen geen nullen voor omdat tussen elk tweetal knooppunten een één- of een tweestapsverbinding bestaat (soms meerdere).
De graad van verbinding is 6 / 10 = 0,6, dus 60% van alle mogelijke verbindingen bestaat ook echt.