WisFaq!

De digitale vraagbaak voor het wiskundeonderwijs

HOME

samengevat

\require{AMSmath}

Puntchromatisch getal

hoi

Ik zit met een probleempje. Ik moet bewijzen dat voor elke graaf G(p,q), dus met p punten en q lijnen, geldt dat:
c(G)=p²/(p²-2q)
Ik kom hier echter niet uit. De c is het puntchromatisch getal van de graaf.

Alvast bedankt voor hulp

groetjes Marian
Marian
Student universiteit - woensdag 2 maart 2005

Antwoord

Hi Marian,

Best wel een interessante stelling, die een ondergrens geeft voor het chromatisch getal. Ik heb een bewijs gevonden, maar misschien kan het wel een stuk eenvoudiger, steunend op voorafgaande eigenschappen of zo, of door met eigenwaarden te werken, ik zeg maar wat.

Ik duid de eigenschap c(G) p²/(p²-2q) verder aan met (*)

Ik geef een bewijs uit het ongerijmde. Stel dat er grafen bestaan waarvoor (*) niet geldt. Kies dan een p waarvoor er een graaf bestaat waarvoor (*) niet geldt. Van alle grafen met p toppen waarvoor (*) niet geldt, kies je dan die met de hoogste q-waarde, dus met zoveel mogelijk bogen.

Deze graaf noem ik G. G is al zeker niet compleet (waarom?). Ik kan dus aan G een boog toevoegen, dan kom ik op G', en dan zal bij G' zeker WEL de eigenschap (*) gelden.

c(G) p²/(p²-2q) bij onderstelling. Als je nu bij G een boog toevoegt, dus q vervangt door q+1, dan stijgt het rechterlid (ga maar na). Het chromatisch getal blijft ofwel gelijk, ofwel stijgt het met een eenheid. Echter, G' voldoet wel aan (*). Dat kan enkel als het chromatisch getal van G' 1 meer is dan het chromatisch getal van G.

Goed, bekijk nu een kleuring in c kleuren van de graaf G. Door toevoeging van eender welke boog stijgt het chromatisch getal. Dat betekent dat twee niet-adjacente toppen steeds dezelfde kleur moeten hebben: immers, als ze een verschillende kleur hadden dan zou toevoeging van de boog tussen deze twee toppen een kleuring in c kleuren van G' opleveren.

Elke twee niet-adjacente toppen van G hebben dus dezelfde kleur. Dat impliceert dat niet-adjacentie in G een transitieve eigenschap is: als a niet-adj met b, dan hebben a en b dezelfde kleur. Als b niet-adj met c, dan hebben b en c dezelfde kleur. Dus hebben a en c dezelfde kleur, en dus zijn a en c niet-adj.

Dat betekent dat het complement van G (dat is dus de graaf met dezelfde toppen, maar waar er vroeger een boog was is er nu geen meer, en omgekeerd) bestaat uit een aantal complete grafen.

Voor G zelf betekent dit laatste dat G compleet multipartiet is, dus dat je de toppen in groepjes kan verdelen en waarbij toppen uit eenzelfde groep nooit adjacent zijn en toppen uit verschillende groepen altijd adjacent zijn.

Als je dan de adjacentiematrix van G opstelt (en je ordent je toppen logisch, dus volgens de partitie die je hebt) dan krijg je het volgende beeld, bv met een partitie van 4,2,2,1:

0 0 0 0 1 1 1 1 1
0 0 0 0 1 1 1 1 1
0 0 0 0 1 1 1 1 1
0 0 0 0 1 1 1 1 1
1 1 1 1 0 0 1 1 1
1 1 1 1 0 0 1 1 1
1 1 1 1 1 1 0 0 1
1 1 1 1 1 1 0 0 1
1 1 1 1 1 1 1 1 0

Hier is c gelijk aan 4 omdat er 4 groepen zijn. We willen een strijdigheid bekomen, dus we willen bewijzen dat de aanname dat (*) niet geldt, fout is. We proberen dus te bewijzen dat (*) wel geldt. Merk op dat (*) zegt dat c minstens gelijk is aan het aantal elementen uit de matrix, gedeeld door het aantal nullen in de matrix.

Duid nu het aantal toppen per groep aan met n_i, i loopt dus van 1 tot c. De som van alle n_i is natuurlijk gelijk aan p.

Te bewijzen is dus nu: c maal aantal nullen aantal elementen, dus:
c å n_i² (ån_i)²
Deel door x², dan staat er:
1/c * å n_i² (ån_i/c)²

Elke som heeft hierin c termen, dus er staat eigenlijk: Het gemiddelde van een aantal kwadraten is minstens gelijk aan het kwadraat van het gemiddelde. En dat is iets wat denk ik wel te bewijzen is... Ik zie niet direct hoe, maar het komt mij wel bekend voor, heb je in de statistiek ook niet een gelijkaardige formule? Enfin, ik kon geen tegenvoorbeelden vinden, en blijkbaar geldt de gelijkheid enkel als de n_itjes allemaal gelijk zijn.

Daarmee is de strijdigheid bewezen: vertrokken van de onderstelling dat (*) niet geldt voor een G is er aangetoond dat G een speciale vorm moet hebben, en daarna is aangetoond dat (*) wel moet gelden voor G, vandaar de strijdigheid.

Als je nog vragen of opmerkingen hierbij hebt, reageer dan gerust.

Groeten,
Christophe.

Christophe

Vragen naar aanleiding van dit antwoord? Klik rechts..!
vrijdag 4 maart 2005