WisFaq!

\require{AMSmath} geprint op vrijdag 29 maart 2024

4-regular graaf met 6 knopen

Beste wisfaq, ik zit met het volgende probleem

Gevraagd is om alle (niet isomorfe) grafen met 6 knopen te vinden, waarbij elke knoop graad 4 heeft. In principe is het niet zo moeiijk om 1 zo’n graaf te vinden. Ik vroeg me echter af hoeveel van dit soort (niet isomorfe) graven er zijn, en hoe ik dit kan bewijzen (het is namelijk niet erg efficient of met trial en error te werk te gaan en dan kijken of een gevonden graaf isomorf is aan mijn eerst gevonden graaf (in een 6 hoek nummer de hoeken 1,2,3,4,5,6 en verbind 1-2-3-4-5-6 en daarnaast 1 met 5 en 3, 5 met 3, 2 met 6 en 4 en 6 en 4))

Bij voorbaat dank,

Herman

herman de vries
13-1-2009

Antwoord

Beste Herman,
Soms is het handiger om te kijken naar de duale graaf, d.w.z. de graaf waar lijnen staan op de plaats waar in je oorspronkelijke graaf juist geen lijnen stonden en omgekeerd.
Een volledige graaf met 6 punten heeft 15 lijnen. Als elk punt graad 4 heeft zijn er 4x6/2=12 lijnen.
De duale graaf heeft dus 15-12=3 lijnen en 6 punten. Elk punt moet nu graad 5-4=1 zijn.
En dan zie je al snel het antwoord op je vraag hoop ik. Laat maar weten al dat niet zo is.
Groet,
Lieke.

ldr
24-1-2009


© 2001-2024 WisFaq
WisFaq - de digitale vraagbaak voor het wiskunde onderwijs - http://www.wisfaq.nl

#57890 - Grafen - Student universiteit