Diagonaalelementen bij een tweestapswegenmatrix

Beste,

Van een graaf kunnen we een directewegenmatrix opstellen. Daar kunnen we aflezen hoeveel directe wegen van een punt (stad) naar een ander punt (stad) leiden.

Als ik nu het kwadraat neem van de directewegenmatrix, bekom ik een matrix waarin het aantal tweestapswegen aangegeven worden.
Dit is duidelijk, behalve voor de elementen op de diagonaal (dus van bijv stad A naar stad A).


Bij de tweestapsmatrix is het eerste diagonaalelement 4. Maar hoe kan ik op 4 verschillende manieren van A naar A gaan in twee stappen? Ik zie er maar twee.

Alvast bedankt.

Pandol
3de graad ASO - maandag 23 januari 2017

Antwoord

Je kunt van A naar A in twee stappen via B. Dat is dan:

heen bovenover - terug bovenover
heen bovenover - terug onderlangs
heen onderlangs - terug bovenover
heen onderlangs - terug onderlangs

...en dat zijn er dan 4. Helpt dat?

Zie Meerstapswegen en matrices

maandag 23 januari 2017

©2001-2024 WisFaq