De digitale vraagbaak voor het wiskundeonderwijs

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

HOME

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

inloggen

colofon

  \require{AMSmath} Printen

Duale graaf probleem

Hallo,

Ik zit vast bij duale grafen. Ik snap wel wat je wil bekomen. Je hebt vb een takkleuringsprobleem en wil er een knoopkleuringsprobleem van maken. Dat kan mbv. een duale graaf. Mijn vraag is dan ook: hoe stel je zo een graaf op?. Ik was hier al op iets gekomen, maar dat is precies een andere methode... Ik zal even zeggen hoe het hier staat:

1) Elke tak in G wordt voorgesteld als een knoop v'(e) in G'
2) Elke knoop v in G ( met invallende takken e1,...,en) wordt voorgesteld mbv. n∑(n-1)/2 takken in G': de knopen v'(e1), v'(e2), ..., v'(en) worden allemaal onderling verbonden.

Dat eerste snap ik, maar van dat 2de snap ik niets. Ik weet gewoon niet wat je daar moet doen. Kan iemand me dat uitleggen?

Alvast bedankt!

Zeg ik
Student universiteit BelgiŽ - woensdag 10 juli 2013

Antwoord

Het klinkt flauw, maar het staat er goed. In iets andere woorden: als twee takken $e_1$ en $e_2$ in $G$ samenkomen in een knoop $v$ dan moeten de knopen $v'(e_1)$ en $v'(e_2)$ in $G'$ verbonden worden.
Dus, als in $G$ in de knoop $v$ drie takken $e_1$, $e_2$ en $e_3$ samenkomen dan moeten de drie knopen $v'(e_1)$, $v'(e_2)$ en $v'(e_3)$ in $G'$ allemaal verbonden worden met takken; op de plaats van $v$ ontstaat dus een driehoek.
Als in $v$ tien takken samenkomen wordt $v$ in feite vervangen door een volledige graaf met tien punten (en die heeft $10*(10-1)/2$ takken.

kphart
Vragen naar aanleiding van dit antwoord? Klik rechts..!
donderdag 11 juli 2013



home |  vandaag |  bijzonder |  gastenboek |  statistieken |  wie is wie? |  verhalen |  colofon

©2001-2023 WisFaq - versie 3