WisFaq!

De digitale vraagbaak voor het wiskundeonderwijs

HOME

samengevat

\require{AMSmath}

Reguliere grafen en isomorfismen

Hoi,

Vertrekkend van het volgende probleem

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:

0 1 0 0 0 0 1
1 0 1 0 0 0 0
0 1 0 1 0 0 0
0 0 1 0 1 0 0
0 0 0 1 0 1 0
0 0 0 0 1 0 1
1 0 0 0 0 1 0

en

0 1 1 0 0 0 0
1 0 1 0 0 0 0
1 1 0 0 0 0 0
0 0 0 0 1 0 1
0 0 0 1 0 1 0
0 0 0 0 1 0 1
0 0 0 1 0 1 0

Voor de grafen die jij vroeg: neem hiervan het complement, dus verander elke 1 in een 0 en vice versa, behalve op de diagonaal.

Dat het er twee zijn wordt bevestigd op deze pagina (onderaan wordt N(n,r) ingevoerd, jij vroeg in die notatie naar N(7,4))

Groeten,
Christophe.

Christophe

Vragen naar aanleiding van dit antwoord? Klik rechts..!
zondag 4 december 2005

Re: Reguliere grafen en isomorfismen