Springen naar inhoud

Grafentheorie (sudoku)- bewijs dat de graaf regulier is


  • Log in om te kunnen reageren

#1

barrel

    barrel


  • >25 berichten
  • 42 berichten
  • Gebruiker

Geplaatst op 27 april 2008 - 15:50

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

Dit forum kan gratis blijven vanwege banners als deze. Door te registeren zal de onderstaande banner overigens verdwijnen.

#2

barrel

    barrel


  • >25 berichten
  • 42 berichten
  • Gebruiker

Geplaatst op 29 april 2008 - 08:16

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





0 gebruiker(s) lezen dit onderwerp

0 leden, 0 bezoekers, 0 anonieme gebruikers

Ook adverteren op onze website? Lees hier meer!

Gesponsorde vacatures

Vacatures