2WO12: Optimalisering in Netwerken

2WO12: Optimalisering in Netwerken Leo van Iersel Technische Universiteit Eindhoven (TU/E) en Centrum Wiskunde & Informatica (CWI)

10 en 13 februari 2014

http://homepages.cwi.nl/~iersel/2WO12/ [email protected]

Leo van Iersel (TUE/CWI)

2WO12: Optimalisering in Netwerken


1 / 40

Overzicht Lecture 1: (behandeld) grafen Euler tour Hamilton circuit toepassingen (fylogenetische bomen en de Bruijn rijen) Lecture 2: (vandaag) kleuren van de punten van een graaf kleuren van landkaarten planaire grafen kleuren van de lijnen van een graaf




2 / 40

Definitie Een k-(punt)kleuring van een graaf G = (V , E ) is een functie f : V → {1, 2, . . . , k} zodanig dat voor elk lijn {u, v } ∈ E geldt dat f (u) 6= f (v ).

Definitie Het (punt)kleurgetal (chromatic number) χ(G ) is de kleinste k ∈ N waarvoor G een k-kleuring heeft. Als G een k-kleuring heeft dan heet G k-kleurbaar.




3 / 40

Voorbeeld De onderstaande graaf is 3-kleurbaar, dus χ(G ) ≤ 3.




4 / 40

Vraag Wat is het kleurgetal van een pad?

Vraag Wat is het kleurgetal van Kn ?

Vraag Wat is het kleurgetal van een even circuit?

Vraag Wat is het kleurgetal van een oneven circuit?




5 / 40

χ(G ) ≤ k bewijs je door een correcte k-kleuring te geven χ(G ) ≥ k bewijs je met een ad hoc argument (b.v. een deelgraaf met een bekend kleurgetal)




6 / 40

Vraag Wat is het kleurgetal van de onderstaande graaf?




7 / 40





8 / 40

Vraag Wat is het kleurgetal van de Petersen graaf?

Petersen graaf Leo van Iersel (TUE/CWI)



9 / 40

Vraag Wat is het kleurgetal van een bipartiete graaf?

Stelling Gegeven een graaf G , zijn de volgende uitspraken equivalent: 1

G is bipartiet

2

G is 2-kleurbaar

3

G bevat geen circuits van oneven lengte




10 / 40

Definitie ∆(G ) is de maximale graad in graaf G

Opgave (2.9) Bewijs dat voor elke graaf G geldt χ(G ) ≤ ∆(G ) + 1

Opgave (2.10) Geef grafen G waarvoor χ(G ) = ∆(G ) + 1

Stelling (Brook) Voor elke samenhangende graaf G geldt χ(G ) ≤ ∆(G ) tenzij G een volledige graaf of een oneven circuit is. Leo van Iersel (TUE/CWI)



11 / 40

Definitie Een clique in een graaf is een verzameling punten die paarsgewijs buren zijn.

Definitie Het cliquegetal ω(G ) is de cardinaliteit van de grootste clique in G .

Voorbeeld In de onderstaande graaf G zijn {a, b, c} en {a, c, d} cliques. Er geldt ω(G ) = 3 (en χ(G ) = 3).

b a c d Leo van Iersel (TUE/CWI)



12 / 40

Stelling Voor elke graaf G geldt ω(G ) ≤ χ(G ).

Vraag Kan χ(G ) veel groter zijn dan ω(G )?




13 / 40





14 / 40

Stelling (Mycielski) Voor elke k ∈ N met k ≥ 2 is er een graaf G met ω(G ) = 2 en χ(G ) = k. De Mycielskian van een graaf G met punten v1 , v2 , . . . , vn krijg je als volgt: voeg punten u1 , u2 , . . . , un en w toe verbind ui met w , voor i = 1, . . . , n verbind ui met alle buren van vi (in G ), voor i = 1, . . . , n

Lemma (Mycielski) Voor de Mycielskian G 0 van een graaf G geldt (i) χ(G ) = k =⇒ χ(G 0 ) = k + 1 (ii) als G geen driehoeken bevat dan bevat G 0 ook geen driehoeken. De stelling van Mycielski volgt direct uit dit lemma. Leo van Iersel (TUE/CWI)



15 / 40

Definitie Een coclique (of independent set) in een graaf is een verzameling punten die paarsgewijs niet verbonden zijn. In een kleuring van een graaf zijn de punten van één kleur een coclique in de graaf

Voorbeeld In de onderstaande graaf vormen de blauwe punten een coclique.




16 / 40

Vraag Hoeveel punten heeft een grootste coclique in de onderstaande graaf? En een grootste clique?




17 / 40

Vraag Hoeveel kleuren heb je nodig om de kaart van de VS te kleuren, zodanig dat buurstaten verschillende kleuren krijgen?




18 / 40

Antwoord Vier kleuren zijn genoeg.

Vraag Kun je elke kaart met vier kleuren kleuren? Leo van Iersel (TUE/CWI)



19 / 40

Formuleer als grafen-probleem door als volgt een graaf te maken: creëer een punt voor elk gebied creëer een lijn tussen twee punten als de bijbehorende gebieden een grens delen.




20 / 40

Definitie Een graaf is planair als hij in het platte vlak kan worden getekend zodanig dat lijnen elkaar niet snijden.

Definitie Een onderverdeling (subdivision) van een graaf G is een graaf G 0 die uit G verkregen kan worden door elke lijn {u, v } te vervangen door een pad {u, w1 , w2 , . . . , wk , v } met k ≥ 0. (Als k = 0 dan verandert er aan die lijn dus niets.)

Stelling (Kuratowski) Een graaf G is planair dan en slechts dan als G geen deelgraaf heeft die een onderverdeling is van K5 of van K3,3 .




21 / 40

Definitie Een embedding is een tekening van een graaf in het platte vlak.

Definitie Een planaire embedding is een embedding waarin lijnen elkaar niet snijden.

Definitie Een planaire embedding van een planaire graaf verdeelt het platte vlak in gebieden. Deze gebieden worden facetten genoemd.

Stelling (Euler) Voor een planaire embedding van een samenhangende planaire graaf met n ≥ 1 punten, m lijnen en f facetten geldt n+f =m+2 Leo van Iersel (TUE/CWI)



22 / 40

Stelling (Euler) Voor een planaire embedding van een samenhangende planaire graaf met n ≥ 1 punten, m lijnen en f facetten geldt n+f =m+2

Voorbeeld Een niet-planaire en een planaire embedding van K2,3 . De planaire embedding heeft drie facetten A, B en C .

n=5 m=6 f=3

A B C Leo van Iersel (TUE/CWI)



23 / 40

Dus het aantal facetten f van een planaire graaf is onafhankelijk van de gekozen embedding. f is niet gedefiniëerd voor niet-planaire grafen.

Lemma Als G een planaire graaf is met n punten, m ≥ 2 lijnen en f facetten, dan: (i) f ≤ 23 m (Opgave 2.24) (ii) m ≤ 3n − 6 (Opgave 2.25) (iii) is er een punt v met d(v ) ≤ 5 (Opgave 2.27) Het volgt uit (ii) dat K5 niet planair is.




24 / 40

Stelling (Vierkleurenstelling) Voor elke planaire graaf G geldt χ(G ) ≤ 4 Dus kan elke landkaart met vier kleuren gekleurd worden. Stelling bewezen door Appel en Haken (1976). Bewijs van 400 pagina’s plus checken van 1936 gevallen met de computer. Fouten in bewijs. Versimpeld bewijs door Robertson, Sanders, Seymour en Thomas (1996). Nog steeds met computer.

Stelling (Makkelijker te bewijzen) Voor elke planaire graaf G geldt χ(G ) ≤ 5 Leo van Iersel (TUE/CWI)



25 / 40

Lijnkleuringen Definitie Een k-lijnkleuring van een graaf G = (V , E ) is een functie f : E → {1, 2, . . . , k} zodanig dat voor elk twee lijnen e, e 0 met e 6= e 0 en e ∩ e 0 6= ∅ (d.w.z., die elkaar raken in een punt) geldt dat f (e) 6= f (e 0 ).

Definitie Het lijnkleurgetal χ0 (G ) is de kleinste k ∈ N waarvoor G een k-lijnkleuring heeft. Als G een k-lijnkleuring heeft dan heet G k-lijnkleurbaar. Leo van Iersel (TUE/CWI)



26 / 40

Voorbeeld De onderstaande graaf is 4-lijnkleurbaar

χ0 (G ) = 4 χ(G ) = 3 Leo van Iersel (TUE/CWI)



27 / 40

Vraag Wat is het lijnkleurgetal van een even en van een oneven circuit?




28 / 40

Vraag Wat is het lijnkleurgetal van K3,3 ?




29 / 40

Vraag Wat is het lijnkleurgetal van een kubus?




30 / 40

Vraag Wat is het lijnkleurgetal van de onderstaande graaf?




31 / 40

Definitie ∆(G ) is de maximale graad in G

Observatie Voor elke graaf G geldt χ0 (G ) ≥ ∆(G )

Stelling (Vizing) Voor elke graaf G geldt χ0 (G ) ≤ ∆(G ) + 1

Stelling (König) Voor elke bipartiete graaf G geldt χ0 (G ) = ∆(G ) Leo van Iersel (TUE/CWI)



32 / 40

Vraag Wat is het lijnkleurgetal van Kn als n even is?

0




33 / 40




34 / 40

Vraag Er zijn 5 spelers: a, b, c, d en e. Er zijn 10 teams: ab, ac, ad, ae, bc, bd, be, cd, ce, de. Een team mag niet twee keer op dezelfde dag spelen. Hoeveel dagen zijn er minimaal nodig om elk team tegen elk ander team te laten spelen?




35 / 40

Kneser Graph KG5,2

ab

de cd

ac

bd ce

ae be

bc ad




36 / 40

χ0 (KG7,3 ) = 4




37 / 40

Definitie Een matching in een graaf G = (V , E ) is een verzameling lijnen M ⊆ E zodanig dat voor elke twee e, e 0 ∈ M geldt dat e ∩ e 0 = ∅. In een lijnkleuring van een graaf vormen de lijnen met dezelfde kleur een matching.

Voorbeeld In elk van de onderstaande grafen vormen de blauwe lijnen een matching.




38 / 40

Lemma Als M en N twee matchings zijn in een graaf G = (V , E ), dan is elke component van de graaf (V , M ∪ N) een pad of een even circuit.

Voorbeeld De lijnen van de blauwe en rode matching vormen een pad en een even circuit.




39 / 40

Lemma Als M en N twee disjuncte matchings zijn in een graaf G = (V , E ) en |M| > |N|, dan bestaan er disjuncte matchings M 0 en N 0 in G met M ∪ N =M 0 ∪ N 0 |M 0 | =|M| − 1 |N 0 | =|N| + 1

Gevolg (Opgave 2.50) Als χ0 (G ) ≤ k dan is er een k-lijnkleuring van G zodanig dat elke kleur hoogstens één keer vaker voorkomt dan elke andere kleur.

Gevolg Als G = (V , E ) bipartiet is en k ≥ ∆(G ), dan is er een k-lijnkleuring van G waarin elke kleur b |Ek | c of d |Ek | e maal voorkomt. Leo van Iersel (TUE/CWI)



40 / 40

2WO12: Optimalisering in Netwerken

Recommend Documents