Matrices en grafen

Matrices en grafen > Grafen

Voorbeeld 2

In deze enkelvoudige graaf is sprake van eenrichtingsverkeer.
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 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 eenrichtingsverkeer?

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 verbindingsgrafen zijn gelijk?

verder | terug