WisFaq!

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 liever niet
10-7-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
11-7-2013