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
Student universiteit - dinsdag 13 januari 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.
