Grafentheorie (sudoku)- bewijs dat de graaf regulier is

Moderators: ArcherBarry, Fuzzwood

Reageer

Bericht 27-04-'08, 16:50

barrel

Berichten: 42

Grafentheorie (sudoku)- bewijs dat de graaf regulier is

Hallo allemaal,

Binnenkort moet ik een taak inleveren waarin 1 vraag een Sudoku als een kleuringsprobleem opvat. Deze moet uitgewerkt worden, waarbij bijv. de omzetting naar het kleuringsprobleem moet worden uitgelegd, de graad van de graaf gevraagd wordt (20, tenzij is me vergis ;-) en als laatste vraag: bewijs dat de graaf regulier is.

Deze laatste vraag is simpel te begrijpen ; elk vakje moet een ander getal (lees kleur) hebben dat een willekeurig vak in zijn vierkant alsook een andere kleur tov een willekeurig getal in rij en kolom. Dit geldt voor elk vakje in een sudoku, dus hebben ze allemaal dezelfde graad (20).

Mijn vraag; kan iemand me een hint geven hoe ik dit wiskundig kan bewijzen?

Alvast bedankt,

Barry
Omhoog

Bericht 29-04-'08, 09:16

barrel

Berichten: 42

Re: Grafentheorie (sudoku)- bewijs dat de graaf regulier is

Oei... niemand?

Na wat zoeken denk ik dat de enige mogelijkheid is om dit vanuit het ongerijmde te bewijzen.

Maar daar loop ik al snel vast.

Stel dat een sudoku niet regulier is, dan is er in de graaf dus minstens 1 knoop die een andere graad heeft dan een andere.

Als deze graad minder is, dan betekent dat dat deze knoop verbonden kan worden aan een punt met dezelfde kleur, wat niet mogelijk is. Als deze knoop een graad hoger heeft, dan is deze verbonden met een knoop uit een andere rij, kolom of drievlak....

Moeilijke materie (voor mij toch), als iemand een hint kan geven?

Barry
Omhoog
Reageer

Terug naar “Huiswerk en Practica”