Matrices en grafen

Matrices en grafen > Grafen

Voorbeeld 1

Stel de bij deze graaf passende verbindingsmatrix $C$ op en laat door berekening zien dat in $C^{2}$ nog wel nullen voorkomen, maar in $C + C^{2}$ 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 = (\begin{matrix} 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{matrix})$ , $C^{2} = (\begin{matrix} 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{matrix})$
en $C + C^{2} = (\begin{matrix} 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{matrix})$

Elk kental van $C^{2}$ 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 tweestapsverbinding. In $C + C^{2}$ 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.

Opgave 3

Bij een ongerichte graaf kun je een verbindingsmatrix opstellen. Die zegt iets over de mate waarin er verbindingslijnen zijn.In Voorbeeld 1 wordt zo'n verbindingsmatrix $C$ gebruikt.

Reken zelf het voorbeeld na.

De diameter (het maximale aantal stappen dat nodig is om van het éne knooppunt naar het andere te komen) is $2$ ? Hoe zie je dat aan $C + C^{2}$ ?

Welke driestapsverbindingen zijn er vanuit knooppunt $C$ ?

Waarom zijn er in deze verbindingsgraaf maximaal $10$ verbindingslijnen mogelijk? Welke verbindingslijnen ontbreken er?

verder | terug