Categorie archieven: Discrete wiskunde

Kleuringen

Geplaatst op door

Op hoeveel verschillende manieren kunnen we de hoekpunten van een gelijkzijdige driehoek kleuren als we alleen over de drie hoofdkleuren rood,geel en blauw mogen beschikken. Twee kleuringen zijn gelijk als ze door een draaing op elkaar overgaan.

 

  • Een eerste manier werkt als volgt: als je slechts 1 kleur gebruikt zijn er drie mogelijkheden. als je twee kleuren gebruikt zijn er 6 oplossingen en als je alle drie de kleuren gebruikt dan zijn er 2 mogelijkheden. in het totaal heb je dus 11 mogelijke kleuringen.
  • Een tweede manier maakt gebruik van de stelling van Burnside: Als een eindige groep werkt op een verzameling , dan is het aantal verschillende configuraties “tot symmetrie” (dus het aantal banen/orbits) gegeven door de formule

        \[\frac{1}{|G|}\sum_{g \in G} |Fix(g)|\]

    met Fix(g) bedoelt men de verzameling elementen x van X die door g worden vastgehouden. In ons voorbeeld noemen we voor G de rotaties van een gelijkzijdige driehoek; dus een draaiing over 0^{circ},120^{\circ}, 240^{\circ}. Voor X nemen we alle mogelijke kleuringen van de hoekpunten met de drie gegeven kleuren. G telt dus 3 elementen. |Fix( 0^{\circ}}|=3^3=27 en |Fix( 120^{\circ})|=|Fix( 240^{\circ})|=3. Volgens de stelling van Burnside zijn er dus

        \[\frac{1}{3}(27+3+3)=11\]

    oplossingen

  • Er bestaat ook een formule die het probleem oplost voor een willekeurige regelmatige. n-hoek:

        \[\frac{1}{n}\sum_{d|n}\varphi(\frac{n}{d})m^d\]

    Hierbij stelt m het aantal beschikbare kleuren voor en is \varphi de totïent functie van Euler.


                     

Art gallery theorema

Geplaatst op door

Het art gallery theorema (of kunstgalerijtheorema) is een bekend resultaat uit de computationele meetkunde. Het werd voor het eerst geformuleerd door de wiskundige Victor Klee in 1973 en later bewezen door Václav Chvátal in 1975.

Stel je hebt een kunstgalerij die de vorm heeft van een veelhoek (polygoon) met n hoeken . Je wilt bewakers plaatsen zodat elke plek in de galerij zichtbaar is voor ten minste één bewaker. De vraag is: Hoeveel bewakers zijn minimaal nodig? Het theorema zegt:

    \[\left\lfloor \frac{n}{3} \right\rfloor\]

bewakers zijn altijd voldoende en soms noodzakelijk om een veelhoek met hoeken volledig te bewaken. Een veelhoek met hoeken kan altijd bewaakt worden door hoogstens bewakers.

Het bewijs maakt gebruik van triangulatie van veelhoeken: Elke veelhoek kan worden opgedeeld in driehoeken. Dan kan men de driehoeken inkleuren met drie kleuren (vergelijkbaar met grafen die drie-kleurig zijn). Er bestaat altijd minstens één kleur die in hoogstens \left\lfloor \frac{n}{3} \right\rfloor driehoeken voorkomt. Als je bewakers in de hoekpunten van die kleur zet, kun je de hele veelhoek bestrijken.

Hieronder zie je een voorbeeld van een 10 hoek:

 

De chromatische veelterm

Geplaatst op door

In de grafentheorie speelt het inkleuren van grafen een centrale rol. Hoeveel manieren zijn er om de knopen van een graaf te kleuren, zodat aangrenzende knopen altijd verschillende kleuren krijgen? Deze eenvoudige vraag leidde tot de introductie van een krachtig wiskundig object: de chromatische veelterm.

Stel dat we een graaf hebben met knopen. Een \lambda-kleuring is een toewijzing van \lambda kleuren aan de knopen, waarbij buren (knopen die door een boog  verbonden zijn) nooit dezelfde kleur mogen hebben. Het aantal mogelijke geldige \lambda-kleuringen hangt natuurlijk af van zowel G als van \lambda. Voor elk natuurlijk getal kunnen we dus het aantal geldige -kleuringen tellen. Verrassend genoeg blijkt dit aantal altijd gegeven te worden door een veelterm in \lambda. Deze veelterm noemen we de chromatische veelterm van , genoteerd als P(G,\lambda). Een voorbeeld:

Er is een verband met het chromatisch getal van een graaf G: het kleinste aantal kleuren dat nodig is om de knopen van zo te kleuren dat geen twee aangrenzende knopen dezelfde kleur krijgen. Het chromatisch getal van een graaf G is dus het kleinste getal \lambda waarvoor de chromatische veelterm positief is.

Enkele vaststellingen:

  1. Een lege graaf met n knopen (geen bogen):
    Elke knoop kan willekeurig één van de \lambda kleuren krijgen, dus P(G,\lambda)=\lambda^n.
  2. Voor volledige grafen is de situatie eenvoudig. Zo geldt voor de volledige graaf  K_3 op 3 knopen dat p(K_3,\lambda)= \lambda(\lambda-1)(\lambda-2). 

 

Euler circuit

Geplaatst op door

Een Eulerpad in een graaf is een pad waarbij elke lijn juist 1 keer wordt aangedaan.

We spreken van een Eulercircuit als bovendien vertrekpunt en eindpunt van het pad dezelfde zijn. Bvb 4 3 0 1 2 0 4

Het was Euler die volgende stelling over Eulercircuits bewezen heeft:

Een samenhangende graaf heeft een Eulercircuit als en slechts als elk punt van de graaf een even graad heeft.

Kijk maar naar de graden in  volgend voorbeeld:

Ook het probleem van de bruggen van Koningsberg is hiermee opgelost. Alle punten van de graaf hebben graad 3 en bijgevolg is een route langsheen de vier bruggen, waarbij elke brug precies één keer bewandeld wordt en waarbij men terugkeert naar de startplaats, niet te vinden.

36 officieren

Geplaatst op door

Het 36 officieren probleem, ook wel bekend als het probleem van Euler’s 36 officieren, is een beroemde puzzel in de combinatoriek, bedacht door de wiskundige Leonhard Euler in 1782. Het probleem kan als volgt worden omschreven:

Stel je hebt een leger van 36 officieren, bestaande uit 6 verschillende regimenten en 6 verschillende rangen. Je moet deze 36 officieren opstellen in een 6×6 rooster, zodanig dat in elke rij en elke kolom precies één officier van elk regiment en één officier van elke rang voorkomt.

Euler conjectureerde dat dit probleem geen oplossing heeft voor een 6×6 rooster, en dit werd later bewezen door Gaston Tarry (1843-1913) in 1901. Het betekent dat het onmogelijk is om een 6×6 rooster te vullen met deze eigenschappen. De onmogelijkheid van het oplossen van het 36-officieren probleem komt voort uit het feit dat het een speciaal geval is van het algemene probleem van het vinden van “orthogonale Latijnse vierkanten”. Latijnse vierkanten zijn roosters waarbij in elke rij en kolom elke symbool precies één keer voorkomt. Twee Latijnse vierkanten zijn orthogonaal als je ze over elkaar legt en elke combinatie van symbolen precies één keer voorkomt. Voor n=6 bestaat er geen paar van orthogonale Latijnse vierkanten, wat het 36-officieren probleem onoplosbaar maakt.

Euler vermoedde dat als n=4k+2, waarbij k een natuurlijk getal is, er geen paar orthogonale Latijnse vierkanten van n\times n bestaat. Dit vermoeden werd pas in 1959 ontkracht, toen de wiskundigen Bose,Shikhande en Parker een paar orthogonale Latijnse vierkanten van 22 \times 22 maakten. 

Er bestaan wel oplossingen als bijvoorbeeld  n=5 en n=7