Tag archieven: grafen

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.

Voetbal

Geplaatst op door

 

Op een voetbal komt een netwerk van bogen voor, die de oppervlakte van de bal verdelen in een aantal gebieden. Sommige van die gebieden worden door vijf bogen begrensd en zijn dus vijfhoekig van vorm; de rest van de gebieden is zeshoekig. Bij elk knooppunt van het netwerk komen drie gebieden samen; twee daarvan zijn zeshoekig en het derde is vijfhoekig. De vijfhoekige gebieden zijn zwart en de zeshoekige zijn wit. Elk vijfhoekig gebied omgeven wordt door een krans van vijf zeshoekige gebieden. 

Noemen we het aantal knooppunten V ( vertrices), E het aantal bogen (edges) en F het aantal gebieden (faces). Euler zegt dat

    \[V-E+F=2\]

  • Stel x het aantal vijfhoeken en y het aantal zeshoeken. Er zijn dus 5x , maar ook 6y knooppunten ( want in elk hoekpunt komen 2 zeshoeken samen). Bijgevolg is y=\frac{5}{3}x.
  • Alle vijfhoeken en zeshoeken hebben samen 5x + 6y = 5x + 10x= 15x zijden. Bij elke boog van het netwerken vallen twee zijden samen dus E=\frac{15}{2}x.
  • Het aantal gebieden wordt gegeven door F=x+y=\frac{8}{3}x .

De formule van Euler voor veelvlakken wordt nu : 5x-\frac{15}{2}x+ \frac{8}{3}x=2 of x=12

Onze voetbal is dus opgebouwd uit 12 vijfhoeken en 20 zeshoeken, dus 32 zijvlakken; Verder zijn er 60 knooppunten en 90  bogen.

In de wiskunde noemt men deze figuur : de afgeknotte isocaëder.

 

 

 

7 bruggen van Koningsbergen

Geplaatst op door

De grote wis- en natuurkundige Leonhard Euler (1707-1783) publiceerde
in 1736 het zogenaamde Koningsberger bruggenprobleem. De stad Koningsbergen, die sinds 1945 Kaliningrad heet, ligt aan de oevers van en op twee eilanden in de rivier de Pregel. De oevers en de eilanden waren in Eulers tijd verbonden door zeven bruggen. De Koningsbergers waren gewend ’s zondags een lange wandeling door de stad te maken en Euler vroeg zich nu af of hij  een wandeling  zou kunnen ontwerpen, waarbij elk der bruggen juist eenmaal zou gepasserd worden.

We vereenvoudigen de plattegrond van Koningsbergen door elk der vier stadsdelen A, B, C en D door een punt voor te stellen en elk der zeven bruggen door een lijn. Een dergelijke figuur noemt men een graaf.  De  graaf in ons probleem heeft vier hoekpunten en zeven kanten. We kunnen het bruggenprobleem nu zo formuleren: Is het mogelijk de graaf zo te doorlopen, dat daarbij elk der kanten slechts éénmaal gepasseerd wordt? Beginnen we bijv. bij het hoekpunt A, dan moet daar een ,,uitgaande kant”, maar ook een ,,inkomende kant” zijn. Telkens als we via een der kanten in een hoekpunt aankomen, moet daar weer behalve de ,,inkomende” ook een ,,uitgaande kant” zijn. Hieruit blijkt, dat als we de graaf zo willen doorlopen, dat we elk der kanten slechts eenmaal gebruiken, er bij elk hoekpunt een even aantal kanten moeten samenkomen. Aangezien dat niet het geval is, is het onmogelijk een wandeling door Koningsbergen te organiseren, waarbij elk der bruggen slechts éénmaal doorlopen wordt.