WisFaq!

Re: Reguliere grafen en isomorfismen

Hoi Christophe,

Is er een algemene regel die luidt dat het complement altijd niet isomorf is met de gegeven graf.

Ik zie makkelijk in dat die het geval is als het aantal bogen van de gegeven graf en het complement niet gelijk zijn en in mijn geval bij n = 4 komt dit ook uit.
Maar bestaat zoiets algemeen?

mbg J

Jeffrey
17-12-2005

Antwoord

Hey,

(De regel die ik in mijn vorige antwoord gebruikte was: Als twee grafen onderling isomorf zijn, dan zijn ook hun complementen onderling isomorf). Nu vraag je dus naar een andere eigenschap, namelijk dat een graaf altijd niet-isomorf is met zijn eigen complement. Wel, dat is niet zo.

Een graaf en zijn complement hebben samen altijd evenveel bogen als een complete graaf, dus als er n toppen zijn zijn dat n(n-1)/2 bogen. Nu, als je dat in twee gelijke delen wil verdelen dan moet n(n-1)/2 dus een tweevoud zijn, of dus n(n-1) moet een viervoud zijn, dus moet n of n-1 een viervoud zijn, dus moet n ofwel een viervoud zijn, ofwel een viervoud plus één. Dit is dus al een nodige voorwaarde opdat een graaf isomorf zou kunnen zijn met zijn complement.

Als we de triviale gevallen n=0 en n=1 even buiten beschouwing laten, dan is het eerste geval n=4. En daar stuiten we meteen al op een tegenvoorbeeld van jouw vermoeden: als je een graaf beschouwt met toppen A, B, C, D, en met bogen AB, BC, CD, dan is die isomorf met zijn complement: die heeft dezelfde toppen en als bogen AC, AD, BD. Als je het natekent zie je dat die isomorf zijn. Ook bij n=5 vind je vrij eenvoudig een tegenvoorbeeld, nl. teken maar eens de graaf met als bogen AB, BC, CD, DE, EA, en teken dan zijn complement: je komt twee keer uit op een 5-cykel.

Ik vermoed dat je ook bij n=8,9,12,13,16,... nog voorbeelden kan vinden van grafen die isomorf zijn met hun eigen complement (en allicht zal je er voor grotere n steeds meer vinden)

Ik hoop dat dit was wat je bedoelde...
Groeten,
Christophe.

Christophe
18-12-2005