De digitale vraagbaak voor het wiskundeonderwijs

home |  vandaag |  gisteren |  bijzonder |  prikbord |  gastenboek |  wie is wie? |  contact

HOME

samengevat
vragen bekijken
een vraag stellen
hulpjes
zoeken
FAQ's
links
twitter
boeken
help

inloggen

colofon

  \require{AMSmath}

Grafen

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
23-1-2017

Antwoord

Printen
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

WvR
23-1-2017


Verschil tussen isomorfe en gelijke grafen

Hallo,
Ik heb het nu over grafen op school en wat ik niet begrijp is het verschil tussen isomorfe en gelijke grafen.
Wat ik er nu van begrijp is dat als grafen dezelfde buren hebben (als elk punt gelabeld is en tegenover hetzelfde punt staat) en evenveel lijnen erdoor lopen dat ze dan gelijk zijn en dat een graaf isomorf is als ze evenveel lijnen hebben als je de graaf herlabeld. Is dit waar?

Sefanj
15-9-2017

Antwoord

Printen
Twee grafen zijn gelijk als ze precies dezelfde punten en dezelfde lijnen hebben.
Ze zijn isomorf als ze er precies hetzelfde uitzien maar niet precies hetzelfde gelabeld zijn.
Bijvoorbeeld: Stel $V=\{1,2,3,4\}$ en $L_1=\{\{1,2\}\}$; dit geeft een graaf met vier punten en één lijn, tussen $1$ en $2$.
Met dezelfde $V$ en $L_2=\{\{3,4\}\}$ krijg je ook zo'n graaf maar nu met het ene lijntje van $3$ naar $4$, deze is niet gelijk aan de eerste.
De herlabeling $1\to3$, $2\to4$, $3\to2$, $4\to1$ laat zien dat deze twee grafen isomorf zijn.

kphart
15-9-2017


klein |  normaal |  groot

home |  vandaag |  bijzonder |  twitter |  gastenboek |  wie is wie? |  colofon

©2001-2017 WisFaq - versie IIb

eXTReMe Tracker