Stel een reguliere graaf met graad 4 en 7 toppen. Geef de verschillende niet isomorfe grafen.
Graag had ik hoeveel er zijn. Ik had gedacht dat er maar éen mogelijkheid is en ik vermoed dat ik kan concluderen dat in het algemeen reguliere grafen geen isomorfismen heeft. Is mijn bedenking juist. Is er geen mooi bewijs of desnoods een tegenbewijs..
Bedankt
Jeffre
Student universiteit België - zaterdag 3 december 2005
Antwoord
Dag Jeffrey,
Je eerste idee is denk ik niet het juiste: in de meeste gevallen zullen er meerdere niet-isomorfe k-reguliere grafen zijn met n toppen. Alleen bij extreme waarden zal je een unieke graaf bekomen, namelijk bij - k=0 (lege graaf); - k=1 en n is even (graaf bestaat uit n/2 'lijnstukken'); - en hun complementen (k=n-1; k=n-2 en n is even); - en bij n=5 en k=2; - bij de gevallen waarbij zowel k als n oneven zijn krijg je natuurlijk nooit een oplossing. (het kan zijn dat dit onvolledig is)
Jouw voorbeeld zit niet in die gevallen. Ik denk dat het eenvoudiger zal zijn om het complement van de graaf te bekijken: dat is dan een graaf met 7 toppen die 2-regulier is. Nu is een 2-reguliere graaf altijd een cykel, of een verzameling cykels. Zo een cykel bestaat uit minstens 3 toppen, dus in dit geval kan je ofwel kiezen voor een 7-cykel, ofwel voor een 3- en een 4-cykel. Dus kom ik op twee niet-isomorfe grafen die aan jouw voorwaarden voldoen.
De adjacentiematrices hiervoor zijn respectievelijk:
Re: Reguliere grafen en isomorfismen 