Algebra

Analyse

Bewijzen

De grafische rekenmachine

Discrete wiskunde

Fundamenten

Meetkunde

Oppervlakte en inhoud

Rekenen

Schoolwiskunde

Statistiek en kansrekenen

Telproblemen

Toegepaste wiskunde

Van alles en nog wat


\require{AMSmath}

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
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.

ldr
zaterdag 24 januari 2009

©2001-2024 WisFaq