Matrices en grafen

Matrices en grafen > Grafen

Voorbeeld 2

In deze graaf is sprake van éénrichtingsverkeer.
Stel een bijpassende directe-wegen-matrix $D$ op. Laat zien dat je in maximaal drie stappen (dus met via twee andere knooppunten) van elk punt van de graaf naar elk ander punt kunt komen.

> antwoord

De directe-wegen-matrix is nu niet symmetrisch, dus je moet goed het "van ... naar ..." in de gaten houden. Bij deze graaf maak je bijvoorbeeld een schema als in de tabel hiernaast.
Je vindt dan $D = (\begin{matrix} 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 & 1 \\ 0 & 1 & 0 & 0 & 1 \\ 0 & 1 & 0 & 0 & 0 \\ 1 & 0 & 1 & 1 & 0 \end{matrix})$ .

Ga na dat in $D$ en in $D + D^{2}$ nog nullen voorkomen, pas in $D + D^{2} + D^{3}$ niet meer.
Dit betekent dat inderdaad tussen elke twee knooppunten van de graaf minstens één verbinding bestaat van één of twee of drie stappen.

Opgave 4

Bekijk nu de graaf in Voorbeeld 2.

Waarom is hier sprake van een gerichte graaf?

Hoe kun je aan de directe-wegen-matrix $D$ zien dat er sprake is van éénrichtingsverkeer?

Bereken nu $D + D^{2}$ en $D + D^{2} + D^{3}$ en leg met behulp van het resultaat uit dat de diameter van deze graaf $3$ is.

Geef een voorbeeld van een route die alleen in drie stappen mogelijk is.

Waarom zijn er maximaal $20$ directe wegen mogelijk? Hoeveel bedraagt nu de graad van verbinding?

Opgave 5

Welke van de onderstaande grafen zijn gelijk?

verder | terug