Természettudományi kar. szakdolgozat Matematika BSc Alkalmazott matematikus szakirány ELTE TTK

¨ tvo ¨ s Lora ńd Tudoma ńyegyetem Eo ńyi kar Term´ eszettudoma

´ th Marko ´ Horva

S´ıkgr´ afok polikromatikus sz´ınez´ ese szakdolgozat Matematika BSc Alkalmazott matematikus szakir´ any

˝: t´ emavezeto Bérczi Kristóf ELTE TTK Oper´ aci´ okutat´ asi Tanszék

2011

Tartalomjegyz´ ek K¨ osz¨ onetnyilv´ an´ıt´ as

iv

Bevezet˝ o

v

Fogalmak, jel¨ ol´ esek

vi

1. Soksz¨ ogek ´ es s´ıkgr´ afok lev´ ed´ ese

1

1.1. Chvátal terem˝or tétele . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2

1.2. S´ıkgr´ afok levédése . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5

2. S´ıkgr´ afok polikromatikus sz´ ama

6

2.1. Alsó és fels˝o becslés p(g)-re . . . . . . . . . . . . . . . . . . . . . . . . . . . .

7

2.1.1. A 2.1 Tétel bizony´ıtása az 1 ≤ g ≤ 4 esetre . . . . . . . . . . . . . . .

7

2.1.2. Lapok cs´ ucsfedése . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

8

2.1.3. Polikromatikus élsz´ınezés . . . . . . . . . . . . . . . . . . . . . . . . . 10 2.1.4. Az alsó becslés igazolása . . . . . . . . . . . . . . . . . . . . . . . . . . 11 2.1.5. A fels˝o becslés igazolása . . . . . . . . . . . . . . . . . . . . . . . . . . 12 2.2. Kapcsolat a védelmi problém´ akkal . . . . . . . . . . . . . . . . . . . . . . . . 13 2.3. Kapcsolat a Négysz´ın-tétellel . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 ¨ 2.4. Osszefoglal´ as, nyitott kérdések . . . . . . . . . . . . . . . . . . . . . . . . . . 16 3. Feloszt´ asok polikromatikus sz´ınez´ ese

17

3.1. Téglalap-feloszt´ asok polikromatikus sz´ınezései . . . . . . . . . . . . . . . . . . 18 3.1.1. Er˝ osen polikromatikus 4-sz´ınezés . . . . . . . . . . . . . . . . . . . . . 18 3.1.2. Guillotine-feloszt´ asok . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 ´ 3.2. Altal´ anos felosztások polikromatikus sz´ınezései . . . . . . . . . . . . . . . . . 21 3.2.1. Gyenge ´ altal´ anos polikromatikus 4-sz´ınezés . . . . . . . . . . . . . . . 21 3.2.2. Gyenge ´ altal´ anos polikromatikus 3- és 5-sz´ınezés . . . . . . . . . . . . 23 3.2.3. Er˝ os ´ altal´ anos polikromatikus 2- és 6-sz´ınezés . . . . . . . . . . . . . . 25 ¨ 3.3. Osszefoglal´ as, nyitott kérdések . . . . . . . . . . . . . . . . . . . . . . . . . . 27

ii

´ TARTALOMJEGYZEK

4. A polikromatikus sz´ınez´ es bonyolults´ aga

iii

28

4.1. A polikromatikus 2-sz´ınezés bonyolultsága . . . . . . . . . . . . . . . . . . . . 29 4.2. A polikromatikus 3-sz´ınezés bonyolultsága . . . . . . . . . . . . . . . . . . . . 30 4.3. A polikromatikus 4-sz´ınezés bonyolultsága . . . . . . . . . . . . . . . . . . . . 31 4.4. Egyéb eredmények, nyitott kérdések . . . . . . . . . . . . . . . . . . . . . . . 33 Irodalomjegyz´ ek

34

K¨ osz¨ onetnyilv´ an´ıt´ as Szeretnék ez´ uton is kösz¨ onetet mondani témavezet˝omnek, Bérczi Krist´ ofnak, hogy mindig szak´ıtott rám id˝ot, kérdéseimmel b´ atran fordulhattam hozz´ a, sok segédanyaggal és még t¨ obb hasznos tan´ accsal látott el. Kösz¨ onettel tartozom még csoporttársaimnak, bar´ ataimnak is, de legf˝ oképpen családomnak, amiért t´ amogatnak és seg´ıtik tanulmányaimat.

iv

Bevezet˝ o Szakdolgozatomban s´ıkgr´ afok polikromatikus sz´ınezésével foglalkozunk. A lehet˝o legtöbb sz´ınnel szeretnénk kisz´ınezni egy s´ıkgr´ af cs´ ucsait u ´ gy, hogy minden lap cs´ ucsai között felt˝ unj¨ on minden sz´ın. A legnagyobb számot, mellyel egy G s´ıkgr´ afnak létezik polikromatikus sz´ınezése, a G s´ıkgr´ af polikromatikus sz´ am´ anak nevezz¨ uk, és p(G)-vel jelölj¨ uk. Bármely s´ıkgr´ af polikromatikus sz´ am´ ara nyilvánvaló fels˝okorlát a legkisebb lapjának mérete, ´ıgy p(G)-t ennek f¨ uggvényében érdemes vizsgálnunk. Tekints¨ uk azokat a s´ıkgr´ afokat, melyek legkisebb lapja g méret˝ u, és jel¨ olje p(g) ezen s´ıkgr´ afok polikromatikus száma köz¨ ul a legkisebbet. Utóbbi pontos értéke már g = 5 esetén sem ismert, de érdemes megeml´ıteni, hogy a p(5) = 4 egyenl˝ oségb˝ ol következne a Négysz´ın-tétel. Miel˝ott rátérnénk a polikromatikus sz´ınezése vizsgálatára, az 1. fejezetben ismertetj¨ uk Victor Klee terem˝ or problém´ aj´ at és Chvátal klasszikus terem˝or tételét [12, 14]. A második szakaszban s´ıkgr´ afok levédési problém´ aj´ at vizsg´ aljuk [2]. A polikromatikus sz´ınezéssel való kapcsolatr´ ol a 2. fejezetben tesz¨ unk majd eml´ıtést. A 2. fejezet ¨ oleli fel a dolgozat egyik f˝o tém´ aj´ at. Alon és t´ arsai [1] eredményeit bemutatva a s´ıkgr´ afok polikromatikus sz´ am´ ara adunk alsó és fels˝o becslést a legkisebb lap méretének f¨ uggvényében. Az alsó becsléshez kisebb kitér˝oket tesz¨ unk k¨ ulönb¨ oz˝o algebrai, gráfelméleti problém´ ak felé, a fels˝o becslést pedig konstrukt´ıvan bizony´ıtjuk. A második nagyobb tém´ at a 3. fejezetben t´ argyaljuk. A s´ıkgr´ afok két speci´ alis osztályának, az a ´ltal´ anos feloszt´ asok és a téglalap-feloszt´ asok polikromatikus sz´ınezéseivel foglalkozunk [3, 6], de eml´ıtést tesz¨ unk a guillotine-feloszt´ asokr´ ol is [8, 10]. A felosztások sz´ınezésekor kib˝ov´ıtj¨ uk a polikromatikus sz´ınezés defin´ıciój´ at, és igazoljuk, hogy minden téglalap-feloszt´ asnak létezik er˝ osen polikromatikus 4-sz´ınezése. L´ atni fogjuk, hogy van olyan által´ anos felosztás melynek nincs gyenge a ´ltal´ anos polikromatikus 4-sz´ınezése, de minden által´ anos felosztásnak létezik gyenge a ´ltal´ anos polikromatikus 3- és 5-sz´ınezése, illetve er˝ os a ´ltal´ anos 2- és 6-sz´ınezése. Az utols´ o fejezetben a polikromatikus sz´ınezés bonyolultságát vizsgáljuk, melyben f˝oként [1] néhány fontos eredményét mutatjuk be, de [6] idevonatkozó részeit is megeml´ıtj¨ uk. Megmutatjuk, annak eld¨ ontése, hogy egy s´ıkgr´ af polikromatikusan k-sz´ınezhet˝o-e, triviális a k = 1 esetben, P-ben van a k = 2 esetben, és a k = 3, 4 esetekben a probléma N P-teljes.

v

Fogalmak, jel¨ ol´ esek Egy gr´ afot s´ıkbarajzolhat´ onak nevez¨ unk, ha lerajzolhat´ o a s´ıkba u ´ gy, hogy élei nem metszik egym´ ast. S´ıkgr´ af alatt egy s´ıkbarajzol´ asával adott s´ıkbarajzolhat´ o gráfot ért¨ unk. Egy s´ıkgr´ afot egyszer˝ unek nevez¨ unk, ha nem tartalmaz p´ arhuzamos éleket és hurkot. Jelölje V (G), E(G), F (G) rendre a G s´ıkgr´ af cs´ ucsainak, éleinek, lapjainak halmazát. Egy lap ker¨ uletén tal´ alhat´ o cs´ ucsot a lap cs´ ucs´ anak nevezz¨ uk, egy f ∈ F (G) lap cs´ ucsainak halmazát pedig Vf -el jel¨ olj¨ uk. Egy lap méretén a cs´ ucsai szám´ at értj¨ uk. A G gr´ af cs´ ucsainak k-sz´ınezésén egy χ : V (G) → {1, . . . , k} f¨ uggvényt ért¨ unk, és a sz´ınezést j´ o k-sz´ınezésnek nevezz¨ uk, ha nincs monokromatikus él, azaz minden uv ∈ E(G) élre χ(u) 6= χ(v). A Négysz´ın-tétel szerint minden s´ıkgr´ afnak létezik jó 4-sz´ınezése. Hasonlóan, a G gr´ af éleinek k-sz´ınezésén egy ξ : E(G) → {1, . . . , k} f¨ uggvényt ért¨ unk, és a sz´ınezést j´ o k-élsz´ınezésnek nevezz¨ uk, ha minden u ∈ V (G) cs´ ucsra és minden uv, uw élre χ(uv) 6= χ(uw). Egy G gr´ af v cs´ ucs´ anak foksz´ am´ an a v végpont´ u élek szám´ at értj¨ uk, és dG (v)-vel jelölj¨ uk. A v ∈ V (G) cs´ ucs foksz´ am´ at egyszer˝ uen d(v)-vel is jelölhetj¨ uk, ha világos, hogy a G-beli fok´ aról van sz´ o. A G gr´ af cs´ ucsai foksz´ am´ anak minimumát δ(G)-vel, maximumát ∆(G)-vel jelölj¨ uk. Irány´ıtott D gr´ af esetén a v ∈ V (D) cs´ ucsb´ ol ki-, illetve belép˝o élek szám´ at d+ (D)vel illetve d− (G)-vel jel¨ olj¨ uk. Tekints¨ uk a G gr´ af cs´ ucsainak egy V 0 részhalmaz´ at. G[V 0 ]-vel jelölj¨ uk G, V 0 által fesz´ıtett részgr´ afj´ at. Tekints¨ uk a G gr´ af cs´ ucsainak egy X halmazát. Ekkor az (X, V (G)\X) halmazpárt G v´ ag´ as´ anak nevezz¨ uk, és egy uv élt v´ ag´ oélnek mondunk, ha u ∈ X és v ∈ V (G)\X. Egy gr´ afot p´ arosnak nevez¨ unk, ha cs´ ucsai két osztályba sorolhatóak u ´ gy, hogy az egy osztályon bel¨ uli cs´ ucsok nincsenek éllel összek¨ otve. Péld´ aul egy tetsz˝ oleges gráf valamely vágása és a vágóélek p´ aros gr´ afot adnak.

vi

1. fejezet

Soksz¨ ogek ´ es s´ıkgr´ afok lev´ ed´ ese Az alábbi felvezet˝o fejezetben megismerked¨ unk Victor Klee terem˝or problém´ aj´ aval és belátjuk V´ aclav Chv´ atal klasszikus terem˝or tételét. Ezek után s´ıkgr´ afok levédésével foglalkozunk, mely a polikromatikus sz´ınezéssel is kapcsolatban áll. Err˝ol majd a 2. Fejezetben lesz szó. A való életb˝ ol sz´ armazó terem˝ or probléma a következ˝o. Egy képtár termeibe szeretnénk a lehet˝ o legkevesebb biztonsági ˝ ort elhelyezni u ´ gy, hogy egy¨ utt az egész képtárat belássák. A problém´ at közel´ıts¨ uk meg u ´ gy, hogy a képtár alaprajza egy egyszer˝ u sokszög, a biztonsági ˝ or¨ ok pedig a sokszög pontjai. Azt mondjuk, hogy a P sokszög pontjainak egy S halmaza levédi P -t, ha minden p ∈ P ponthoz létezik olyan s ∈ S pont, hogy a ps szakasz teljes egészében P -ben helyezkedik el. A terem˝or problém´ anak számos változata van, a továbbiakban Victor Klee terem˝or problém´ aj´ aval foglalkozunk. Klee kérdése a következ˝o volt: Adott egy P egyszer˝ u soksz¨ og. Legkevesebb h´ any o ˝rrel tudjuk levédeni P -t u ´gy, hogy az o ˝r¨ oket kiz´ ar´ olag P cs´ ucsaiba helyezhetj¨ uk el?

1

2

1.1. Chvátal terem˝or tétele

1.1.

Chv´ atal terem˝ or t´ etele

V´ aclav Chv´ atal 1975-ben megmutatta, hogy egy n cs´ ucs´ u sokszög esetén

jnk

˝or mindig elég, 3 és néha sz¨ ukséges is, ahhoz hogy levédj¨ uk a sokszöget. 1978-ban Steve Fisk [5] adott egy rövid bizony´ıt´ ast Chvátal tételére. A bizony´ıtásaik abban megegyeztek, hogy mindketten a sokszög h´ aromsz¨ ogelésével közel´ıtették meg a problém´ at. Egy egyszer˝ u sokszög h´ aromsz¨ ogelésén azt értj¨ uk, hogy a szoksz¨ oget egym´ ast nem metsz˝o átl´ ok beh´ uzás´ aval h´ aromsz¨ ogekre osztjuk. ´ ıt´ 1.1. All´ as. Minden egyszer˝ u soksz¨ ognek létezik h´ aromsz¨ ogelése. Bizony´ıt´ as: Teljes indukci´ ot alkalmazunk. Az áll´ıtás n = 3 cs´ ucs´ u sokszögre nyilván teljes¨ ul. Tegy¨ uk fel, hogy n ≥ 4, és n-nél kevesebb cs´ ucs´ u sokszögre már beláttuk az áll´ıtást. Tekints¨ uk az n cs´ ucs´ u P sokszög egy konvex cs´ ucs´ at (v2 ), azaz egy olyan cs´ ucsot, melyhez konvex bels˝o sz¨ og tartozik. Legyenek v1 és v3 a v2 szomszédai. Ha a v1 v3 átl´ o benne van P -ben, akkor beh´ uzás´ aval P -t felbontottuk P1 és P2 egyszer˝ u sokszögekre, melyeknek sz¨ ukségképpen n-nél kevesebb cs´ ucsuk van, teh´ at létezik h´ aromsz¨ ogelés¨ uk, és egy¨ utt P h´ aromsz¨ ogelését adják. Egy példa látható az 1.1 (a) ábr´ an.

1.1. ´ abra. Soksz¨ ogek h´ aromsz¨ ogelése: az els˝o átl´ o beh´ uzása

Ha a v1 v3 ´ atl´ o nincs benne P -ben, akkor a v1 v2 v3 z´ art h´ aromsz¨ og tartalmazza P legal´ abb egy cs´ ucs´ at, mely k¨ ulönb¨ ozik az el˝ oz˝oekt˝ol. Legyen ezek köz¨ ul x az a cs´ ucs, mely legtávolabb ol, azaz legk¨ ozelebb van v2 -höz v1 v3 egyenes normálisa szerint. Ekkor a van v1 v3 egyenest˝ v2 x átl´ o beh´ uzás´ aval ismét két egyszer˝ u sokszögre osztottuk P -t, melyek cs´ ucssz´ ama n-nél kisebb, teh´ at ismét megkaphatjuk P egy h´ aromsz¨ ogelését. Egy példa látható az 1.1 (b) ábr´ an. Egy h´ aromsz¨ ogelés minden h´ aromsz¨ ogében vegy¨ unk fel egy pontot. Két pontot pontosan akkor köss¨ unk ¨ ossze, ha a nekik megfelel˝o h´ aromsz¨ ogeknek van közös oldaluk. Az ´ıgy kapott gráfot a h´ aromsz¨ ogelés du´ alis gr´ afj´ anak nevezz¨ uk.

3

1.1. Chvátal terem˝or tétele ´ ıt´ 1.2. All´ as. B´ armely egyszer˝ u soksz¨ og h´ aromsz¨ ogelésének du´ alis gr´ afja egy fa.

Bizony´ıt´ as: A du´ alis gr´ af ¨ osszef¨ ugg˝o a konstrukciója miatt. Tegy¨ uk fel indirekt, hogy létezik benne kör. Ez azt jelentené, hogy vagy van egy izolált pont P belsejében, vagy P ”lyukas”. Ezek egyike sem lehetséges, ugyanis P egyszer˝ u.

1.1. T´ etel (Chv´ atal).

jnk

3 egyszer˝ u soksz¨ oget levédj¨ unk.

o ˝r mindig elég, és néha sz¨ ukséges is ahhoz, hogy egy n cs´ ucs´ u

Bizony´ıt´ as: Legyen adott egy P egyszer˝ u sokszög. H´ aromsz¨ ogelj¨ uk P -t (n − 3 átl´ o beh´ uz´ asával). Legyen ez a h´ aromsz¨ ogelés T . Sz´ınezz¨ uk ki T tetsz˝ oleges h´ aromsz¨ ogének cs´ ucsait k¨ ulönb¨ oz˝o ({1, 2, 3}) sz´ınekkel. Ezut´ an tekints¨ uk az ezzel szomszédos h´ aromsz¨ ogeket. Ezeknek pontosan két cs´ ucsuk sz´ınezett, ráadásul k¨ ulönb¨ oz˝o sz´ın˝ uek, ezért a sz´ınezetlen cs´ ucsot sz´ınezz¨ uk ki a harmadik sz´ınnel. Mivel T du´ alis gráfja fa, ezért minden lépésben olyan h´ aromsz¨ oget sz´ınez¨ unk, melynek pontosan két cs´ ucsa sz´ınezett, és k¨ ulönb¨ oz˝o sz´ın˝ uek. Ezért ezt az elj´ ar´ ast folytatva megkapjuk T egy sz´ınezését, melynél b´ armely h´ aromsz¨ og cs´ ucsai k¨ ulönb¨ oz˝o sz´ın˝ uek. V´ alasszuk ki aztja sz´ ınt, melyet a legkevesebbszer használtunk. Egyrészt nk ez a sz´ am nyilvánval´ oan legfeljebb , másrészt ha az ilyen sz´ın˝ u cs´ ucsokba helyezz¨ uk el 3 az ˝oröket, akkor lefogj´ ak P -t, hiszen egy h´ aromsz¨ og cs´ ucs´ aban lév˝ o ˝or levédi a h´ aromsz¨ oget, és minden h´ aromsz¨ og valamelyik cs´ ucs´ aba helyezt¨ unk ˝ort.

1.2. ´ abra. (a) Egy sokszög h´ aromsz¨ ogelése és sz´ınezése; (b) A ”fés˝ u” sokszög

Az 1.2 (a) ´ abr´ an látható egy sokszög h´ aromsz¨ ogelése és sz´ınezése. A 1.2 (b) ábr´ an pedig egy n = 3m cs´ ucs´ u sokszög (m fog´ u fés˝ u) látható melynek levédéséhez legal´ abb m ˝or sz¨ ukséges.

1.1. Megjegyz´ es. Az

jnk

érték félrevezethet˝ o lehet, ha u ´gy gondoljuk, hogy a soksz¨ og min3 den harmadik cs´ ucs´ aba egy o ˝rt a ´ll´ıtva levédhet˝ o a soksz¨ og. Erre egy ellenpéld´ at l´ athatunk az 1.3 a ´br´ an.

1.1. Chvátal terem˝or tétele

4

1.3. ábra. Ha a sokszög minden harmadik cs´ ucs´ aba tesz¨ unk ˝ort, akkor az x1 , x2 , x3 pontok valamelyike nem lesz védve. 1.2. Megjegyz´ es. Egy soksz¨ oget ortogon´ alisnak nevez¨ unk, ha szomszédos oldalai mer˝ olegesek egym´ asra. Azért érdekes az ilyen soksz¨ ogeket vizsg´ alni, mert a val´ os´ agban az ép¨ uletek a ´ltal´ aban ortogon´ alisak. Kahn, ucs´ u ortoj n kKlawe és Kleitman [9] bebizony´ıtotta, hogy egy n cs´ o ˝r mindig elég, és néha sz¨ ukséges is. A bizony´ıt´ as alap¨ otlete, gon´ alis soksz¨ og levédéséhez 4 hogy a soksz¨ oget a ´tl´ ok beh´ uz´ as´ aval konvex négysz¨ ogekre bontjuk fel, majd az a ´ltal´ anos esethez hasonl´ oan (de most) 4-sz´ınezz¨ uk, és a legkevesebbszer haszn´ alt sz´ınnel sz´ınezett cs´ ucsokba helyezve az o ˝r¨ oket levédj¨ uk a soksz¨ oget.

5

1.2. S´ıkgr´ afok levédése

1.2.

S´ıkgr´ afok lev´ ed´ ese

A sokszögek levédéséhez hasonl´ oan vizsgálhatjuk 3-dimenzi´ os fel¨ uletek, s´ıkgr´ afok levédését is. Bose és t´ arsai [2] h´ aromsz¨ ogelt fel¨ uletek levédésvel foglalkoztak, ezen eredmények köz¨ ul ismertet¨ unk most néhányat.

El˝ osz¨ or is vezess¨ uk be a h´ aromsz¨ ogelt fel¨ uletet fogalmát.

H´ aromsz¨ ogelt fel¨ uletnek nevez¨ unk egy olyan soklap´ u fel¨ uletet, melynek minden oldallapja egy h´ aromsz¨ oglap. Legyenek T h´ aromsz¨ ogelt fel¨ ulet cs´ ucsai V = {v1 , . . . , vn } térbeli pontok, ahol vi -t 3 koordin´ atáj´ aval (xi , yi , zi ) jellemezz¨ uk. Feltehet˝o, hogy zi minden i-re nemnegat´ıv, teh´ at ha az X − Y s´ıkra mint tengerszintre gondolunk, a T fel¨ ulet egyetlen pontja sincs a tengerszint alatt. Tegy¨ uk fel, hogy a h´ aromsz¨ ogelt fel¨ ulet¨ unk olyan, hogy minden f¨ ugg˝ oleges (z tengellyel p´ arhuzamos) egyenessel a metszete (ha metszik egym´ ast) egyetlen pont. Ekkor minden vi pontot mer˝olegesen levet´ıtve az X − Y s´ıkra egy n cs´ ucs´ u h´ aromsz¨ ogelt s´ıkgr´ afot kapunk. A továbbiakban ezért s´ıkgr´ afok levédésével foglalkozunk. Egy s´ıkgr´ af v cs´ ucs´ aba helyezett ˝ or azokat az lapokat védi le, melyeknek a v cs´ ucsa. A k¨ uls˝ o lap levédését˝ol eltekinthet¨ unk. jnk

o ˝r mindig elég, és néha sz¨ ukséges is ahhoz, hogy egy n 2 cs´ ucs´ u egyszer˝ u s´ıkgr´ afot levédj¨ unk, ha az o ˝r¨ oket kiz´ ar´ olag a cs´ ucsokba helyezhetj¨ uk. 1.2. T´ etel (Bose et al. [2]).

A tételt most nem bizony´ıtjuk, de kés˝obb, más formában mégis látni fogjuk. Az 1.4 ábr´ an látható 7 cs´ ucs´ u S1 s´ıkgr´ afr´ ol megmutathat´ o, hogy levédéséhez legal´ abb 3 ˝or sz¨ ukséges. S2 s´ıkgr´ afot kész´ıts¨ uk el u ´ gy S1 -b˝ol, hogy S1 egy péld´ anyát be´ agyazzuk S1 sz´ınezett h´ arom´ szögébe. Altal´ aban Sk−1 egy péld´ anyát ágyazzuk be S1 sz´ınezett h´ aromsz¨ ogébe. Ekkor belátható, hogy a 4k + 3 cs´ ucs´ u Sk s´ıkgr´ af levédéséhez legal´ abb 2k + 1 ˝or sz¨ ukséges, és ha ennyi ˝ orrel levédj¨ uk, akkor legfeljebb 1 ˝or lehet a k¨ uls˝ o lapon.

1.4. ábra. Az S1 gráf

2. fejezet

S´ıkgr´ afok polikromatikus sz´ ama Tekints¨ uk a G s´ıkgr´ af egy χ : V (G) → {1, . . . , k} k-sz´ınezését. Egy ilyen sz´ınezés esetén azt mondjuk, hogy egy f ∈ F (G) lap polikromatikusan sz´ınezett, ha mind a k sz´ın megtalálható f cs´ ucsai között. A gr´ af sz´ınezését akkor mondjuk polikromatikusnak, ha minden lapja (beleértve a k¨ uls˝ ot is) polikromatikusan sz´ınezett: ∀ f ∈ F (G) ∀ i ∈ {1, . . . , k} ∃ v ∈ Vf : χ(v) = i. G polikromatikus sz´ am´ an azt a legnagyobb k számot értj¨ uk, melyre létezik G-nek polikromatikus k-sz´ınezése. G polikromatikus szám´ at p(G)-vel jelölj¨ uk. p(G)-re egy nyilvánvaló fels˝okorlát G legkisebb lapj´ anak mérete, ´ıgy p(G)-t ez utóbbi f¨ uggvényében érdemes vizsg´ alni. Jelölje g(G) a G gr´ af lapjai köz¨ ul a legkisebbnek a méretét. Vezess¨ uk be a következ˝o jelölést: p(g) := min{p(G)|G s´ıkgr´ af, g(G) = g}. A defin´ıciókb´ ol azonnal következik, hogy tetsz˝ oleges G s´ıkgr´ afra p(g(G)) ≤ p(G) ≤ g(G). Tegy¨ uk fel, hogy a G s´ıkgr´ af tartalmaz hurkot valamely v cs´ ucs kör¨ ul. Legyen G1 a hurkon bel¨ uli, G2 a hurkon k´ıv˝ uli gr´ af (ezalatt mindkét esetben a v-t tartalmaz´ o, de a hurkot nem tartalmaz´ o gr´ afot értj¨ uk). Ekkor p(G) = min{p(G1 ), p(G2 )} és g(G) = min{g(G1 ), g(G2 )}. Tehát p(G) b´ armely alsó becslése hurkot nem tartalmaz´ o G-re igaz hurkot tartalmaz´ ora is. Továbbá b´ armely hurkot tartalmaz´ o konstrukció a fels˝o becslésre hurok nélk¨ ulivé tehet˝o. A továbbiakban teh´ at kizár´ olag hurok nélk¨ uli s´ıkgr´ afokat vizsgálunk. A fejezetben alsó és fels˝o becslést adunk p(g)-re, és megmutatjuk a polikromatikus sz´ınezés kapcsolatát a védelmi problém´ akkal és a Négysz´ın-tétellel.

6

2.1. Alsó és fels˝o becslés p(g)-re

2.1.

7

Als´ o´ es fels˝ o becsl´ es p(g)-re

A következ˝okben alsó és fels˝o becslést adunk p(g)-re. Az alsó becsléshez k¨ ulönb¨ oz˝o algebrai, gráfelméleti tételeket fogunk felhasználni, a fels˝o becslést pedig konstrukt´ıvan igazoljuk. 2.1. T´ etel. p(1) = p(2) = 1, p(3) = p(4) = 2, és g ≥ 3 esetén 3g − 5 3g + 1 ≤ p(g) ≤ . 4 4 3g + 1 3g − 5 ,..., intervallum 2 vagy 3 egész sz´ amot tartal2.1. Megjegyz´ es. A 4 4 maz, ´ıgy a becslés p(g) lehetséges értékeit 2 vagy 3 sz´ amra korl´ atozza. A pontos érték viszont m´ ar g = 5 esetén sem ismert.

2.1.1.

A 2.1 T´ etel bizony´ıt´ asa az 1 ≤ g ≤ 4 esetre

2.1. Lemma. p(G) ≥ 2 minden olyan s´ıkgr´ afra, melyre g(G) ≥ 3. Bizony´ıt´ as: Tekints¨ uk G egy h´ aromsz¨ ogelését. Az ´ıgy kapott G0 s´ıkgr´ af minden bels˝o lapja 3 méret˝ u. Tekints¨ uk G0 cs´ ucsainak jó 4-sz´ınezését ({1, 2, 3, 4} sz´ınekkel) mely a Négysz´ıntétel alapj´ an létezik. Ekkor G0 b´ armely bels˝o lapján pontosan 3 sz´ın t˝ unik fel. A jó sz´ınezés miatt a k¨ uls˝ o lapon is legal´ abb két sz´ın felt˝ unik, feltehetj¨ uk hogy ezek az 1-es és 2-es sz´ınek. Ezut´ an a 3-as sz´ınnel sz´ınezett cs´ ucsokat sz´ınezz¨ uk át 1-es sz´ın˝ ure, a 4-es sz´ınnel sz´ınezett 0 ´ cs´ ucsokat pedig sz´ınezz¨ uk ´ at 2-es sz´ın˝ ure. Igy G 2-sz´ınezett, és b´ armely lapján felt˝ unik mindkét sz´ın, teh´ at G0 -nek egy polikromatikus 2-sz´ınezését kaptuk. Ha a h´ aromsz¨ ogeléshez felvett éleket elt¨ or¨ olj¨ uk, akkor megkapjuk G polikromatikus 2-sz´ınezését is. Ezek után térj¨ unk rá a 2.1 Tétel egyszer˝ ubb eseteire. Nyilv´ anvaló, hogy minden s´ıkgr´ af polikromatikusan 1-sz´ınezhet˝o, ´ıgy b´ armely g(G) = g esetén p(g) ≥ 1. Ha g(G) = 1, akkor G-nek csup´ an egyetlen cs´ ucsa van, ´ıgy p(1) ≤ 1. Ha g(G) = 2, akkor G vagy tartalmaz 2 hossz´ u kört, vagy 2 pontból áll. Az áll´ıtás igazol´ asához elég mutatni egy olyan G0 gráfot, melyre g(G0 ) = 2 és p(G0 ) = 1, ugyanis ebb˝ol p(2) ≤ 1 következik. Egy ilyen G0 gráf látható a 2.1 (a) ábr´ an. A 2.1 Lemma alapj´ an g(G) ≥ 3 esetén p(G) ≥ 2. M´ asrészt tekints¨ uk a K4 egy s´ıkbarajzol´ asát (2.1 (b) ´ abra), melyre egyszer˝ uen meggondolható, hogy p(K4 ) = 2. Ebb˝ol p(3) = 2.

2.1. ´ abra. (a) G0 gr´ af: g(G0 ) = 2, p(G0 ) = 1; (b) K4 : g(K4 ) = 3, p(K4 ) = 2


8

A g = 4 esethez tekints¨ uk a következ˝o konstrukciót. Induljunk ki a 2.2 (a) ábr´ an látható G4B b´ azisgr´ afb´ ol, majd kész´ıts¨ uk el a 2.2 (b) ábr´ an látható G gráfot, ahol a sat´ırozott vi vj élek a b´ azisgr´ af egy-egy péld´ anyát jel¨ olik u ´ gy, hogy a vi , vj cs´ ucsok, az x, y cs´ ucsoknak felelnek meg. Ha G-nek létezik polikromatikus 3-sz´ınezése, akkor egy ilyen sz´ınezés esetén a G-beli b´ azisgr´ afok is polikromatikusan sz´ınezettek, kivéve a k¨ uls˝ o lapjukat, hiszen azok nem lapjai G-nek. Nyilv´ anval´ o, hogy G4B b´ armely polikromatikus 3-sz´ınezése esetén - melyben tehát a k¨ uls˝ o lap polikromatikus sz´ınezését nem követelj¨ uk meg - az x és y pontok k¨ ulönb¨ oz˝o sz´ın˝ uek, ugyanis ellenkez˝o esetben a gr´ af sz´ınezett lapja nem lenne polikromatikus. Ekkor az el˝obb le´ırtak miatt v1 , v2 , v3 , v4 cs´ ucsok sz´ıne p´ aronként k¨ ulönb¨ oz˝o. M´ asrészr˝ol G részgr´ afként tartalmaz v1 , v2 , v3 , v4 cs´ ucs´ u K4 -t, melyr˝ ol tudjuk, hogy nem jól 3-sz´ınezhet˝o. Ebb˝ol az ellentmond´ asb´ ol p(G) < 3, és ´ıgy p(4) = 2.

2.2. ´ abra. (a) G4B b´ azisgráf, (b) G gráf

2.1.2.

Lapok cs´ ucsfed´ ese

2.2. Lemma. Legyen G egy s´ıkgr´ af, ∅ = 6 F 0 ⊆ F (G), ∅ = 6 V 0 ⊆ V (G), és i(V 0 , F 0 ) jel¨ olje F 0 és V 0 k¨ ozti fedések sz´ am´ at, azaz azon (v, f ) p´ arok sz´ am´ at, melyekre v ∈ V 0 , f ∈ F 0 , és v cs´ ucsa f -nek. Ekkor i(V 0 , F 0 ) ≤ 2|F 0 | + 2|V 0 | − 3. Bizony´ıt´ as: Konstru´ aljunk egy H szomszéds´ agi gráfot a V 0 -beli cs´ ucsok és az F 0 -beli lapok között a következ˝ok szerint. V (H) = F 0 ∪ V 0 , és f v pontosan akkor él H-ban, ha f ∈ F 0 , v ∈ V 0 és G-ben v cs´ ucsa az f lapnak. Könnyen látszik, hogy H egyszer˝ u, p´ aros s´ıkgr´ af. S˝ ot, i(V 0 , F 0 ) = |E(H)|. H-ra mint egyszer˝ u, h´ aromsz¨ ogmentes s´ıkgr´ afra fel´ırva az Euler-formulát az alábbi egyenl˝otlenséget kapjuk: |E(H)| ≤ 2V (H) − 4 feltéve, hogy H-nak legal´ abb 3 cs´ ucsa van. Ebb˝ol azt kapjuk, hogy i(V 0 , F 0 ) ≤ 2(|V 0 | + |F 0 |) − 4. M´ asrészt, ha H-nak csup´ an két cs´ ucsa, és egy éle van, akkor i(V 0 , F 0 ) = 1 = 2(|V 0 | + |F 0 |) − 3, ´ıgy adódik a bizony´ıtandó becslés.

9

2.1. Alsó és fels˝o becslés p(g)-re 2.3. Lemma. Legyen A ∈ {0, 1}m×n egy m´ atrix. A k¨ ovetkez˝ o2a ´ll´ıt´ as ekvivalens:

(i) Létezik olyan C ∈ {0, 1}m×n m´ atrix , hogy C ≤ A (azaz cij ≤ aij ∀i ∈ {1, . . . , m}, ∀j ∈ {1, . . . , n}), és C minden sora legal´ abb q darab 1-est, és minden oszlopa legfeljebb r darab 1-est tartalmaz. (ii) ∀M ⊆ {1, . . . , m}, ∀N ⊆ {1, . . . , n}-re:

P

aij ≥ q|M | − r|N |.

i∈M,j∈{1,...,n}\N

Bizony´ıt´ as (v´ azlat):

Defini´ aljunk egy folyamot az s, t, u1 , . . . , um , v1 , . . . , vn cs´ ucsokon a

következ˝ok szerint. K¨ oss¨ uk ¨ ossze az s forrást az ui pontokkal, és legyen az élek kapacit´ asa q. Köss¨ uk ¨ ossze az ui pontokat a vj pontokkal és az ui vj él kapacit´ asa legyen ai,j . Vég¨ ul köss¨ uk ¨ ossze a vj pontokat a t nyel˝ ovel, az élek kapacit´ asa pedig legyen r. Ha (i) teljes¨ ul, akkor feltehetj¨ uk, hogy a C mátrix olyan, hogy minden sora pontosan q darab ´ 1-est tartalmaz. Igy pontosan akkor létezik mq érték˝ u (maximális) folyam, ha (i) teljes¨ ul. M´ asrészt megmutathat´ o, hogy a folyam minden vágása legal´ abb mq méret˝ u akkor és csak akkor, ha (ii) teljes¨ ul. Ezekb˝ ol az MFMC tétel alapján következik a lemma áll´ıtása.

2.4. Lemma. Legyen G s´ıkgr´ af, g(G) = g. Ekkor minden f ∈ F (G) lapnak ki tudjuk v´ alasztani g − 2 darab cs´ ucs´ at u ´gy, hogy egyik cs´ ucsot sem v´ alasztottuk 2-nél t¨ obb laphoz. Bizony´ıt´ as:

Legyen A = (af,v )f ∈F,v∈V ∈ {0, 1}|F |×|V | a G gráf lapjai és cs´ ucsai közötti

szomszéds´ agi mátrix, azaz af,v = 1 pontosan akkor, ha v cs´ ucsa f -nek. Azt akarjuk megmutatni, hogy létezik olyan C ∈ {0, 1}|F |×|V | mátrix, hogy C ≤ A, továbbá C minden oszlopa legal´ abb g − 2 darab 1-est, és minden oszlopa legfeljebb 2 darab 1-est tartalmaz. Ugyanis ekkor egy f ∈ F (G) laphoz rendelj¨ uk azokat a v cs´ ucsokat, melyekre cf,v = 1. A C-re vonatkozó feltételek biztos´ıtj´ ak, hogy ´ıgy a lemmának megfelel˝o választást adtunk. A bizony´ıt´ ashoz a 2.3 Lemm´ at használjuk fel, tehát azt fogjuk megmutatni, hogy minden X 0 0 F ⊆ F (G) és minden V ⊆ V (G) halmazra af,v ≥ (g −2)|F 0 |−2|V 0 |. Legel˝ osz¨ or f ∈F 0 ,v∈V \V 0

bontsuk két részre a szummát: X

f ∈F 0 ,v∈V \V 0

af,v =

X

f ∈F 0 ,v∈V

af,v −

X

af,v

f ∈F 0 ,v∈V 0

Az els˝o szummának g|F 0 | egy trivi´ alis alsó becslése, a második szumma fels˝o becslése pedig P af,v ≤ i(V 0 , F 0 ) ≤ 2|F 0 | + 2|V 0 | − 3 ≤ 2|F 0 | + 2|V 0 |. Így: a 2.2 Lemm´ aból j¨ on: f ∈F 0 ,v∈V 0

X

f ∈F 0 ,v∈V \V 0

af,v ≥ g|F 0 | − 2|F 0 | − 2|V 0 | = (g − 2)|F 0 | − 2|V 0 |.


2.1.3.

10

Polikromatikus ´ elsz´ınez´ es

A polikromatikus cs´ ucssz´ınezéshez hasonl´ oan a polikromatikus élsz´ınezést is definiálhatjuk. G gráf éleinek ξ : E(G) → {1, . . . , k} sz´ınezését polikromatikusnak nevezz¨ uk, ha minden v ∈ V (G) cs´ ucs polikromatikus, azaz minden v ∈ V (G) cs´ ucsra mind a k sz´ın el˝ofordul a v végpont´ u éleken: ∀ v ∈ V (G) ∀ i ∈ {1, . . . , k} ∃ uv ∈ E(G) : ξ(uv) = i. A polikromatikus cs´ ucssz´ınezésnél a legkisebb lap mérete volt egy triviális fels˝okorlát. Az élsz´ınezésnél nyilvánval´ o, hogy egy G gráf, melynek a legkisebb foksz´ ama d, nem sz´ınezhet˝o d-nél t¨ obb sz´ınnel polikromatikusan. Az él-polikromatikus számra nem fogunk a továbbiakban becsléseket adni, csup´ an azt fogjuk belátni, hogy minden G multi-gr´ afnak, melynek 3d + 1 sz´ınnel. Ehhez legkisebb foksz´ ama legal´ abb d, létezik polikromatikus él-sz´ınezése 4 3 lemmát használunk fel, melyeket röviden be is bizony´ıtunk. 2.5. Lemma. Legyen p egy pozit´ıv egész sz´ am. B´ armely G p´ aros multi-gr´ af élei kisz´ınezhet˝ oek p sz´ınnel u ´gy, hogy minden v cs´ ucsra a v-b˝ ol kiindul´ o, azonos sz´ın˝ u élek sz´ ama minden sz´ınrelényeg´ azaz b´ armely két sz´ınre ez a sz´ am legfeljebb eggyel tér el, teh´ at eben ugyanannyi, d(v) d(v) vagy , vagy . p p Bizony´ıt´ as: Els˝o lépésben vágjuk szét G cs´ ucsait - ha sz¨ ukséges - u ´ gy, hogy minden cs´ ucs foka legfeljebb p legyen. Ezt a következ˝o eljárás seg´ıtségével tegy¨ uk meg: vegy¨ unk egy v cs´ ucsot G-ben. Ha a v cs´ ucs foka ´ j cs´ ucsot d nagyobb mint p, akkor v helyett k darab u d vesz¨ unk: v1 , . . . vk , ahol k = . Ezeket v leszármazottjainak nevezz¨ uk. A v cs´ ucs, p G-beli vu1 , . . . , vud éleivel a következ˝ot csináljuk az u ´ j gráfban: minden i = 1, . . . , k-ra, (i − 1)p < j ≤ min{d, ip} esetén h´ uzzuk be a vi uj élt. Az eljárás befejeztével az u ´ j gráf p´ aros marad, és minden cs´ ucs´ anak legfeljebb p a foka. K˝onig tétele szerint ennek a gráfnak létezik jó p-élsz´ınezése. Sz´ınezz¨ uk ki ´ıgy a gráfot, majd egyes´ıts¨ uk u ´ jra a cs´ ucsok leszármazottjait, ´ıgy visszakaptuk az eredeti gr´ afunkat, és annak k´ıv´ ant sz´ınezését.

2.6. Lemma. Minden G multi-gr´ aftartalmaz olyan B p´ aros fesz´ıt˝ o részgr´ afot, hogy minden dG (v) v ∈ V (G) cs´ ucsra dB (v) ≥ . 2 Bizony´ıt´ as:

Tekints¨ uk G-nek egy olyan vágását, mely a lehet˝o legtöbb vágóélt tartal-

mazza. Legyen B az a p´ aros gr´ af, mely G cs´ ucsaib´ ol áll. Tegy¨ uk fel, ol ésa vágóélekb˝ dG (v) hogy ekkor létezik olyan v cs´ ucs, melyre dB (v) < . Ekkor azonban v-t áttéve az 2 élvágás másik osztályába G-nek t¨ obb vágóélt tartalmaz´ o élvágását kapjuk, mely ellent mond a feltevés¨ unknek.

11


2.7. Lemma. B´ armely G multi-gr´ af éleinek létezik olyan ir´ any´ıt´ asa, mely esetén d+ (v) ≥ d(v) . 2 Bizony´ıt´ as: Feltehetj¨ uk, hogy G ¨ osszef¨ ugg˝o, egyébként komponensenként láthatjuk be az áll´ıtást. Ha G minden foka p´ aros, akkor egy Euler-kör mentén ir´ any´ıtsuk meg az éleket. Tegy¨ uk fel ezut´ an, hogy G-nek léteznek p´ aratlan fok´ u cs´ ucsai. Ekkor adjunk hozz´ a G-hez egy u ´ j u cs´ ucsot. G ¨ osszes p´ aratlan fok´ u cs´ ucs´ at - melyekb˝ ol nyilvánvalóan p´ aros sok van - köss¨ uk ¨ ossze u-val. Az ´ıgy kapott G0 gráf minden foka p´ aros. Az el˝obb látott módon egy Euler-kör mentén ir´ any´ıtsuk meg G0 éleit, majd az eljárás végén t¨ orölj¨ uk ki a felvett u cs´ ucsot. Így G éleinek egy k´ıv´ ant ir´ any´ıtását kapjuk, hiszen a p´ aros fok´ u v cs´ ucsokra d(v) + 1 d(v) − 1 d(v) + + + , a p´ aratlan fok´ u v cs´ ucsokra d (v) = vagy d (v) = . d (v) = 2 2 2 2.2. T´ etel. Minden G multi-gr´ afnak, melynek legkisebb foksz´ ama d, létezik polikromatikus 3d + 1 élsz´ınezése sz´ınnel. 4 Bizony´ıt´ as:

Megadjuk G éleinek egy sz´ınezését u ´ gy, hogy minden cs´ ucs polikromatikus d legyen. A 2.6 Lemma alapj´ an G-nek van olyan B fesz´ıt˝o p´ aros részgr´ afja, hogy δ(B) ≥ . 2 Jelölje B kétosztályát B1 és B2 . Legyen a 2.5 Lemma szerint ξ a B gráf éleinek sz´ınezése 3d + 1 sz´ınnel. p= 4 Ha egy v cs´ ucsra dB (v) ≥ p, akkor v polikromatikus, hiszen a bel˝ole kiindul´ o élek között dB (v) ≥ 1 élen. mind a p sz´ın felt˝ unik legal´ abb p Tekints¨ unk egy olyan v cs´ ucsot, melyre dB (v) < p. Ekkor létezik olyan sz´ın, mely nem t˝ unik fel a v-b˝ol kiindul´ o sz´ınezett élek egyikén sem, ´ıgy a ξ sz´ınezés tulajdons´ aga alapján b´ armely sz´ın legfeljebb egyszer t˝ unik fel a v-b˝ol induló éleken, tehát a v végpont´ u sz´ınezett élek sz´ıne p´ aronként k¨ ulönb¨ oz˝o. Sz´ınezz¨ uk ki G eddig még nem sz´ınezett életi a következ˝ok szerint. El˝osz¨ or a 2.7 Lemmaalapj´ an ´ır´ any´ ıtsuk meg G[B1 ] és G[B2 ] éleit, ´ıgy minden v ∈ Bi ⊂ V (G) d − dB (v) + (i = 1, 2). A v-b˝ol induló nem sz´ınezett élek mindegyike cs´ ucsra dG[Bi ] (v) ≥ 2 Bi -beli. A v kezd˝ opont´ u ir´ any´ıtott éleket sz´ınezz¨ uk olyan sz´ınekkel, melyek nem t˝ unnek fel ´ a v-b˝ol induló B-beli éleken. Igyb´ armely v ∈ V(G) cs´ ucsra a bel˝ole kiindul´ ulönb¨ o, k¨ oz˝o d − dB (v) d − dB (v) , p = p, ugyanis dB (v) + ≥ sz´ın˝ u élek sz´ ama: min dB (v) + 2 2 $ % d d d − dB (v) d 3d + 1 2 + ≥ + = = p. 2 2 2 2 4

2.1.4.

Az als´ o becsl´ es igazol´ asa

Az el˝oz˝o szakaszokban kapott eredmények seg´ıtségével fogjuk megmutatni, hogy p(g) minden g ≥ 5 esetén.

3g − 5 ≤ 4

12


Bizony´ıt´ as:

Legyen G olyan s´ıkgr´ af, melyre g(G) = g. A 2.4 Lemma alapján minden

f ∈ F (G) lapnak ki tudjuk választani g − 2 cs´ ucs´ at u ´ gy, hogy G semelyik cs´ ucs´ at sem választottuk kett˝ onél t¨ obb laphoz. Egy H multi-gr´ afot fogunk elkész´ıteni a következ˝ok szerint. Vegy¨ unk fel két u ´ j x és y cs´ ucsot és legyen V (H) = F (G) ∪ {x, y}. Minden v ∈ V (G) cs´ ucsnak megfeleltet¨ unk egy H-beli élt, melyet v-él nek h´ıvunk. (i) Ha v-t két k¨ ulönb¨ oz˝o, f1 és f2 laphoz választottuk, akkor a v-él legyen f1 f2 . (ii) Ha v-t csak az f laphoz választottuk, akkor a v-él legyen f x. (iii) Ha v-t egyetlen laphoz sem választottuk, akkor a v-él legyen xy. Köss¨ uk ¨ ossze az x és y cs´ ucsokat g − 2 darab éllel, ´ıgy H egy hurokmentes multigráf, és b´ armely cs´ ucs´ uk H éleit p = anak foka legal´ abb g − 2. A 2.2 Tétel miatt kisz´ınezhetj¨ 3g − 5 3(g − 2) + 1 = sz´ınnel u ´ gy, hogy minden f ∈ V (H) cs´ ucs polikromatikus 4 4 legyen. Ezut´ an sz´ınezz¨ uk G cs´ ucsait u ´ gy, hogy minden v ∈ V (G) cs´ ucsra azt a sz´ınt választjuk, amilyen sz´ın˝ u a v-él. Nyilv´ anval´ o, hogy minden f ∈ F (G) lap polikromatikus. Ezzel G-nek 3g − 5 egy polikromatikus sz´ınezését adtuk sz´ınnel. 4

2.1.5.

A fels˝ o becsl´ es igazol´ asa

A bizony´ıt´ as során tetsz˝ alni fogunk egy Gg gráfot, melyre oleges 3 ≤ g egészre konstru´ 3g + 1 , ezzel igazolva a fels˝o becslést. g(Gg ) = g és p(Gg ) ≤ 4 g Bizony´ıt´ as: Legyen 3 ≤ g egész. Legyen p´ aros g esetén k = l = , p´ aratlan g esetén k = 2 g−1 g+1 ,l = . Kész´ıts¨ uk el a 2.3 ábr´ an látható Gg gráfot. A kis h´ aromsz¨ og (u1 , v1 , w1 ) 2 2 belsejében és a nagy h´ aromsz¨ og (uk , vl , wk ) k¨ ulsejében is vegy¨ unk fel g − 2 darab cs´ ucsot és köss¨ uk ¨ ossze u ´ gy, hogy egy-egy g hossz´ u kört kapjunk. Ezt ábr´ an szaggatott vonallal jelölj¨ uk. Ezzel g(Gg ) = g. Az u1 , . . . , uk , v1 , . . . vl , w1 , . . . wk cs´ ucsok mindegyike pontosan két olyan laphoz tartozik, mely nem tartalmaz szaggatott élt. Ezért Gg b´ armely polikromatikus sz´ınezése esetén minden sz´ınnel legal´ abb 2-t sz´ınezt¨ unk az u1 , . . . , uk , v1 , . . . vl , w1 , . . . wk ´ cs´ ucsok köz¨ ul. Igy 2p(Gg ) ≤ 2k + l =

melyb˝ol p(Gg ) ≤

3g + 1 . 4

(

3g 2 3g+1 2

ha g p´ aros ha g p´ aratlan

13

2.2. Kapcsolat a védelmi problém´ akkal

3g + 1 2.3. ´ abra. Gg gráf: g(Gg ) = g, p(Gg ) ≤ 4

2.2.

Kapcsolat a v´ edelmi probl´ em´ akkal

Az 1. fejezetben t¨ obbek között s´ıkgr´ afok levédésével foglalkoztunk az ˝oröket a cs´ ucsokba áll´ıtva. Tekins¨ uk egy tetsz˝ oleges G s´ıkgr´ af egy polikromatikus sz´ınezését, és válasszuk ki az egyik sz´ınt. Mivel a sz´ınezés polikromatikus, ezért minden lapon van olyan cs´ ucs, melyet a kiv´ alasztott sz´ınnel sz´ınezt¨ unk. Tehát ezekbe a cs´ ucsokba áll´ıtva az ˝oröket levédj¨ uk G-t. Ennek alapj´ an igaz a következ˝o tétel. n 2.3. T´ etel. B´ armely G s´ıkgr´ af levédhet˝ o 3g−5 ≤

|V (G)|.

4

4n o ˝rrel, ahol g = g(G) és n = 3g − 8

Az 1. fejezetben jmegmutattuk, hogy b´ armely n cs´ ucs´ u s´ıkgr´ af, melynek nincs 1 és 2 méret˝ u nk lapja, levédhet˝o orrel (1.2 Tétel). Ez egyszer˝ ˝ u következménye a 2.1 lemmának. 2

14

2.3. Kapcsolat a Négysz´ın-tétellel

2.3.

Kapcsolat a N´ egysz´ın-t´ etellel

2.4. T´ etel (N´ egysz´ın-t´ etel). Minden s´ıkgr´ af j´ ol 4-sz´ınezhet˝ o. A négysz´ın-sejtést Francis Gutrhie fogalmazta meg. Eszerint b´ armely térkép kisz´ınezhet˝o 4 sz´ınnel u ´ gy, hogy a szomszédos tartományok k¨ ulönb¨ oz˝o sz´ın˝ uek. Ezt könnyen átfogalmazhatjuk s´ıkgr´ afokra, ha a tartományokat tekintj¨ uk a s´ıkgr´ af cs´ ucsainak, és két cs´ ucs között pontosan akkor megy él, ha a nekik megfelel˝o két tartomány szomszédos. Az els˝o bizony´ıt´ ast Kenneth Appel, Wolfgang Haken és John Koch adták 1976-ban. Bizony´ıtásukban s´ıkgr´ afokból ´ alló elker¨ ulhetetlen halmazokat vizsgáltak. Egy elker¨ ulhetetlen halmaz olyan, hogy egy tetsz˝ oleges s´ıkgr´ af h´ aromsz¨ ogelése részgr´ afként tartalmaz legal´ abb egyet a halmazbeli s´ıkgr´ afok köz¨ ul. A bizony´ıt´ as további részét szám´ıtógéppel ellen˝ orizték, mely kör¨ ulbel¨ ul 1200 ór´ at vett igénybe, és a publikáci´ o végleges változata 741 oldalb´ ol áll. 20 évvel kés˝obb Neil Robertson, Paul Seymour, Daniel Sanders és Robin Thomas továbbfejlesztették a bizony´ıt´ ast. A lehetséges esetek sz´ am´ at 638-ra reduk´ alt´ ak, és egy O(n2 )-es gráf-sz´ınez˝o algoritmust haszálva 24 ´ ora alatt futtaták le azokat. A végleges publikáci´ o 43 oldal terjedelm˝ u lett. 2005-ben Georges Gonthier a Coq tétel bizony´ıtó rendszerben ellen˝ orizte a Négysz´ıntételt. Szám´ıt´ ogépet mell˝ oz˝o bizony´ıtást azóta sem ismer¨ unk. Ebben a fejezetben láttuk, hogy 2 ≤ p(5) ≤ 4. Most megmutatjuk, hogy a p(5) = 4 egyenl˝ oségb˝ ol következne a Négysz´ın-tétel. A gondolatmenet hasonl´ o lesz ahhoz, mint amikor megmutattuk, hogy p(4) < 3. Tekints¨ uk a 2.4 ábr´ an szerepl˝ o G5B b´ azisgráfot. A k¨ uls˝ o

2.4. ábra. G5B b´ azisgráf lap polikromatikus sz´ınezését˝ol eltekintve G5B b´ armely polikromatikus 4-sz´ınezése esetén az x és y cs´ ucsok k¨ ulönb¨ oz˝o sz´ın˝ uek lesznek, k¨ ulönben a gráf sz´ınezett lapja nem lenne polikromatikus. Tekints¨ unk egy tetsz˝ oleges G s´ıkgr´ afot, és minden uv ∈ V (G) élt helyettes´ıts¨ unk G5B egy

2.3. Kapcsolat a Négysz´ın-tétellel

15

péld´ anyával u ´ gy, hogy az u illetve v cs´ ucsokba az x illetve y cs´ ucsok ker¨ uljenek. Ezut´ an G minden f lapj´ anak belsejében vegy¨ unk még fel 3 pontot, melyeket f valamely szomszédos 2 cs´ ucs´ aval körbek¨ ot¨ unk. Egy példa látható a 2.5 ábr´ an. Az ´ıgy kapott G0 gráf b´ armely lapja legal´ abb 5 méret˝ u. Ha p(5) = 4, akkor G0 -nek létezik polikromatikus 4-sz´ınezése, és egy ilyen sz´ınezés esetén minden G0 -beli b´ azisgr´ af (a k¨ uls˝ o lapjukt´ ol eltekintve) polikromatikusan 4-sz´ınezett lesz, ezért a G0 -beli b´ azisgr´ afok x és y cs´ ucsai k¨ ulönb¨ oz˝o sz´ın˝ uek. Azaz ha G minden cs´ ucs´ at

2.5. ´ abra. G0 konstrukci´ oja. A megvastag´ıtott élek G5B egy-egy péld´ anyát jelölik.

olyan sz´ın˝ ure sz´ınezz¨ uk, mint a megfelel˝o G0 -beli cs´ ucs sz´ıne, akkor G egyik éle sem lesz monokromatikus, teh´ at G egy j´ o sz´ınezését kapjuk (legfeljebb) 4 sz´ınnel.

¨ 2.4. Osszefoglal´ as, nyitott kérdések

2.4.

16

¨ Osszefoglal´ as, nyitott k´ erd´ esek

Ebben a fejezetben megmutattuk, hogy p(1) = p(2) = 1, p(3) = p(4) = 2, és g ≥ 3 esetén 3g + 1 3g − 5 ≤ p(g) ≤ . 4 4 2.1. Nyitott k´ erd´ es. Hat´ arozzuk meg p(g) pontos értékét minden pozit´ıv egész g-re. A g = 5 az els˝o nyitott eset, ahol egyel˝ore annyit tudunk, hogy 2 ≤ p(5) ≤ 4. Legyen p0 (g) := min{p(G)|G egyszer˝ u s´ıkgr´ af, g(G) = g}. 2.2. Nyitott k´ erd´ es. Milyen g értékekre a ´ll fent a p(g) = p0 (g) egyenl˝ oség? Ismeretes, hogy egy konvex poliéder reprezent´ alható egy 3-összef¨ ugg˝o egyszer˝ u s´ıkgr´ affal. Megmutathat´ o az is, hogy egy 3-¨ osszef¨ ugg˝o egyszer˝ u s´ıkgr´ af realizálható egy konvex poliéderként. Ezért a 3-¨ osszef¨ ugg˝ o egyszer˝ u s´ıkgr´ afokat szok´ as poliéder gr´ afoknak nevezni. Legyen p00 (g) := min{p(G)|G poli´ eder gr´ af, g(G) = g}. Mivel egy konvex poliéder b´ armely lapja legal´ abb 3 oldal´ u, és b´ armely konvex poliédernek létezik olyan lapja, mely legfeljebb 5 oldal´ u, ezért p00 (g) kizár´ olag a g = 3, 4, 5 értekekre értelmes. 2.3. Nyitott k´ erd´ es. Hat´ arozzuk meg p00 (g) pontos értékét (g = 3, 4, 5).

3. fejezet

Feloszt´ asok polikromatikus sz´ınez´ ese Ebben fejezetben a s´ıkgr´ afok két speci´ alis osztályának sz´ınezésével foglalkozunk. Téglalapfeloszt´ asnak nevezz¨ uk egy téglalap felosztását véges sok, egym´ ast nem fed˝o téglalapokra u ´ gy, hogy semelyik négy sem tal´ alkozik közös cs´ ucsban. Ha egy felosztásn´ al megengedj¨ uk azt, hogy négy téglalap egy cs´ ucsban tal´ alkozzon, akkor a ´ltal´ anos feloszt´ asr´ ol beszél¨ unk. Egy felosztás rendjén a felosztásban szerepl˝ o téglalapok szám´ at értj¨ uk, beleértve az eredeti téglalapot mint k¨ uls˝ o tartom´ anyt. Legyen S(t) az F felosztás t téglalapjának 4 sark´ at tartalmaz´ o halmaz. (Tehát egy felosztásbeli téglalapnak pontosan 4 sarka van, de lehetnek még egyéb cs´ ucsok a ker¨ uletén.) A t1 és t2 téglalapok szomszédosak F -ben, ha S(t1 )∩S(t2 ) 6= ∅, és ekkor egy u ∈ S(t1 )∩S(t2 ) cs´ ucsot t1 és t2 k¨ oz¨ os sark´ anak nevez¨ unk. Tehát a T felosztás egy téglalap-feloszt´ as, ha minden t1 , t2 , t3 , t4 ∈ T esetén S(t1 ) ∩ S(t2 ) ∩ S(t3 ) ∩ S(t4 ) = ∅. Megjegyezz¨ uk, hogy ez már b´ armely 3 téglalap esetén is teljes¨ ul. Az is nyilvánvaló, hogy egy téglalap-feloszt´ as esetében minden cs´ ucs pontosan két felosztásbeli téglalap közös sarka (beleértve az eredeti t∗ téglalapot is). Egy felosztásra tekinthet¨ unk u ´ gy is, mint egy s´ıkgr´ af, melynek cs´ ucsai a téglalapok sarkai, élei pedig ezen téglalapok oldalainak azon szegmensei, melyek a cs´ ucsokat kötik össze. A ´ felosztások sz´ınezését u ´ gy értelmezz¨ uk, mintha a s´ıkgr´ af cs´ ucsait sz´ıneznénk. Erdemes el˝ore kiemelni, hogy a felosztások polikromatikus sz´ınezésekor nem k¨ ovetelj¨ uk meg, hogy a k¨ uls˝ o lap polikromatikus legyen. Ezért vezess¨ uk be a következ˝o jelölést. Ha egy F felosztás téglalapjairól u ´ gy beszél¨ unk, hogy a k¨ uls˝ o t∗ tartományt is beleértj¨ uk, akkor a felosztást F ∗ -al jel¨ olj¨ uk.

17

3.1. Téglalap-feloszt´ asok polikromatikus sz´ınezései

3.1. 3.1.1.

18

T´ eglalap-feloszt´ asok polikromatikus sz´ınez´ esei Er˝ osen polikromatikus 4-sz´ınez´ es

Egy T téglalap-feloszt´ as er˝ osen polikromatikus 4-sz´ınezésén a felosztás olyan χ : V (T ) → {1, 2, 3, 4} 4-sz´ınezését értj¨ uk, melynél minden téglalapnak mind a 4 sz´ın el˝ofordul a sarkaiban: ∀t ∈ T ∀i ∈ {1, 2, 3, 4} ∃u ∈ S(t) : χ(u) = i. Ismét kihangs´ ulyozzuk, hogy a k¨ uls˝ o lap polikromatikusságát nem követelj¨ uk meg. 3.1. T´ etel. Minden téglalap-feloszt´ asnak létezik polikromatikus 4-sz´ınezése. 3.2. T´ etel. Minden téglalap-feloszt´ asnak létezik er˝ osen polikromatikus 4-sz´ınezése.

3.1. ábra. Egy téglalap-feloszt´ as polikromatikus (a), és er˝osen polikromatikus sz´ınezése (b)

A 3.2 Tételnek egyértelm˝ u következménye a 3.1 Tétel, ´ıgy a továbbiakban az utóbbi bizony´ıt´ as´ aval foglalkozunk. Ehhez tegy¨ unk egy kis kitér˝ot az r-gráfok felé. Egy r-reguláris G multigráfot r-gr´ afnak nevez¨ unk, ha p´ aros szám´ u cs´ ucsa van, és G minden vágása, mely V (G)-t két p´ aratlan számosság´ u halmazra osztja, legal´ abb r vágóélt tartalmaz. A 3.2 Tétel bizony´ıt´ asa során felhasználjuk Bertrand Guenin alábbi eredményét, melyet most bizony´ıt´ as nélk¨ ul közl¨ unk. 3.3. T´ etel (Guenin, [7]). Minden s´ıkbarajzolhat´ o 4-gr´ afnak létezik j´ o 4-élsz´ınezése. Folytassuk teh´ at a 3.2 Tétel bizony´ıtásával: Bizony´ıt´ as: Legyen T egy téglalap-feloszt´ as. Feltehetj¨ uk, hogy T rendje p´ aros, k¨ ulönben kiegész´ıthetj¨ uk p´ aros rend˝ uvé a 3.2 (a,b) ábr´ an l´ atható módon. Konstru´ aljunk egy G gráfot a következ˝ok szerint. Minden T ∗ -beli téglalapnak feleltess¨ unk meg egy cs´ ucsot G-ben. Gben a t1 és t2 téglalapoknak megfelel˝o cs´ ucsokat pontosan annyi éllel köss¨ uk össze, ahány közös sarka van t1 -nek és t2 -nek T ∗ -ban. Tehát G minden cs´ ucsa egy T ∗ -beli téglalapnak, és G minden éle egy T -beli cs´ ucsnak felel meg. A 3.2 (b,c) ábr´ an láthatunk egy péld´ at, melyen a téglalap-feloszt´ ast és a G gráfot egy¨ utt ábr´ azoljuk. Nyilv´ anval´ o, hogy a kapott G multigráf egy 4-regul´ aris s´ıkgr´ af, p´ aros szám´ u cs´ uccsal. Azt fogjuk bel´ atni, hogy G egy 4-gr´ af. Ehhez már csak azt kell megmutatni, hogy G minden vágása legal´ abb 4 vágóélt tartalmaz.


19

3.2. ábra. (a,b) Egy téglalap-feloszt´ as p´ aros rend˝ uvé egész´ıtése; (c) A megkonstru´ alt G gráf; (d) G vágása

Legyen (X, V (G)\X) a G egy vágása. Legyen C a G[X] maxim´ alis összef¨ ugg˝o komponense. C a T felosztásban téglalapok egyes´ıtésének felel meg, amely egy ortogonális P sokszög. A 3.2 (d) ´ abr´ an X a sz´ınezett téglalapoknak megfeleltett cs´ ucshalmaz (mely most egyben a C is), a vágóéleket pedig megvastag´ıtottuk.

π . Nyilv´ anvaló, 2 hogy P ker¨ uletén legal´ abb 4 konvex cs´ ucs van. Tekints¨ uk G egy olyan e élét, amely P egy Egy ortogonális sokszög cs´ ucs´ at nevezz¨ uk konvex nek, ha a hozz´ atartozó szög

konvex cs´ ucs´ anak felel meg. Ekkor az e él nem mehet két P -beli téglalapot reprezent´ aló (azaz két C-beli) cs´ ucs között. Ugyanis két P -beli téglalapot reprezen´ atl´ o cs´ ucs között pontosan akkor megy él G-ben, ha a téglalapoknak létezik közös sarkuk, de a közös sarok nem lehet konvex cs´ ucs P -ben. M´ asrészt az e él nem mehet két X-beli cs´ ucs között sem, C maximalit´ as miatt. Tehát a P konvex cs´ ucs´ anak megfeleltetett e él vágóél, ´ıgy a vágás legal´ abb 4 vágóélt tartalmaz, teh´ at G 4-gráf. Tekints¨ uk G egy jó 4-élsz´ınezését, amely a 3.3 Tétel szerint létezik. Ezut´ an a T téglalap-feloszt´ as minden cs´ ucs´ at sz´ınezz¨ uk olyan sz´ınre, amilyen a neki megfeleltetett G-beli él sz´ıne. G konstrukciója miatt ez T -nek egy er˝osen polikromatikus 4-sz´ınezése.

3.1. Megjegyz´ es. A bizony´ıt´ asban szerepl˝ o konstrukci´ on´ al kihaszn´ altuk azt, hogy egy téglalap-feloszt´ as cs´ ucsa pontosan két téglalap k¨ oz¨ os sarka, ezért az a ´ltal´ anos feloszt´ asokn´ al nem tudunk ilyen gr´ afot kész´ıteni. M´ asrészt a k¨ ovetkez˝ o szakaszban megmutatjuk, hogy van olyan a ´ltal´ anos feloszt´ as, melynek nincs polikromatikus 4-sz´ınezése. 3.2. Megjegyz´ es. A bizony´ıt´ as sor´ an a k¨ uls˝ o tartom´ any is er˝ osen polikromatikus 4-sz´ınezett lett. Ez azt jeleneti, hogy ha az eredeti téglalap-feloszt´ asunk p´ aros rend˝ u volt, akkor 4 sz´ınnel megsz´ınezhet˝ o er˝ osen polikromatikusan u ´gy, hogy a k¨ uls˝ o tartom´ any sarkaiban is mind a 4 sz´ın felt˝ unj¨ on. A p´ aratlan rend˝ u téglalap-feloszt´ asokat a 3.2 (a,b) a ´br´ anak megfelel˝ oen p´ aros rend˝ uvé egész´ıthetj¨ uk, de ha a sz´ınezés ut´ an elt¨ or¨ olj¨ uk a felvett téglalapot, akkor az eredeti téglalap-feloszt´ as k¨ uls˝ o lapja nem lesz er˝ osen polikromatikus.


3.1.2.

20

Guillotine-feloszt´ asok

A guillotine-felosztás a téglalap-feloszt´ asok egy speci´ alis családja. Egy guillotine-feloszt´ ast rekurz´ıv módon kaphatunk meg a következ˝oképpen, véges sok lépést végrehajtva. (i) Kiindul´ as: Egy téglalap. (Minden téglalap guillotine-felosztás) (ii) Egy l´ ep´ es: A guillotine-felosztás egy téglalapját valamely oldal´ aval p´ arhuzamos egyenessel két téglalapra vágjuk. 3.4. T´ etel (Horev, Katz, Krakovski, L¨ offler, [8]). Minden guillotine-feloszt´ asnak létezik er˝ osen polikromatikus 4-sz´ınezése, mely O(n) id˝ o alatt megtal´ alhat´ o, ahol n a feloszt´ as rendje. 3.5. T´ etel (Keszegh, [10]). Minden n-dimenzi´ os guillotine-feloszt´ asnak létezik er˝ osen polikromatikus 2n -sz´ınezése. A 3.4 Tétel els˝o fele azonnal következik a 3.2 Tételb˝ol. A tétel eredeti bizony´ıtásában [8] a szerz˝ ok kihaszn´ alt´ ak a guillotine-felosztások rekurz´ıv felép´ıtését. A felosztást egy bináris fában t´ arolva (az el´ agazások a vágásoknak felelnek meg) a bizony´ıtásb´ ol egy O(n)-es algoritmus adható er˝ osen polikromatikus 4-sz´ınezés megtalálására. Az n-dimenziós esettel Keszegh Bal´ azs foglalkozott, ˝ o bizony´ıtotta a 3.5 Tételt.

´ 3.2. Altal´ anos felosztások polikromatikus sz´ınezései

3.2.

21

´ Altal´ anos feloszt´ asok polikromatikus sz´ınez´ esei

Az által´ anos felosztások sz´ınezésekor kib˝ov´ıtj¨ uk a polikromatikus sz´ınezés fogalmát. Egy A ´ altal´ anos felosztás gyenge a ´ltal´ anos polikromatikus k-sz´ınezésén, olyan ϑ : V (A) → {1, . . . , k} sz´ınezést ért¨ unk, melyre (i) k ≤ 4 esetén: minden t ∈ A téglalap cs´ ucsai között mind a k sz´ın felt˝ unik. (ii) k ≥ 4 esetén: minden t ∈ A téglalap cs´ ucsai között legal´ abb 4 sz´ın felt˝ unik. Egy A ´ altal´ anos felosztás er˝ os a ´ltal´ anos polikromatikus k-sz´ınezésén, olyan θ : V (A) → {1, . . . , k} sz´ınezést ért¨ unk, melyre (i) k ≤ 4 esetén: minden t ∈ A téglalap sarkai között mind a k sz´ın felt˝ unik. (ii) k ≥ 4 esetén: minden t ∈ A téglalap sarkai között 4 sz´ın felt˝ unik. 3.3. Megjegyz´ es. Nyilv´ anval´ o, hogy k ≤ 4 esetén a defin´ıci´ ok megegyeznek a régi polikromatikus illetve er˝ osen polikromatikus sz´ınezés defin´ıci´ oj´ aval. 3.4. Megjegyz´ es. Vil´ agos, hogy k ≥ 4 esetén egy gyenge (ill. er˝ os) a ´ltal´ anos polikromatikus k-sz´ınezés egyben egy gyenge (ill. er˝ os) a ´ltal´ anos polikromatikus (k + 1)-sz´ınezés is (hiszen tov´ abbi sz´ıneket is megengedhet¨ unk, melyeket nem haszn´ alunk). Hasonl´ oan trivi´ alis, hogy k ≤ 4 esetén minden gyenge (ill. er˝ os) a ´ltal´ anos polikromatikus k-sz´ınezés implik´ al egy gyenge (ill. er˝ os) a ´ltal´ anos polikromatikus (k − 1)-sz´ınezést (péld´ aul u ´gy, hogy két sz´ınt o ¨sszeolvasztunk). Elegend˝ o teh´ at olyan gyenge és er˝ os k-sz´ınezéseket tal´ alnunk, hogy k a lehet˝ o legk¨ ozelebb legyen 4-hez.

3.2.1.

Gyenge ´ altal´ anos polikromatikus 4-sz´ınez´ es

3.6. T´ etel. Létezik olyan a ´ltal´ anos feloszt´ as, melynek nem létezik gyenge a ´ltal´ anos polikromatikus 4-sz´ınezése.

3.3. ´ abra. (a) a G 3 × 3-s négyzetr´ acs felosztás; (b) a H felosztás

A 3.6 Tétel bizony´ıt´ as´ ahoz tekints¨ uk el˝osz¨ or a 3.3 a´br´ an látható G (3 × 3-as négyzetr´ acs) és H ´ altal´ anos felosztásokat, melyek egy négyzet felosztásával keletkeztek. A G illetve H felosztások (bal, fels˝o, jobb, alsó) szélén, azoknak a cs´ ucsoknak a halmazát értj¨ uk, melyek az eredeti négyzet (bal, fels˝o, jobb, alsó) oldal´ an fekszenek. Az alábbi 3 áll´ıtás triviális:


22

´ ıt´ 3.1. All´ as. Ha G egy gyenge a ´ltal´ anos polikromatikus 4-sz´ınezésénél 3 sz´ın felt˝ unik a bal (fels˝ o) szélen, akkor ugyanez a 3 sz´ın felt˝ unik a jobb (als´ o) szélen is. ´ ıt´ 3.2. All´ as. G semelyik gyenge a ´ltal´ anos polikromatikus 4-sz´ınezésénél nem fordulhat el˝ o, hogy ha valamely 3 sz´ın felt˝ unik a bal (jobb) szélen, akkor ugyanez a 3 sz´ın felt˝ unik az als´ o (fels˝ o) szélen is. ´ ıt´ 3.3. All´ as. H b´ armely gyenge a ´ltal´ anos polikromatikus 4-sz´ınezésénél 3 sz´ın felt˝ unik a bal vagy a jobb szélén. Konstru´ aljunk egy Q felosztást a következ˝oképpen: induljunk ki a 7 × 7-es négyzetr´ acsból, majd a középs˝ o 4 négyzetet egyes´ıts¨ uk.

Ezut´ an az imént egyes´ıtett négyzet oldal´ aval

szomszédos négyzeteket is egyes´ıts¨ uk a 3.4 (a) ábr´ an látható módon. Legyenek G1 , G2 , G3 , G4 rendre a Q bal fels˝o, jobb fels˝o, bal alsó, jobb alsó sark´ anál tal´ alható 3 × 3-s négyzetr´ acs felosztások. 3.1. Lemma. A Q feloszt´ as b´ armely gyenge a ´ltal´ anos polikromatikus 4-sz´ınezésénél 3 sz´ın felt˝ unik a G1 fels˝ o szélén, vagy a G2 fels˝ o szélén. Bizony´ıt´ as: Tegy¨ uk fel indirekt, hogy sem G1 , sem G2 fels˝o szélén nem t˝ unik fel 3 sz´ın. A ´ ıt´ ´ ıtás 3.1 All´ as alapj´ an ekkor sem G1 , sem G2 alsó szélén nem t˝ unik fel 3 sz´ın. A 3.3 All´ alapján G3 és G4 fels˝o szélén is felt˝ unik 3 sz´ın, ugyanis G3 és G4 között a H egy elforgatottja ´ van. Vég¨ ul a 3.2 All´ıt´ as miatt sem G3 jobb szélén, sem G4 bal szélén nem t˝ unik fel 3 sz´ın, ´ ezzel azonban ellentmond´ asra jutottunk a 3.3 All´ıtással. 3.1.1. K¨ ovetkezm´ eny. Ha a Q-nak létezik gyenge a ´ltal´ anos polikromatikus 4-sz´ınezése, ´ ´ akkor a 3.1 Lemma és a 3.2 All´ıt´ as miatt két eset fordulhat el˝ o. Oramutat´ o j´ ar´ as´ aval megegyez˝ oen haladva: (i) Q minden szélének els˝ o 3 cs´ ucsa 3 sz´ınnel sz´ınezett, utols´ o 3 cs´ ucsa 2 sz´ınnel sz´ınezett. (ii) Q minden szélének els˝ o 3 cs´ ucsa 2 sz´ınnel sz´ınezett, utols´ o 3 cs´ ucsa 3 sz´ınnel sz´ınezett. Defini´ aljunk most egy C felosztást: vegy¨ unk egy 3 × 3-as négyzetr´ acsot, majd a bal fels˝o és jobb alsó négyzetébe ´ agyazzuk be Q egy-egy péld´ anyát (Q1 és Q2 ), a jobb fels˝o négyzetébe pedig egy 7 × 7-es négyzetr´ acsot a 3.4 (b) ábr´ anak megfelel˝oen. Megmutatjuk, hogy a C felosztásnak nem létezik gyenge által´ anos polikromatikus 4-sz´ınezése, ezzel bel´ atva a 3.6 Tételt. Bizony´ıt´ as: Tegy¨ uk fel indirekt, hogy C-nek létezik ilyen sz´ınezése. A 3.1 Lemm´ at alkalmazva Q1 -re és Q2 -re: C-ben a 7 × 7-es négyzetr´ acs bal és alsó szélén is tal´ alható 3 egym´ ast követ˝o cs´ ucs, melyek p´ aronként k¨ ulönb¨ oz˝o sz´ın˝ ure vannak festve mégpedig u ´ gy, hogy azok ´ ıtás miatt a 7 × 7-es négyzetr´ a széleknek els˝o 3, vagy utols´ o 3 cs´ ucsai. A 3.1 All´ acsban tal´ alhat´ o olyan 3 × 3-as négyzetr´ acs, melynek jobb és alsó szélén is 3 sz´ın felt˝ unik, ez azon´ ban ellentmond a 3.2 All´ıt´ asnak.


23

3.4. ´ abra. (a) A Q felosztás; (b) A C felosztás

3.2.2.

Gyenge ´ altal´ anos polikromatikus 3- ´ es 5-sz´ınez´ es

A következ˝o 2 szakasz bizony´ıt´ asaiban moh´ o algoritmusokat fogunk megadni. A bizony´ıt´ asokhoz el˝ osz¨ or is helyezz¨ uk el a felosztásokat a deréksz¨ og˝ u koordináta-rendszerben u ´ gy, ´ hogy a téglalapok oldalai p´ arhuzamosak legyenek a tengelyekkel. Igy egy felosztás cs´ ucsait a koordin´ atáikkal azonos´ıthatjuk. A moh´ o algorimusokhoz definiáljuk a felosztások cs´ ucsainak sz´ınezési sorrendjét : a koordin´ atákat olyan sorrendben tekints¨ uk, hogy azokat el˝osz¨ or az y koordin´ ata szerint a legnagyobbt´ ol a legkisebbig, majd ezen bel¨ ul az x koordináta szerint a legkisebbt˝ol a legnagyobbig rendezz¨ uk. Azaz balról-jobbra, fentr˝ol-le. Péld´ aul az egység négyzet cs´ ucsainak sz´ınezési sorrendje: (0, 1), (1, 1), (0, 0), (1, 0). Nyilv´ analó, hogy ha ebben a sorrendben sz´ınezz¨ uk a cs´ ucsokat, akkor minden felosztásbeli téglalapnak a jobb alsó sark´ at fogjuk utoljára sz´ınezni. 3.7. T´ etel. Minden a ´ltal´ anos feloszt´ asnak létezik gyenge a ´ltal´ anos polikromatikus 3-sz´ınezése. Bizony´ıt´ as:

Tekints¨ unk egy A felosztást. A-ban minden v cs´ ucsnak legfeljebb egy olyan

szomszédja van, melynek az x koordinátája kisebb az övénél, és legfeljebb egy olyan szomszédja van, melynek y koordin´ atája nagyobb az övénél. Tekints¨ uk A cs´ ucsainak sz´ınezési sorrendjét. A moh´ o algoritmus során a cs´ ucsokat ebben a sorrendben fogjuk sz´ınezni 3 sz´ınnel, u ´ gy hogy a kisz´ınezett v cs´ ucs sz´ıne k¨ ulönb¨ ozz¨ on az eml´ıtett, legfeljebb 2 szomszédos cs´ ucs sz´ınét˝ol. Legyen az éppen sz´ınezend˝ o cs´ ucs v. Az algoritmus egy által´ anos lépése: (i) Ha v-nek még nincs sz´ınezett szomszédja (azaz v az A bal fels˝o sarka), akkor v-t tetsz˝ oleges sz´ınnel sz´ınezz¨ uk ki. (ii) Ha v-nek idáig egyetlen szomszédját (w) sz´ınezt¨ uk ki, akkor v-t sz´ınezz¨ uk ki tetsz˝ oleges, w sz´ınét˝ol k¨ ulönb¨ oz˝o sz´ınre. (iii) Ha v-nek idáig két sz´ınezett szomszédja van (x és y), akkor ez a h´ arom cs´ ucs egy t ∈ A téglalap hat´ ar´ an van, melynek v a jobb alsó sarka.


24

(a) Ha x és y k¨ ulönb¨ oz˝o sz´ın˝ ure vannak sz´ınezve, akkor v-t sz´ınezz¨ uk a harmadik sz´ınnel. (b) Tegy¨ uk fel, hogy x és y azonos sz´ın˝ ure vannak sz´ınezve. Mivel v a t utols´ o sz´ınezend˝ o cs´ ucsa, ´ıgy x-nek t-ben már van egy sz´ınezett w szomszédja, és a kezdeti feltevés¨ unk szerint x sz´ıne k¨ ulönb¨ ozik w sz´ınét˝ol. A 3.5 ábr´ an két példa látható x, y, v, w helyzetére. Ezért v-t az x és w sz´ıneit˝ ol eltér˝o sz´ınnel sz´ınezve, t hat´ ar´ an felt˝ unik mind a 3 sz´ın. A le´ırt algoritmus során minden t ∈ A téglalap polikromatikusan 3-sz´ınezett lesz, ´ıgy megadtuk az A felosztás egy gyenge ´ altal´ anos polikromatikus 3-sz´ınezését.

3.5. ´ abra. Két példa az éppen sz´ınezend˝ o v cs´ ucs és az x, y, w cs´ ucsok helyzetére.

3.8. T´ etel. Minden a ´ltal´ anos feloszt´ asnak létezik gyenge a ´ltal´ anos polikromatikus 5-sz´ınezése. Bizony´ıt´ as: Tekints¨ unk egy A felosztást. A következ˝o algoritmussal megadjuk A-nak egy 5-sz´ınezését, melynél a cs´ ucsokat a sz´ınezési sorrendben sz´ınezz¨ uk. Legyen v az éppen sz´ınezend˝ o cs´ ucs. Legyen (ha létezik) x a v azon szomszédja, melynek x koordinátája kisebb az övénél, és legyen (ha létezik) y a v azon szomszédja, melynek y koordinátája nagyobb az övénél. Tehát x a v bal oldali szomszédja, y a v fels˝o szomszédja. Továbbá legyenek (ha léteznek) Bv illetve Jv azon A-beli téglalapok, melyeknek v a bal alsó illetve a jobb alsó sarka, és legyen w az y, v-t˝ ol eltér˝ o szomszédja Bv -ben. A 3.6 ábr´ an látható két példa ezek elhelyezkedésére. Az éppen sz´ınezend˝ o v cs´ ucsnak az alábbi feltételekkel válasszunk sz´ınt: (i) v sz´ıne k¨ ulönb¨ ozz¨ on x sz´ınét˝ol (ii) v sz´ıne k¨ ulönb¨ ozz¨ on y sz´ınét˝ol (iii) v sz´ıne k¨ ulönb¨ ozz¨ on w sz´ınét˝ol (iv) v sz´ıne k¨ ulönb¨ ozz¨ on a Jv − {v}-n használt (legalább) 3 sz´ınt˝ ol A (ii) és (iii) feltétel biztos´ıtja azt, hogy Bv (ha létezik) cs´ ucsain legal´ abb 3 sz´ın felt˝ unj¨ on. Ha Jv létezik, akkor van olyan v 0 cs´ ucs, hogy Jv = Bv0 , ráadásul v 0 megel˝ozi v-t a sz´ınezési sorrendben, teh´ at Jv − {v} legal´ abb 3-sz´ınezett. Ezzel látjuk, hogy a (iv) feltétel¨ unk is értelmes. Mivel minden t ∈ A téglalapra létezik olyan v cs´ ucs, hogy t = Jv , ´ıgy a fenti feltételekkel az


25

algoritmus a cs´ ucsoknak olyan sz´ınezését adja meg, hogy minden A-beli téglalap legal´ abb négy sz´ınnel sz´ınezett lesz. Továbbá az éppen sz´ınezend˝ o cs´ ucs sz´ınére a feltételek legfeljebb 4 sz´ınt tiltanak meg, ´ıgy 5 sz´ın mindenképpen elegend˝o a felosztás sz´ınezéséhez.

3.6. ´ abra. Két példa az éppen sz´ınezend˝ o v cs´ ucs és az x, y, w cs´ ucsok helyzetére.

3.5. Megjegyz´ es. A 3.7 és 3.8 Tétel bizony´ıt´ as´ aban adott polikromatikus sz´ınezések j´ o sz´ınezések is. Ezt a 3.7 tételben a (iii), a 3.8 Tételben pedig az (i) és (ii) feltételek biztos´ıtj´ ak.

3.2.3.

Er˝ os ´ altal´ anos polikromatikus 2- ´ es 6-sz´ınez´ es

3.9. T´ etel. Minden a ´ltal´ anos feloszt´ asnak létezik er˝ os a ´ltal´ anos polikromatikus 2-sz´ınezése. Bizony´ıt´ as: Tekints¨ unk egy A felosztást és cs´ ucsainak a sz´ınezési sorrendjét. Ismét ebben a sorrenben fogjuk megsz´ınezni a cs´ ucsokat, de most csak 2 sz´ınnel. Legyen az éppen sz´ınezend˝ o cs´ ucs v: (i) Ha v semelyik A-beli téglalapnak sem a jobb alsó sarka, akkor v-t sz´ınezz¨ uk tetsz˝ oleges sz´ınre. (ii) Ha v valamely t ∈ A téglalap jobb alsó sarka, akkor t másik h´ arom sarka már sz´ınezett. (a) Ha t sz´ınezett sarkain mind a 2 sz´ın felt˝ unik, akkor v-t tetsz˝ oleges sz´ınnel sz´ınezhetj¨ uk. (b) Ha t sz´ınezett sarkai azonos sz´ın˝ ure vannak sz´ınezve, akkor v-t sz´ınezz¨ uk az ett˝ ol eltér˝ o sz´ınnel. A 3.11 Tétel bizony´ıt´ as´ ahoz tegy¨ unk egy kis kitér˝ot a gráfok list´ as sz´ınezése felé. Legyen G egy gr´ af, és minden v ∈ V (G) cs´ ucsra legyen adott a sz´ınek egy L(v) halmaza (lista), melyekkel a v cs´ ucsot sz´ınezhetj¨ uk. G cs´ ucsainak list´ as sz´ınezésén a cs´ ucsok olyan sz´ınezését értj¨ uk, melynél minden v cs´ ucs sz´ıne benne van az L(v) list´ aban. A gráf k-lista sz´ınezhet˝ o, ha a cs´ ucsokra tetsz˝ oleges k hossz´ u list´ at megadva létezik olyan list´ as sz´ınezés mely a gráf jó sz´ınezését adja.


26

3.10. T´ etel (Erd˝ os, Rubin, Taylor, [4]). A p´ aros hossz´ u k¨ or¨ ok 2-lista sz´ınezhet˝ oek. 3.11. T´ etel. Minden a ´ltal´ anos feloszt´ asnak létezik er˝ os a ´ltal´ anos polikromatikus 6-sz´ınezése. Bizony´ıt´ as:

Tekints¨ unk egy A felosztást. Legyen G egy gráf A cs´ ucsain, melyben x és

y között pontosan akkor megy él, ha x és y ugyanannak az A-beli téglalapnak sarkai. A következ˝okben bel´ atjuk, hogy G-nek létezik jó 6-sz´ınezése, ugyanis G egy ilyen sz´ınezése az A felosztás egy er˝ os ´ altal´ anos polikromatikus 6-sz´ınezését adja meg. El˝osz¨ or G azon cs´ ucsait sz´ınezz¨ uk ki, melyekben 4 téglalap tal´ alkozott.

Ezeket a sz´ınezési sorrendben

sz´ınezz¨ uk ki u ´ gy, hogy az éppen sz´ınezend˝ o v cs´ ucsra tetsz˝ oleges olyan sz´ınt használhatunk, mely nem t˝ unik fel v sz´ınezett szomszédai között (megengedett sz´ın). Mivel egy éppen sz´ınezend˝ o cs´ ucsnak legfeljebb 4 sz´ınezett szomszédja van, ´ıgy 6 sz´ın biztosan elegend˝o lesz a jó sz´ınezéshez. Az ilyen cs´ ucsok sz´ınezése után legyen az algoritmus a következ˝o. Jelölje W a még ki nem sz´ınezett cs´ ucsok halmazát. Egy W -beli cs´ ucs olyan, hogy legfeljebb két A-beli téglalap sarka, azaz a W -beli cs´ ucsok foksz´ ama legfeljebb 6. Jelöle W 6 azon W -beli cs´ ucsok halmazát, melyek foksz´ ama G-ben pontosan 6, ´ıgy egy x ∈ W 6 cs´ ucs A-ban pontoson 2 téglalap sarka, és ezeknek nincsen másik közös sarkuk. Emiatt x-nek G-ben van két szomszédja, melyek egy A-beli téglalap ugyanazon oldal´ an helyekednek el. Legyen y, az x-hez közelebbi ezek köz¨ ul. Minden ilyen (x, y) cs´ ucsp´ arra ´ır´ any´ıtsuk meg az xy élt G-ben x-t˝ol y-ig. Erre egy példa látható a 3.7 ´ abr´ an. Nyilv´ anval´ o, hogy az xy élek egyikét sem ir´ any´ıtjuk meg visszafelé, tehát a W 6 -beli cs´ ucsok kifoka pontosan 1.

3.7. ábra. Az xy él ir´ any´ıtása Ezek után el˝ osz¨ or azokat a W 6 -beli cs´ ucsokat sz´ınezz¨ uk, melyek befoka 0. Legyen x egy ilyen cs´ ucs. Az x kifoka 1, ezért van sz´ınezetlen szomszédja, ami az jelenti, hogy van olyan sz´ın amivel x-t sz´ınezve nem romlik el a sz´ınezés¨ unk. Sz´ınezz¨ uk ki x-t egy ilyen megengedett sz´ınnel, majd vegy¨ uk ki W 6 -ból. Ismételj¨ uk ezt a lépést addig, am´ıg W 6 -ban nem marad 0 kifok´ u cs´ ucs. Ezek után minden W 6 -beli cs´ ucs kifoka és befoka is egyaránt 1. Így egyrészt minden W 6 -beli cs´ ucsnak van 2 sz´ınezetlen szomszédja, tehát minden cs´ ucsnak van egy legal´ abb 2 elem˝ u list´ aja a megengedett sz´ınekkel, másrészt a W 6 -beli cs´ ucsok gráfja ir´ any´ıtott körökre bomlik fel. Tekints¨ unk egy ilyen ir´ any´ıtott kört. Világos, hogy a körben a v´ızszintes és f¨ ugg˝oleges élek felváltva követik egym´ ast, ´ıgy az ilyen körök p´ aros hossz´ uak. A p´ aros hossz´ u körök 2-lista sz´ınezhet˝oek, ´ıgy meg tudjuk adni ezek egy jó sz´ınezését. Sz´ınezz¨ uk ennek megfelel˝oen W 6

¨ 3.3. Osszefoglal´ as, nyitott kérdések

27

cs´ ucsait. Ezek után már csak a W − W 6 cs´ ucsok sz´ınezetlenek. Ezek foksz´ ama azonban legfeljebb 5, teh´ at minden ilyen cs´ ucs sz´ınezésére létezik megengedett sz´ın.

3.3.

¨ Osszefoglal´ as, nyitott k´ erd´ esek

Az által´ anos felosztások esetében megmutattuk, hogy mind a gyenge által´ anos, mind az er˝os által´ anos polikromatikus k-sz´ınezés esetében elegend˝o a 4-hez minél közelebbi k értékeket vizsgálni. Megjegyezt¨ uk, hogy k ≤ 4 esetben ezek a sz´ınezések megegyeznek a téglalapfelosztásokn´ al definiált polikromatikus és er˝osen polikromatikus k-sz´ınezésekkel, és igazoltuk, hogy minden téglalap-feloszt´ asnak létezik er˝osen polikromatikus 4-sz´ınezése. L´ attuk, hogy létezik olyan ´ altal´ anos felosztás, melynek nem létezik gyenge által´ anos polikromatikus 4-sz´ınezése, de b´ armely ´ altal´ anos felosztásnak létezik gyenge által´ anos polikromatikus 3-, illetve 5-sz´ınezése. Er˝ os ´ altal´ anos polikromatikus sz´ınezés esetén a 2 illetve 6 értékekre igazoltuk ezeket. A gyenge ´ altal´ anos polikromatikus 3-, és 5-sz´ınezéskre adott moh´ o algoritmusok nem adnak minden esetben er˝ os polikromatikus sz´ınezést, ´ıgy az alábbi két kérdés egyel˝ore még nyitott. 3.1. Nyitott k´ erd´ es. Minden a ´ltal´ anos feloszt´ asnak létezik er˝ os a ´ltal´ anos polikromatikus 3-sz´ınezése? 3.2. Nyitott k´ erd´ es. Minden a ´ltal´ anos feloszt´ asnak létezik er˝ os a ´ltal´ anos polikromatikus 5-sz´ınezése?

4. fejezet

A polikromatikus sz´ınez´ es bonyolults´ aga A mostani fejezetben a polikromatikus sz´ınezés bonyolultságát vizsgáljuk. Polinomális id˝o alatt ellen˝ orizhet˝ o, hogy egy k-sz´ınezés polikromatikus-e, ´ıgy annak eld¨ ontése, hogy egy s´ıkgr´ af polikromatikusan k-sz´ınezhet˝o-e, N P-beli. A k = 1 eset triviális, hiszen minden s´ıkgr´ af polikromatikusan 1-sz´ınezhet˝o, azaz minden inputra igen választ kapunk. A fejezet további részében a k = 2, 3, 4 esetekre tér¨ unk ki. Az N P-nehézség bizony´ıtása során polinomiális visszavezetj¨ uk a feladatainkat már ismert N P-nehéz problém´ akra.

28

4.1. A polikromatikus 2-sz´ınezés bonyolultsága

4.1.

29

A polikromatikus 2-sz´ınez´ es bonyolults´ aga

A 3-SAT azon kielég´ıthet˝ o CNF-formulák nyelve, melyeknél minden kl´ oz legfeljebb 3 elem˝ u. Ha egy ϕ ∈ 3-SAT CNF-formula kielég´ıthet˝o u ´ gy, hogy egyik kl´ ozon bel¨ ul sem igaz minden literál, akkor azt mondjuk, hogy ϕ ∈ NAE-3-SAT (Not All Equal 3-SAT). Egy CNFformulát s´ıkbelinek nevez¨ unk, ha a literál-klóz incidenciagráfja s´ıkbarajzolhat´ o lesz, ha benne a negálatlan literálokat körbek¨ otj¨ uk, és változ´ oknak megfelel˝o negált és nagálatlan literálokat összek¨ otj¨ uk. A NAE-3-SAT-beli s´ıkbeli CNF-formulák nyelvét PLANAR-NAE-3-SAT-tal jelölj¨ uk. Az al´ abbi tételt Bernard Moret bizony´ıtotta. 4.1. T´ etel (Moret, [11]). PLANAR-NAE-3-SAT ∈ P. Nevezz¨ unk egy CNF-formulát s´ıkbeli∗ -nak, ha a literál-klóz incidenciagráfja s´ıkbarajzolhat´ o. A NAE-SAT-beli s´ıkbeli CNF-formulák nyelvét PLANAR∗ -NAE-SAT-tal jelölj¨ uk. A 4.1 Tétel bizony´ıt´ as´ aban szerepl˝ o visszavezetés s´ıkbeli∗ CNF-formulákra is m˝ uködik, ezért igaz, hogy PLANAR∗ -NAE-3-SAT ∈ P. 4.2. T´ etel. Létezik polinomi´ alis algoritmus annak eld¨ ontésére, hogy egy adott s´ıkgr´ af polikromatikusan 2-sz´ınezhet˝ o-e. Bizony´ıt´ as (v´ azlat): Azt fogjuk kihaszn´ alni, hogy egy s´ıkgr´ af cs´ ucsainak 2-sz´ınezése pontosan akkor polikromatikus, ha egyik lap sem monokromatikus. Tekints¨ unk egy G s´ıkgr´ afot. Konstru´ aljunk G-hez egy ϕG s´ıkbeli∗ CNF-formulát a következ˝oképpen. Vegy¨ unk fel G minden cs´ ucs´ ahoz egy változ´ ot, és az egy lapon lév˝ o cs´ ucsok változ´ oi alkossák a kl´ ozokat. A 4.1 (a,b) ´ abr´ an láthatunk egy péld´ at, ahol a CNF-formula literál-klóz incidenciagráfj´ at is ábr´ azoljuk. Ha G polikromatikusan 2-sz´ınezhet˝o, akkor tekints¨ uk egy ilyen sz´ınezését.

4.1. ábra. G, ϕG , ϕ0G

Az egyik sz´ınnel sz´ınezett cs´ ucsok változ´ oi legyen igazak, a másik sz´ınnel sz´ınezett cs´ ucsok változ´ oi legyenek hamisak. Ezzel ϕG minden kl´ ozán bel¨ ul lesz igaz és hamis változ´ o is, tehát ϕG ∈ PLANAR∗ -NAE-SAT. M´ asrészt, ha ϕG ∈ PLANAR∗ -NAE-SAT, akkor sz´ınezz¨ uk ki az egyik sz´ınnel azokat a cs´ ucsokat, melyeknek a változ´ ojuk igaz, a t¨ obbi cs´ ucsot pedig sz´ınezz¨ uk a másik sz´ınnel. Ezzel G polikromatikus 2-sz´ınezését kapjuk. Így annak eld¨ ontése, hogy G s´ıkgr´ af polikromatikusan 2-sz´ınezhet˝o-e ekvivalens annak eld¨ ontésével, hogy ϕG s´ıkbeli∗ CNF-formula PLANAR∗ -NEA-SAT-beli-e. Ezt követ˝oen tekints¨ uk ϕG egy n > 3 méret˝ u k kl´ ozját. A k kl´ ozot bontsuk kétfelé. Egy


30

u ´ j x literál felvételével k-t egy 3 és egy n − 1 méret˝ u k1 , k2 kl´ ozra cserélj¨ uk a 4.1 (b,c) ábr´ anak megfelel˝oen. Az x literál k1 -ben negálatlanul, k2 -ben negálva szerepeljen. Ezt az eljárást folytassuk addig, m´ıg minden kl´ oz legfeljebb 3 méret˝ u lesz, ´ıgy egy ϕ0G s´ıkbeli∗ CNF-formulát kapunk. M´ asrészt ha ϕG ∈ PLANAR∗ -NAE-SAT, akkor ϕ0G ∈ PLANAR∗ NAE-3-SAT. Ugyanis amikor egy kl´ ozt kétfelé bontunk az egyik u ´ j kl´ ozban biztosan lesz igaz változ´ o, a másikban pedig ha nincs, akkor a felvett literált választhatjuk u ´ gy, hogy az igaz legyen. S˝ ot, ha ϕ0G ∈ PLANAR∗ -NAE-3-SAT, akkor ϕG ∈ PLANAR∗ -NAE-SAT. Hiszen ha egyes´ıtj¨ uk a szétbontott kl´ ozokat nem fordulhat el˝o, hogy minden változ´ o logikai értéke egyforma legyen, mert a megfelel˝o x és ¬x változ´ ok logikai értéke k¨ ulönb¨ oz˝o. Így annak eld¨ ontése, hogy ϕG PLANAR∗ -NAE-beli-e ekvivalens annak eld¨ ontésével, hogy ϕ0G PLANAR∗ -NAE-3-SAT-beli-e. ¨ Osszegezve: annak eld¨ ontése, hogy G polikromatikusan 2-sz´ınezhet˝o-e ekvivalens annak eld¨ ontésével, hogy ϕ0G PLANAR∗ -NAE-3-SAT-beli-e, melyr˝ ol tudjuk, hogy P-ben van.

4.2.


Egyszer˝ u s´ıkgr´ af j´ o 3-sz´ınezhet˝oségét fogjuk polinomálisan visszavezetni a polikromatikus 3-sz´ınezhet˝oségére. Ehhez az al´ abbi tételt fogjuk felhasználni. 4.3. T´ etel (Stockmeyer, [13]). Annak eld¨ ontése, hogy egy egyszer˝ u s´ıkgr´ af j´ ol 3-sz´ınezhet˝ o-e, N P-nehéz. 4.4. T´ etel. Annak eld¨ ontése, hogy egy egyszer˝ u s´ıkgr´ af polikromatikusan 3-sz´ınezhet˝ o-e, N P-teljes. Bizony´ıt´ as: M´ ar csak azt kell bel´ atnunk, hogy a feladat N P-nehéz. Legyen adott egy G egyszer˝ u s´ıkgr´ af. Polinomiális id˝o alatt konstru´ alunk egy G0 egyszer˝ u s´ıkgr´ afot u ´ gy, hogy G0 pontosan akkor j´ ol 3-sz´ınezhet˝o, ha G polikromatikusan 3-sz´ınezhet˝o. Minden uv ∈ E(G) élhez vegy¨ unk fel egy yuv cs´ ucsot valamely olyan lap belsejében, melynek uv hat´ ara, majd köss¨ uk ¨ ossze u-val és v-vel. Ekkor minden E(G)-beli él egy h´ aromsz¨ ognek oldala. Ezut´ an minden f ∈ F (G) lapnak válasszuk ki egy x cs´ ucs´ at, majd vegy¨ unk fel egy xf cs´ ucsot f belsejében és köss¨ uk o¨ssze x-el. Egy példa látható a 4.2 ábr´ an. Az ´ıgy kapott G0 gráf egyszer˝ u s´ıkgr´ af. Tekints¨ uk (ha létezik) G egy j´ o 3-sz´ınezését. Ekkor egyik uv ∈ E(G) él sem monokromatikus, ´ıgy G0 -ben az yuv cs´ ucsot az u és v sz´ıneit˝ ol eltér˝o harmadik sz´ınnel sz´ınezve minden h´ arom méret˝ u lap polikromatikus lesz. Egy f ∈ F (G) lapot pedig az xf cs´ ucs sz´ınezésével tehet¨ unk polikromatikussá. Ezzel megadtuk G0 egy polikromatikus 3-sz´ınezését. M´ asrészt tekints¨ uk (ha létezik) G0 egy polikromatikus 3-sz´ınezését. Ekkor természetesen G0 minden h´ arom méret˝ u lapja is polikromatikus, ebb˝ol adódóan egyik uv ∈ E(G) él sem monokromatikus, tehát G j´ o sz´ınezését kaptuk (esetleg 2 sz´ınnel). Tehát G pontosan akkor jól 3-sz´ınezhet˝o,


31

4.2. ábra. G0 konstrukciója

ha G0 polikromatikusan 3-sz´ınezhet˝o.

4.3.


A k = 4 esethez két problém´ at fogalmazunk meg, mégpedig kétszeresen összef¨ ugg˝ u gráfokra. Ennek az egyik oka az, hogy egy s´ıkgr´ af akkor és csak akkor polikromatikusan k-sz´ınezhet˝o, ha minden kétszeresen ¨ osszef¨ ugg˝ o komponense is az. R´ aadásul mélységi kereséssel a maximális, kétszeresen ¨ osszef¨ ugg˝ o komponens polinomiális id˝o alatt megtalálható. M´ asrészt egy kétszeresen ¨ osszef¨ ugg˝ o s´ıkgr´ af minden lapja egy kör, és ez megk¨ onny´ıti vizsgálatainkat. Legyen L néhány pozit´ıv egész sz´ amot tartalmaz´ o halmaz. Tekints¨ uk a következ˝o 2 problémát: L-PLANE-PROPER-k-COLORABILITY: Adott: G kétszeresen ¨ osszef¨ ugg˝ o s´ıkgr´ af, ahol G b´ armely lapjának mérete L-beli. Kérdés: Létezik-e G cs´ ucsainak j´ o k-sz´ınezése? L-PLANE-POLY-k-COLORABILITY: Adott: G kétszeresen ¨ osszef¨ ugg˝ o s´ıkgr´ af, ahol G b´ armely lapjának mérete L-beli. Kérdés: Létezik-e G cs´ ucsainak polikromatikus k-sz´ınezése? 4.5. T´ etel (Alon et al. [1]). L-PLANE-PROPER-3-COLORABILITY... (i) ... P-ben van, ha L = {2, 3}. (ii) ... trivi´ alis, ha L kiz´ ar´ olag p´ aros sz´ amokat tartalmaz. (iii) ... N P-teljes, ha {3, s} ⊆ L, ahol s ≥ 4. (iv) ... N P-teljes, ha {4, t} ⊆ L, ahol t ≥ 5 p´ aratlan. 4.6. T´ etel (Alon et al. [1]). L-PLANE-POLY-3-COLORABILITY... (i) ... P-ben van, ha L = {2, 3, }. (ii) ... trivi´ alis, ha L kiz´ ar´ olag p´ aros sz´ amokat tartalmaz. (iii) ... N P-teljes, ha {3, s} ⊆ L, ahol s ≥ 4.


32

(iv) ... N P-teljes, ha {4, t} ⊆ L, ahol t ≥ 5 p´ aratlan. (v) ... trivi´ alis, ha L ⊆ {6, . . .}. 4.7. T´ etel. Annak eld¨ ontése, hogy egy egyszer˝ u s´ıkgr´ af polikromatikusan 4-sz´ınezhet˝ o-e, N P-teljes. Bizony´ıt´ as: Most is csak azt kell belátnunk, hogy a feladat N P-nehéz. Legyen G egyszer˝ u s´ıkgr´ af. Minden uv ∈ E(G) élhez vegy¨ unk fel egy xuv cs´ ucsot, és az uv élt helyettes´ıts¨ uk az u − xuv − v u ´ ttal. Ezut´ an minden f ∈ F (G) lap belsejében vegy¨ unk fel egy vf cs´ ucsot és köss¨ uk ¨ ossze f cs´ ucsaival. Az ´ıgy kapott G0 gráf egyszer˝ u s´ıkgr´ af és minden lapjának mérete pontosan 4. Egy példa látható a 4.3 ábr´ an. Megmutatjuk, hogy G pontosan akkor

4.3. ábra. G0 konstrukciója

jól 3-sz´ınezhet˝o, ha G0 polikromatikusan 4-sz´ınezhet˝o. Tekints¨ uk (ha létezik) G egy χ j´ o 3-sz´ınezését az {1, 2, 3} sz´ınekkel. Ezt a χ sz´ınezést egész´ıtj¨ uk ki G0 sz´ınezésévé a következ˝oképpen. Minden vf (f ∈ F (G)) cs´ ucsot sz´ınezz¨ uk ki a 4-es sz´ınnel. Mivel χ j´ o 3-sz´ınezés, ezért egyik e ∈ E(G) él sem monokromatikus, ´ıgy xuv -t (uv ∈ E(G)) a χ(u), χ(v), 4 sz´ınekt˝ ol eltér˝o negyedik sz´ınnel sz´ınezve, minden f ∈ F (G0 ) lap polikromatikusan 4-sz´ınezett lesz. A másik ir´ anyhoz tekints¨ uk (ha létezik) G0 egy χ0 polikromatikus 4-sz´ınezését. Legyen vf valamely f laphoz felvett cs´ ucs. Az által´ anoss´ ag megszor´ıtása nélk¨ ul feltehetj¨ uk, hogy χ0 (vf ) = 4. Ekkor minden olyan uv ∈ E(G) élre, mely f -et határolja az u, xuv , v cs´ ucsok az 1, 2, 3 sz´ınekkel vannak sz´ınezve, ´ıgy minden vg cs´ ucsra, melyet valamely f -el szomszédos g ∈ F (G) laphoz vett¨ unk fel χ0 (vg ) = 4. Ezt a gondolatmenetet ”lapr´ ol-lapra lépve” megismételhetj¨ uk, és mivel G0 du´ alis gráfja összef¨ ugg˝o, ´ıgy minden f 0 ∈ F (G)-re χ0 (vf 0 ) = 4, és minden más w ∈ G0 cs´ ucsra χ0 (w) 6= 4. Tehát ha χ0 -t lesz˝ uk´ıtj¨ uk G-re (χ), akkor G egy 3-sz´ınezését kapjuk. M´ asrészt χ0 polikromatikus 4-sz´ınezés, ezért minden uv élre, mely ucsok k¨ ulönb¨ oz˝o sz´ın˝ uek, azaz χ(u) 6= χ(v). valamely f ∈ F (G) lap hat´ ara, az u, v, xuv , fv cs´ Így χ j´ o 3-sz´ınezése G-nek.

4.4. Egyéb eredmények, nyitott kérdések

4.4.

33

Egy´ eb eredm´ enyek, nyitott k´ erd´ esek

Az el˝oz˝o fejezetben megmutattuk, hogy nem minden által´ anos felosztásnak létezik gyenge által´ anos polikromatikus 4-sz´ınezése. A következ˝o tétel igazolható. 4.8. T´ etel (Gerbner et al. [6]). Annak eld¨ ontése, hogy egy a ´ltal´ anos feloszt´ asnak létezike gyenge a ´ltal´ anos polikromatikus 4-sz´ınezése, N P-teljes. A 4.3 szakaszban definiáltuk az L-PLANE-POLY-3-COLORABILITY problém´ at. Az egyetlen eset amit egyel˝ ore nem tudtunk lefedni a 4.6 Tételben, amikor L legkisebb eleme 5. Ha fennállna, hogy p(5) ≥ 3, akkor az alábbi probléma triviális lenne. 4.1. Nyitott k´ erd´ es. Mi a bonyolults´ aga az {5, . . .}-PLANE-POLY-3-COLORABILITY problém´ anak? A 4.1, 4.2, 4.3 szakaszokban a polikromatikus k-sz´ınezés bonyolultságát vizsgáltuk a k = 1, 2, 3, 4 esetekben. 4.2. Nyitott k´ erd´ es. A PLANE-POLY-k-COLORABILITY probléma N P-teljes minden r¨ ogz´ıtett k ≥ 5-re?

Irodalomjegyz´ ek [1] N. Alon, R. Berke, K. Buchin, M. Buchin, P. Csorba, S. Shannigrahi, B. Speckmann, P. Zumstein: Polychromatic Colorings of Plane Graphs, Discrete & Computational Geometry (2009) pp. 421-442 [2] P. Bose, T. Shermer, G. Toussaint, B. Zhu: Guarding Polyhedral Terrains, Comput. Geom. (1997) pp. 173-185 [3] D. Dimitrov, E. Horev, R. Krakovski: Polychromatic colorings of rectangular partitions, Discrete Mathematics (2009) pp. 2957-2960 [4] P. Erd˝ os, A. L. Rubin, H. Taylor: Choosability in graphs, Congr. Numer. 26 (1979) pp. 125-157 [5] S. Fisk: A short proof of Chv´ atal’s watchman theorem, J. Comb. Theory, Ser. B (1978) [6] D. Gerbner, B. Keszegh, N. Lemons, C. Palmer, D. P´ alvölgyi, B. Patkós: Polychromatic colorings of arbitrary rectangular partitions, Discrete Mathematics (2010) pp. 21-30 [7] B. Guenin: Packing t-joins and edge coloring in planar graphs, Manuscript [8] E. Horev, M. J. Katz, R. Krakovski, M. L¨ offler: Polychromatic 4-coloring of guillotine subdivisions, Inf. Process. Lett. (2009) pp. 690-694 [9] J. Kahn, M. Klawe, D. Kleitman: Traditional galleries require fewer watchmen, SIAM J. Algebraic and Discrete Methods 4 (1983) pp. 194-206 [10] B. Keszegh: Polychromatic Colorings of n-dimensional Guillotine-Partitions, COCOON (2008) pp. 110-118 [11] B.M.E. Moret: Planar NAE3SAT is in P, SIGACT News 19(2) (1988) pp. 51-54 [12] J. O’Rourke: Art Gallery Theorems and Algorithms, Oxford University Press (1987) [13] L. Stockmeyer: Planar 3-colorability is polynomial complete, SIGACT News 5(3) (1973) pp. 19-25 [14] J. Urrutia: Art Gallery and Illumination Problems, Handbook of Computational Geometry (2000) pp. 973-1027

34

Természettudományi kar. szakdolgozat Matematika BSc Alkalmazott matematikus szakirány ELTE TTK

Recommend Documents