klieks

© h.hofstede (h.hofstede@hogeland.nl)

Veel of juist weinig verbonden....

Weinig verbonden:
Een verzameling knooppunten van een graaf heet een onafhankelijke set als tussen geen enkele van die knooppunten een directe verbindingslijn loopt. De maximale onafhankelijke set van een graaf is degene met de meeste knooppunten, en dat grootst mogelijke aantal knopen heet het onafhankelijkheidsgetal van G. We geven het aan met α(G).

Veel verbonden:
Een bedekking van een graaf G is een verzameling knooppunten uit G waarvoor geldt dat elke verbindingslijn van G minstens één uiteinde in die verzameling heeft. De minimale bedekking van G is de bedekking met zo min mogelijk knooppunten. We geven dat aantal knooppunten aan met β(G).

Stelling 1.

S is een onafhankelijke set ⇔ V\S is een bedekking

(V is de verzameling van alle knooppunten van een graaf. V\S betekent: "De verzameling V met daaruit weggelaten de verzameling S")

Bewijs.

Als S een onafhankelijke set is, dan heeft geen enkele verbindingslijn begin- en eindpunt in S.
Dus heeft elke verbindingslijn minstens één uiteinde in V\S.
Dus is V\S een bedekking.
En andersom geldt precies het zelfde (gewoon deze redenering van onder naar boven volgen)

■

Stelling 2.

α + β = K

(K is het totaal aantal knooppunten van de graaf)

Bewijs.

Stel dat S een maximale onafhankelijke set is, en B een minimale bedekking
Dan is volgens de vorige stelling V\B een onafhankelijke set en V\S een bedekking.

K - β is het aantal elementen van V\B en is dus hoogstens gelijk aan α. Immers V\B is een onafhankelijke set en de grootste was S
Daaruit volgt K ≥ α + β .....(1)

K - α is het aantal elementen van V\S en is dus minstens gelijk aan β. Immers V\S is een bedekking en de kleinste was B
Daaruit volgt K ≤ α + β ......(2)

Omdat beiden moeten kloppen moet dus wel gelden K = α + β

■

Een kliek is een (deel)verzameling van knooppunten van een graaf die samen een complete subgraaf vormen (compleet betekent dat elk knooppunt met elk ander knooppunt is verbonden, wist je nog?).
Als een graaf G geen grote klieks heeft, dan zou je (lijkt mij) verwachten dat zo'n graaf juist wel een grote onafhankelijke set heeft.

En dat blijkt ook zo te zijn!

Maar hoe die zaken nou precies van elkaar afhangen is nog niet zo heel eenvoudig. Ramsey onderzocht wat de maximale kliekgrootte K en de grootte van de maximale onafhankelijke set S met elkaar te maken hebben.
Hij ontdekte (1930) dat er voor elke combinatie van K en S een getal r bestaat zodat alle grafen met minstens r knooppunten altijd een kliek van grootte K of een onafhankelijke set van grootte S bevatten
Die getallen r(K, S) heten dan ook de Ramsey-getallen.

Het Ramsey getal r(K, S) is het antwoord op de vraag:

Hoeveel mensen moet ik minstens op mijn verjaardag uitnodigen,
zodat minstens K elkaar allemaal kennen, of minstens S elkaar allemaal niet kennen?

r (K, S)		m a x i m a l e S
r (K, S)		1	2	3	4	5	6	7
m a x i m a l e K	1	1	1	1	1	1	1	1
	2	1	2	3	4	5	6	7
	3	1	3	6	9	14	18	23
	4	1	4	9	18	25	?	?
	4	1	5	14	?	?	?	?

Die vraagtekens zijn nog niet bekend!
Het zal je vast niet verbazen dat de tabel symmetrisch in de hoofddiagonaal is.

Het bewijs dat r(3, 3) = 6

Populairder gesteld is dit de beroemde verjaardagsstelling:

Bij een groep van 6 mensen zijn er altijd drie te vinden die elkaar OF allemaal kennen OF allemaal niet kennen

Je kunt het probleem zó oplossen: kleur de verbindingslijnen van een volledige graaf K₆ met de kleuren rood en groen. (rood betekent "niet verbonden", groen betekent "wel verbonden"). Ga dan op zoek naar de grootste volledige rode (S) of groene (K) subgraaf.

K₅ hierboven is rood-groen gekleurd zonder dat een rode of groene K₃ kunt vinden.
Met K₆ ernaast gaat dat niet lukken..... Dat kun je zó zien:

Kies een knooppunt A.
Dat heeft 5 verbindingslijnen, dus zijn er minstens 3 dezelfde kleur (een mooi voorbeeld van het duiventilprincipe)
Stel dat AB, AC en AD bijvoorbeeld allemaal rood zijn

Bekijk nu driehoek BCD.
• Als die een rode zijde heeft, dan vormt deze zijde samen met de lijnen naar punt A een helemaal rode driehoek.
• Als die geen rode zijde heeft, is hij helemaal groen.

In beide gevallen is er een driehoek die helemaal dezelfde kleur is.
Conclusie: Als je K₆ met twee kleuren gaat kleuren is er altijd een driehoek te vinden waarvan de zijden dezelfde kleur hebben. En als je rood ziet als "niet-verbonden" en groen als "wel verbonden" dan betekent dat, dat er altijd een subgraaf van 3 punten te vinden is die OF volledig verbonden is (een kliek) , OF onafhankelijk is.

Hier is nog een grappig verwant raadsel:

Zes punten liggen in een plat vlak. Ze worden verbonden door 15 lijnstukken die allemaal verschillend van lengte zijn.
Dan is er een lijnstuk dat de kortste zijde van een driehoek is, en tegelijk de langste van een andere driehoek.
Toon dat aan!!!!!

Laten we nog even verder afdwalen: Zouden er, behalve K₆, nog meer grafen zijn die de eigenschap hebben dat er altijd een driehoek van één kleur te vinden is?
Jazeker zijn die er!
Uiteraard elke graaf die een K₆ heeft deze eigenschap. Maar er zijn er meer.
Kijk maar naar de graaf hier rechtsonder. Die is gemaakt door in de figuur links alle punten van de driehoek te verbinden met alle punten van de vijfhoek.

•

Deze bevat geen K₆, immers als je zes zijden kiest zijn er alttijd 3 van de vijfhoek bij, en van die drie zijn er minstens 2 niet met elkaar verbonden.

•

Bekijk de drie zijden van de driehoek. Als ze dezelfde kleur zijn, hebben we al een driehoek gevonden. Als ze niet dezelfde kleur zijn stellen we dat er 2 rood en 1 groen (andersom mag net zo goed). Zie de figuur linksonder.

Stel dat minstens één van de twee knooppunten aan de groene lijn twee rode verbindingen met aangrenzende punten van de vijfhoek heeft, zoals in situatie A met de aangrenzende punten P en Q. Als PR of QR rood zijn, dan is er een helemaal rode driehoek (PRS of QRS). Maar als PR en QR beiden groen zijn, dan is driehoek PRQ helemaal groen. Dus in situatie A is er altijd een driehoek met drie gelijkgekleurde zijden te vinden.
Als er méér dan drie rode lijnen vanaf S gaan, gaan er altijd 2 naar aangrenzende punten van de vijfhoek, en hebben we weer situatie A.

Blijft over het geval dat er vanaf beide knooppunten aan de groene lijn twee rode lijnen naar niet-aangrenzende punten van de vijfhoek gaan. In dat geval gaan er dus vanaf elk van beide punten 3 groene lijnen naar de vijfhoek. Dat zijn zes groene lijnen, dus minstens twee van die zes moeten naar hetzelfde knooppunt van de vijfhoek gaan. Maar dan heb je een helemaal groene driehoek gevonden!

Kortom: er is altijd een driehoek die helemaal van één kleur is.

Oké, genoeg afgedwaald, terug naar de intrigerende wereld van de Ramsey-getallen.

Recursierelatie voor r

Deze titel is een beetje opschepperij. We kunnen niet veel meer doen dan een recursierelatie voor een bovengrens van r geven. Is al moeilijk genoeg.
Er blijkt te gelden :

r(K, S) ≤ r(K, S - 1) + r(K - 1, S)

Bewijs.

Neem een graaf G met r(K, S - 1) + r(K - 1, S) knooppunten, en kies daar een knooppunt P uit.
Dan zijn er twee mogelijkheden:

P grenst NIET aan een verzameling N van minstens r(K, S - 1) knooppunten.

P grenst WEL aan een verzameling W van minstens r(K - 1, S) knooppunten.

Eén van beiden moet wel het geval zijn, immers het totaal aantal knooppunten waar P wel of niet aan grenst is K - 1 (alle knooppunten van de graaf zonder P zelf) Die K - 1 knooppunten moeten over N en W verdeeld worden.

mogelijkheid 1.

N is een (deel)graaf met minstens r(K, S - 1) knooppunten. Dus die bevat OF een kliek met grootte K OF een onafhankelijke set met grootte S - 1.
Als je P toevoegt aan N dan krijg je een graaf met OF een kliek van grootte K (die was er als) OF een onafhankelijke set van S, immers P grenst niet aan N, die is erbij gekomen.

mogelijkheid 2.

W is een (deel)graaf met minstens r(K - 1, S) knooppunten. Dus die bevat OF een kliek met grootte K - 1 OF een onafhankelijke set met grootte S.
Als je P toevoegt aan W dan krijg je een graaf met OF een kliek van grootte K (P is erbij gekomen) OF een onafhankelijke set van S (die was er al)

In beide gevallen krijg je een kliek van K of een onafhankelijke set van S.
Dus in een graaf met r(K, S - 1) + r(K - 1, S) knooppunten is er altijd een kliek van K of een onafhankelijke set van S, dus r(K, S) ≤ r(K, S - 1) + r(K - 1, S)

■

Speciaal geval.
Als r(K, S - 1) en r(K - 1, S) beiden even zijn, neem dan een graaf G met r(K, S - 1) + r(K - 1, S) - 1 knooppunten.
Die heeft een oneven aantal knooppunten, dus er moet een knooppunt zijn met even graad (stelling uit deze eerdere les). Kies dat punt als P.
Dan kan P niet aan precies r(K, S - 1) - 1 of aan r(K - 1, S) - 1 knooppunten grenzen (oneven).
Met precies hetzelfde bewijs als hierboven komt dat erop neer dat het ≤ teken in de stelling dan vervangen mag worden door een < teken.

En nu zijn wiskundigen al bijna een eeuw bezig afschattingen van de Ramseygetallen te vinden.
Nog steeds..... Ze hebben kennelijk veel vrije zondagmiddagen....
Met deze recusierelatie kun je vaak een bovengrens voor r vinden.
Een ondergrens is natuurlijk het mooist te vinden door gewoon een graaf te tekenen zonder rode of groene K_n zoals hierboven bij r(3, 3) gebeurde.

Vooruit; we doen er nog eentje. Ik ben vrij en het is zondagmiddag...

Het bewijs dat r(4, 3) = 9

r(3, 3) = 6 (zie boven) en r(4, 2) = 4 (opgave 2)
Pas de ongelijkheid toe. Je mag het < teken gebruiken omdat beide getallen even zijn (het speciale geval hier vlak boven)
r(4, 3) < r(3, 3) + r(4, 3) = 6 + 4 = 10
Dus r(4, 3) ≤ 9. Daar hebben we al een bovengrens.

Voor de ondergrens zoeken we dus een graaf met 8 knooppunten, die gekleurd wordt met twee kleuren, en waar geen K₃ of K₄ in één kleur te vinden is.

Nou: daar is íe al:

Leg de rode en groene grafen over elkaar. Voilá!

Stelling van Schur.
- een leuke toepassing, en een uitbreiding gratis erbij!-

Door de Ramsey-getallen te zien als kleuringen van een volledige graaf in twee kleuren (rood-groen) komt natuurlijk meteen een algemener geval tevoorschijn, namelijk:

De vraag wordt dan: "Bij maximaal hoeveel knooppunten kun je de verbindingslijnen van een graaf met 2, 3, 4, .... kleuren kleuren?"

OPGAVEN

1.	Toon aan dat r(1, S) = r(K, 1) = 1

2.	Toon aan dat r(2, S) = S en r(K, 2) = K

3.	Toon aan dat er in K₆, bij kleuring met rood en groen, altijd TWEE driehoeken te vinden zijn die helmaal rood of helemaal groen zijn.