Matrices en grafen > Grafen
123456Grafen

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 = ( 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 ) , C 2 = ( 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 )
en C + C 2 = ( 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 )

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.

a

Reken zelf het voorbeeld na.

b

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 ?

c

Welke driestapsverbindingen zijn er vanuit knooppunt C ?

d

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

verder | terug