7
Barevnost a dalˇs´ı tˇ eˇ zk´ e probl´ emy
Pro motivaci t´eto lekce se pod´ıv´ ame hloubˇeji do historie poˇc´ atk˚ u graf˚ u v matematice. Kromˇe slavn´eho probl´emu sedmi most˚ u v Kr´ alovci (dneˇsn´ım Kaliningradˇe) je za dalˇs´ı historick´ y miln´ık azej´ıc´ı z poloviny 19. stolet´ı: Kolik v´ yvoje teorie graf˚ u povaˇzov´ an probl´em ˇctyˇr barev poch´ nejm´enˇe barev je tˇreba pouˇz´ıt na obarven´ı politick´e mapy pro rozliˇsen´ı sousedn´ıch st´ at˚ u? Na rozd´ıl od sedmi most˚ u, probl´em ˇctyˇr barev z˚ ustal nevyˇreˇsen´ y po v´ıce neˇz 100 let a stimuloval rozvoj skoro vˇsech modern´ıch oblast´ı teorie graf˚ u. Nˇekteˇr´ı vˇsak kladou prapoˇc´ atky graf˚ u v matematice daleko pˇred Eulerov´ ymi sedmi mosty ˇci probl´emem ˇctyˇr barev, aˇz ke stˇredovˇek´e ot´ azce, zda lze ˇsachov´ ym konˇem obej´ıt celou ˇsachovnici bez opakov´ an´ı. Tato ot´ azka vede v modern´ım pojet´ı k dalˇs´ımu zaj´ımav´emu a obt´ıˇzn´emu probl´emu tzv. Hamiltonovsk´e kruˇznice v grafu. . . 2
Struˇ cn´ y pˇrehled lekce • Definice barevnosti grafu, z´akladn´ı vlastnosti. • Varinaty probl´emu barven´ı. • Dalˇs´ı obt´ıˇzn´e“ probl´emy jako Hamiltonovsk´a kruˇznice. ” • Algoritmick´a sloˇzitost (NP-´uplnost) z´akladn´ıch grafov´ych probl´em˚ u. Petr Hlinˇen´ y, FI MU Brno
1
FI: MA010: Barevnost a dalˇs´ı
7.1
Barevnost grafu
Nejprve si uved’me pojem barevnosti – pˇredstavme si, ˇze hrany grafu n´am ˇr´ıkaj´ı, ˇze jejich koncov´e vrcholy mus´ı b´yt barevnˇe odliˇsen´e (tˇreba proto, ˇze reprezentuj´ı sousedn´ı st´aty, nebo proto, ˇze jinak jsou si pˇr´ıliˇs podobn´e a je tˇreba je jinak rozl´ıˇsit, atd).2Samozˇrejmˇe bychom mohli kaˇzd´emu vrcholu grafu d´at jinou barvu, ale k ˇcemu by pak takov´y probl´em byl? My bychom chtˇeli pouˇz´ıt barev celkem co nejm´enˇe. 2 Definice: Obarven´ım grafu G pomoc´ı k barev mysl´ıme libovoln´e zobrazen´ı c : V (G) → {1, 2, . . . , k} takov´e, ˇze kaˇzd´e dva vrcholy spojen´e hranou dostanou r˚ uzn´e barvy, tj. c(u) 6= c(v) pro vˇsechny {u, v} ∈ E(G). Definice 7.1. Barevnost grafu G je nejmenˇs´ı ˇc´ıslo χ(G) pro kter´e existuje obarven´ı grafu G pomoc´ı χ(G) barev.
2
ˇ ısla 1, 2, . . . , k z pˇredchoz´ı definice tak naz´yv´ame barvami vrchol˚ C´ u (je to pohodlnˇejˇs´ı, neˇz popisovat barvy bˇeˇzn´ymi jm´eny jako b´ıl´a, ˇcerven´a, atd). Pozn´ amka: Uvˇedomme si, ˇze barevnost lze definovat pouze pro graf bez smyˇcek, protoˇze oba konce smyˇcky maj´ı vˇzdy stejnou barvu a nic s t´ım nenadˇel´ ame. Petr Hlinˇen´ y, FI MU Brno
2
FI: MA010: Barevnost a dalˇs´ı
Lema 7.3. Necht’ G je jednoduch´y graf (bez smyˇcek) na n vrcholech. Pak χ(G) ≤ n a rovnost nast´av´a pr´avˇe kdyˇz G ≃ Kn je ´ upln´y graf. 2 D˚ ukaz: Staˇc´ı kaˇzd´y vrchol obarvit jinou barvou a m´ame skuteˇcn´e obarven´ı n barvami dle definice. Nav´ıc pokud nˇekter´a dvojice u, v vrchol˚ u nen´ı spojen´a hranou, m˚ uˇzeme volit lepˇs´ı obarven´ı c(u) = c(v) = 1 a zbyl´e vrcholy r˚ uzn´ymi barvami 2, 3, . . . , n − 1, tj. pak χ(G) < n. 2
Petr Hlinˇen´ y, FI MU Brno
3
FI: MA010: Barevnost a dalˇs´ı
Pˇr´ıklad 7.4. Vrat’me se k pˇr´ıkladu barven´ı“ mapy z u ´vodu lekce a ukaˇzme si, jak mapy ” souvisej´ı s grafy a jejich barevnost´ı.
1
2
3
b
b s
g
c
1 3
4
c
g
s
s sh
h d
2
1
e
d s
f
s e
a
s f
a s
2
Jednotliv´e oblasti na mapˇe (pˇredpokl´ ad´ ame, ˇze kaˇzd´ y st´ at m´ a souvisl´e u ´zem´ı, tj. st´ aty = oblasti) prohl´ as´ıme za vrcholy naˇseho grafu a sousedn´ı dvojice st´ at˚ u spoj´ıme hranami. Nezapomeˇ nme, ˇze sousedn´ı“ znamen´ a sd´ılen´ı cel´eho u ´seku hranice, ne jen jednoho rohu. 2 ” Pˇri troˇse snahy tak´e najdeme lepˇs´ı obarven´ı uveden´e mapy vyuˇz´ıvaj´ıc´ı pouh´ ych tˇr´ı barev: 1
2
1 s
3
2
3
s
s s1
1 3
1
3 s
2
2
2 s
s 1
s 2 2
Petr Hlinˇen´ y, FI MU Brno
4
FI: MA010: Barevnost a dalˇs´ı
Vˇ eta 7.5. Nepr´azdn´y graf G m´a barevnost 1 pr´avˇe kdyˇz nem´a ˇz´adn´e hrany. G m´a barevnost ≤ 2 pr´avˇe kdyˇz nem´a ˇz´adnou kruˇznici lich´e d´elky jako podgraf.
2
D˚ ukaz: Pokud graf nem´a hrany, m˚ uˇzeme vˇsechny vrcholy obarvit stejnou barvou 1. Naopak pokud maj´ı vˇsechny vrcholy stejnou barvu, nem˚ uˇze graf m´ıt ˇz´adnou hranu.2 Druh´a ˇc´ast: Na jednu stranu, lichou kruˇznici nelze obarvit dvˇema barvami, viz obr´azek. Na druhou stranu si pˇredstavme, ˇze zvol´ıme libovoln´y vrchol v grafu G s barvou 1 a ostatn´ı vrcholy obarv´ıme takto: Vrcholy, jejichˇz vzd´alenost od v je lich´a, obarv´ıme 2. Vrcholy, jejichˇz vzd´alenost od v je sud´a, obarv´ıme 1. v s1 s2
2 s ?? s
1 s
s1
2 s 1 s
s2
s1 s2 s 12
Pokud bychom tak z´ıskali tˇreba dva vrcholy spojen´e hranou f v sud´e vzd´ alenosti od v, z´ısk´ ame uzavˇren´ y sled S lich´e d´elky pˇres f a v. Stejnˇe tak pro dva vrcholy v lich´e vzd´ alenosti. Ponech´ ame-li ze sledu S ty hrany, kter´e se opakuj´ı lich´ y poˇcet kr´ at, dostaneme Eulerovsk´ y podgraf T lich´eho poˇctu hran. Jak jiˇz v´ıme (Odd´ıl 4.1), T pak obsahuje kruˇznici a tud´ıˇz jej lze induktivnˇe sestrojit jako hranovˇe-disjunktn´ı sjednocen´ı kruˇznic. Avˇsak sjednocen´ı kruˇznic sud´e d´elky nevytvoˇr´ı T lich´e velikosti, spor. Proto naˇse obarven´ı za dan´ ych pˇredpoklad˚ u nem˚ uˇze d´ at stejnou barvu sousedn´ım vrchol˚ um, a tud´ıˇz dvˇe barvy staˇc´ı. 2 Petr Hlinˇen´ y, FI MU Brno
5
FI: MA010: Barevnost a dalˇs´ı
Hladov´ e obarvov´ an´ı Definice: Graf G je k-degenerovan´y, pokud kaˇzd´y podgraf G obsahuje vrchol stupnˇe nejv´yˇse k. Pˇr´ıkladem k-degenerovan´eho grafu je kaˇzd´ y graf stupnˇe nejv´ yˇse k, ale na druhou stranu kdegenerovan´e grafy mohou m´ıt vysok´e stupnˇe. (Nestaˇc´ı vˇsak m´ıt jen n´ızk´ y nejmenˇs´ı stupeˇ n!) 2
Vˇ eta 7.6. Kaˇzd´y k-degenerovan´y graf lze spr´avnˇe hladovˇe obarvit k + 1 barvami.
2
D˚ ukaz: Jelikoˇz graf G je k-degenerovan´y, vybereme libovoln´y jeho vrchol v1 stupnˇe nejv´yˇse k a rekurzivn´ı aplikac´ı tohoto postupu obarv´ıme podgraf G − v1 , kter´y je podle definice tak´e k-degenerovan´y. Nakonec si vˇsimneme, ˇze ≤ k soused´e vrcholu v1 dostanou nejv´yˇse k r˚ uzn´ych barev, takˇze v1 dobarv´ıme zbylou barvou. 2 D˚ uleˇzit´e aplikace t´eto vˇety uvid´ıme v pˇr´ıˇst´ı lekci, avˇsak jedno zaj´ımav´e zes´ılen´ı (Brooksovu vˇetu) si uvedeme nyn´ı:
Petr Hlinˇen´ y, FI MU Brno
6
FI: MA010: Barevnost a dalˇs´ı
Vˇ eta 7.7. Necht’ G je souvisl´y jednoduch´y graf maxim´aln´ıho stupnˇe k ≥ 2. Pak χ(G) ≤ k aˇz na pˇr´ıpady, kdy G je ´ upln´y graf nebo lich´a kruˇznice. D˚ ukaz (n´aznak): Pro k = 2 plyne tvrzen´ı z Vˇety 7.5. Necht’ tedy k ≥ 3. V jednom smˇeru je jasn´e, ˇze χ(Kk+1 ) = k + 1. Naopak tedy pˇredpokl´adejme, ˇze G nen´ı ´upln´y. Z´aroveˇ n se omezme jen na pˇr´ıpad, ˇze G m´a vˇsechny stupnˇe rovn´e k, nebot’ jinak lze aplikovat postup z Vˇety 7.6. 2 • Prvn´ım krokem nahl´edneme, ˇze pak G obsahuje dva nespojen´e vrcholy u, v se spoleˇcn´ym sousedem w. Pokud ale je graf G−{u, v} nesouvisl´y, pak graf pˇr´ısluˇsnˇe rozdˇel´ıme a indukc´ı po ˇc´astech obarv´ıme. 2 • Pˇridejme tedy pˇredpoklad, ˇze G−{u, v} je souvisl´y. Druh´ym krokem nahl´edneme, ˇze graf H vznikl´y z G − w ztotoˇznˇen´ım u s v do jednoho vrcholu je (k − 1)degenerovan´y. 2 • Tud´ıˇz graf H hladovˇe obarv´ıme k barvami podle Vˇety 7.6. Po opˇetovn´em rozpo” jen´ı“ vrchol˚ u u, v z´ısk´ame obarven´ı G − w k barvami takov´e, ˇze u, v maj´ı stejnou barvu. Nyn´ı w m´a v sousedstv´ı nejv´yˇse k − 1 barev a G cel´y obarv´ıme. 2
Petr Hlinˇen´ y, FI MU Brno
7
FI: MA010: Barevnost a dalˇs´ı
Grafy vysok´ e barevnosti Ke spr´avn´emu pochopen´ı barevnosti grafu je nezbytn´e se zamyslet, kter´e grafy maj´ı vysokou barevnost. Jedn´a se napˇr´ıklad o grafy obsahuj´ıc´ı velk´e kliky (´upln´e podgrafy). Je to vˇsak vˇse? 2 Nen´ı! Lze nal´ezt grafy s libovolnˇe vysokou barevnost´ı neobsahuj´ıc´ı ani troj´uheln´ıky. Tvrzen´ı 7.8. (Mycielski) Graf z´ıskan´y z grafu G n´asleduj´ıc´ı konstrukc´ı (viz obr´azek) m´a barevnost χ(G) + 1 a neobsahuje troj´ uheln´ıky, pokud je neobsahuje ani G.
2
Nejobecnˇeji lze ˇr´ıci n´asleduj´ıc´ı pˇrekvapiv´e tvrzen´ı: Vˇ eta 7.9. (Erd˝ os) Pro kaˇzd´a c, r > 0 existuje graf s barevnost´ı alespoˇn c a neobsahuj´ıc´ı kruˇznice kratˇs´ı neˇz r. Petr Hlinˇen´ y, FI MU Brno
8
FI: MA010: Barevnost a dalˇs´ı
7.2
Variace na barevnost a jin´ e
Definice 7.10. Hranov´ a barevnost grafu G. Hled´ame obarven´ı ce (E(G)) → {1, 2, . . . , k} takov´e, ˇze ˇz´adn´e dvˇe hrany se spoleˇcn´ym vrcholem nedostanou stejnou barvu. Nejmenˇs´ı moˇzn´y poˇcet barev k, pro kter´e hranov´e obarven´ı existuje, se naz´yv´a hranov´a barevnost χe (G) grafu. 2 Na rozd´ıl od bˇeˇzn´e barevnosti um´ıme hranovou barevnost docela ostˇre aproximovat. Vˇ eta 7.11. (Vizing) Pro kaˇzd´y jednoduch´y graf plat´ı ∆(G) ≤ χe (G) ≤ ∆(G) + 1. Plat´ı, ˇze vˇetˇsina graf˚ u splˇ nuje ∆(G) = χe (G). Um´ıte jednoduˇse sestrojit (a dok´ azat) pˇr´ıklady pro druh´ y pˇr´ıpad?
Probl´em pˇresn´eho urˇcen´ı hranov´e barevnosti grafu vˇsak st´ale z˚ ust´av´a algoritmicky velmi obt´ıˇzn´y a tak´e ´uzce souvis´ı s probl´emem ˇctyˇr barev.
Petr Hlinˇen´ y, FI MU Brno
9
FI: MA010: Barevnost a dalˇs´ı
Definice 7.12. V´ ybˇ erov´ a barevnost grafu G. (k-prvkov´e Je d´an graf G spolu s pˇriˇrazen´ymi seznamy barev“ L : V (G) → N k ” podmnoˇziny). Nyn´ı hled´ame obarven´ı cch (V (G)) → takov´e, ˇze ˇz´adn´e dva sousedn´ı vrcholy nedostanou stejnou barvu a nav´ıc cch (v) ∈ L(v) pro kaˇzd´y vrchol v.
N
Nejmenˇs´ı moˇzn´a d´elka k seznam˚ u barev, pro kterou v´ybˇerov´e obarven´ı vˇzdy existuje (tj. pro kaˇzdou moˇznou takovou volbu seznam˚ u), se naz´yv´a v´ybˇerov´a barevnost ch(G) grafu. 2 V´ybˇerov´a barevnost m˚ uˇze (kupodivu!) b´yt libovolnˇe vzd´alena“ bˇeˇzn´e barevnosti. ” Tvrzen´ı 7.13. Pro kaˇzd´e k nalezneme bipartitn´ı graf s v´ybˇerovou barevnost´ı vˇetˇs´ı neˇz k. 2 Fakt: Hranov´a v´ybˇerov´a barevnost ´ upln´ych bipartitn´ıch graf˚ u ´uzce souvis´ı se zn´am´ym u. probl´emem latinsk´ych obd´eln´ık˚
Petr Hlinˇen´ y, FI MU Brno
10
FI: MA010: Barevnost a dalˇs´ı
Hamiltonovsk´ e grafy Definice: Kruˇznice C obsaˇzen´a v grafu G se naz´yv´a Hamiltonovsk´a, pokud C proch´az´ı vˇsemi vrcholy G. Obdobnˇe mluv´ıme o Hamiltonovsk´e cestˇe P v G, pokud cesta P ⊂ G proch´az´ı vˇsemi vrcholy G. Graf G je Hamiltonovsk´y, pokud obsahuje Hamiltonovskou kruˇznici.
2
Moˇzn´a to zn´ı pˇrekvapivˇe, ale i probl´em Hamiltonovsk´e kruˇznice ´uzce souvisel s ˇreˇsen´ım probl´emu ˇctyˇr barev. To je vˇsak mimo r´amec naˇseho textu. Vˇ eta 7.14. (Dirac) Kaˇzd´y graf na n ≥ 3 vrcholech s minim´aln´ım stupnˇem ≥ n/2 je Hamiltonovsk´y. 2 D˚ ukaz (n´aznak): Necht’ P je nejdelˇs´ı cesta v grafu G s vrcholy po ˇradˇe u0 , u1 , . . . , uk . Podle jej´ı maximality leˇz´ı kaˇzd´y soused u0 i uk na P . Pak existuje 0 < i < k takov´e, ˇze u0 ui+1 ∈ E(G) a z´aroveˇ n uk ui ∈ E(G). Pak u0 ui+1 P uk ui P tvoˇr´ı kruˇznici v G a snadno plyne, ˇze se jedn´a o Hamiltonovskou kruˇznici. 2
Petr Hlinˇen´ y, FI MU Brno
11
FI: MA010: Barevnost a dalˇs´ı
7.3
N P-´ uplnost grafov´ ych probl´ em˚ u
Definice sloˇzitostn´ı tˇr´ıdy N P se t´ yk´ a v´ yhradnˇe rozhodovac´ıch probl´em˚ u (s ANO/NE“ ” odpovˇed´ı). D´ a se neform´ alnˇe ˇr´ıci, ˇze probl´em patˇr´ı do tˇr´ıdy N P, pokud jeho odpovˇed’ ANO lze prok´ azat (ve smyslu uhodnout a ovˇeˇrit“) v´ ypoˇctem, kter´ y bˇeˇz´ı v polynomi´ aln´ım ˇcase. ” N P-´ upln´e probl´emy jsou zhruba ˇreˇceno ty, kter´e ve tˇr´ıdˇe N P maj´ı nejvyˇsˇs´ı obt´ıˇznost ˇreˇsen´ı. Od jednoho N P-´ upln´eho probl´emu A se dostaneme k jin´emu B tzv. polynomi´ aln´ım pˇrevodem: Uk´ aˇzeme, jak bychom ze zn´ am´eho postupu ˇreˇsen´ı B efektivnˇe nalezli ˇreˇsen´ı (libovoln´e instance) A. 2
Nyn´ı si uk´aˇzeme vhodn´ymi pˇrevody, ˇze onˇech nejobt´ıˇznˇejˇs´ıch“ (N P-´upln´ych) ” probl´em˚ u je v teorii graf˚ u mnoho, bohuˇzel by se dalo ˇr´ıci vˇetˇsina. To ostatnˇe ukazuje, proˇc jsme zat´ım v praxi tak m´alo ´ uspˇeˇsn´ı pˇri poˇc´ıtaˇcov´em ˇreˇsen´ı mnoh´ych praktick´ych probl´em˚ u – pˇresn´e a efektivn´ı ˇreˇsen´ı N P-´ upln´ych ´ uloh se totiˇz vˇseobecnˇe povaˇzuje za nemoˇzn´e. Probl´ em 7.15. 3-SAT (splnitelnost logick´ ych formul´ı ve spec. verzi) N´asleduj´ıc´ı probl´em je N P-´ upln´y: Vstup: Logick´a formule Φ v konjunktivn´ım norm´aln´ım tvaru takov´a, ˇze kaˇzd´a klauzule obsahuje nejv´yˇse 3 liter´aly. V´ystup: Existuje logick´e ohodnocen´ı promˇenn´ych tak, aby v´ysledn´a hodnota Φ byla 1 (pravda)? Petr Hlinˇen´ y, FI MU Brno
12
FI: MA010: Barevnost a dalˇs´ı
Probl´ em 7.16. 3-COL (3-obarven´ı grafu) N´asleduj´ıc´ı probl´em je N P-´ upln´y: Vstup: Graf G. V´ystup: Lze vrcholy G korektnˇe obarvit 3 barvami? D˚ ukaz (n´aznak): Uk´aˇzeme si polynomi´aln´ı pˇrevod z probl´emu 3-SAT. 2 Sestroj´ıme graf G pro danou formuli Φ. Z´akladem grafu je troj´uheln´ık, jehoˇz vrcholy oznaˇc´ıme X, T, F . Kaˇzd´e promˇenn´e xi ve Φ pˇriˇrad´ıme dvojici vrchol˚ u spojen´ych s X. Kaˇzd´e klauzuli ve Φ pˇriˇrad´ıme podgraf na 6 vrcholech (z nichˇz tˇri jsou spojen´e s T ), jako na obr´azku. Nakonec voln´e p˚ ulhrany“ z obr´azku pospojujeme dle toho, jak´e liter´aly ” vystupuj´ı v klauzul´ıch. s s s s x1 (x1 ∨ ¬xi ∨ . . . ) ¬x1 s T s s s X .. s s . s .. s F . xi ¬xi s Pak G m´a 3-obarven´ı pr´avˇe kdyˇz je Φ splniteln´a, jak si lze ovˇeˇrit na obr´azku. Petr Hlinˇen´ y, FI MU Brno
13
FI: MA010: Barevnost a dalˇs´ı
2
Probl´ em 7.17. IS (nez´ avisl´ a mnoˇ zina) N´asleduj´ıc´ı probl´em je N P-´ upln´y: Vstup: Graf G a pˇrirozen´e ˇc´ıslo k. V´ystup: Lze v G naj´ıt nez´avislou podmnoˇzinu velikosti (aspoˇn) k?
2
D˚ ukaz: Uk´aˇzeme polynomi´aln´ı pˇrevod z probl´emu 3-COL. Necht’ H je graf na n vrcholech, kter´y je za ´ ukol obarvit tˇremi barvami. Poloˇz´ıme k = n a graf G sestroj´ıme ze tˇr´ı disjunktn´ıch kopi´ı grafu H takto: s s Tv v s s s
s H
s
s
s
s
s
s
s
s
s
s
s
s
s
G
s
2
Pokud c : V (H) → {1, 2, 3} je obarven´ı H tˇremi barvami, v grafu G lze vybrat k = n nez´avisl´ych vrchol˚ u tak, ˇze pro kaˇzd´y v ∈ V (H) vezmeme c(v)-tou kopii vrcholu v v grafu G. Naopak pokud I je nez´avisl´a mnoˇzina v grafu G o velikosti k = n, pak z kaˇzd´eho troj´uheln´ıku Tv , v ∈ V (H) n´aleˇz´ı do I pr´avˇe jeden vrchol. Podle toho jiˇz urˇc´ıme jednu ze tˇr´ı barev pro vrchol v v H. 2 Petr Hlinˇen´ y, FI MU Brno
14
FI: MA010: Barevnost a dalˇs´ı
Probl´ em 7.18. VC (vrcholov´ e pokryt´ı) N´asleduj´ıc´ı probl´em je N P-´ upln´y: Vstup: Graf G a pˇrirozen´e ˇc´ıslo k. V´ystup: Lze v G naj´ıt vrcholov´e pokryt´ı, tj. mnoˇzinu C ⊆ V (G) takovou, ˇze kaˇzd´a hrana G m´a alespoˇn jeden konec v C, o velikosti nejv´yˇse k? 2 D˚ ukaz: Uk´aˇzeme polynomi´aln´ı pˇrevod z probl´emu IS. Necht’ G je graf na n vrcholech, v nˇemˇz m´ame naj´ıt nez´avislou mnoˇzinu I velikosti ℓ. Vˇsimnˇeme si, ˇze doplnˇek C = V (G) \ I nez´avisl´e mnoˇziny I je vlastnˇe vrcholov´ym pokryt´ım. Takˇze v naˇsem pˇrevodu staˇc´ı pouˇz´ıt stejn´y graf G a k = n − ℓ. 2 s
s f
sf sf
s
s
s f
s
s
s f
s f
sf
s
s
nez´avisl´a mnoˇzina Petr Hlinˇen´ y, FI MU Brno
s
s f vrcholov´e pokryt´ı
15
FI: MA010: Barevnost a dalˇs´ı
Probl´ em 7.19. DOM (dominuj´ıc´ı mnoˇ zina) N´asleduj´ıc´ı probl´em je N P-´ upln´y: Vstup: Graf G a pˇrirozen´e ˇc´ıslo k. V´ystup: Lze v G naj´ıt dominuj´ıc´ı mnoˇzinu, tj. mnoˇzinu D ⊆ V (G) takovou, ˇze kaˇzd´a vrchol G m´a nˇekter´eho souseda v D, o velikosti nejv´yˇse k?2 D˚ ukaz (n´aznak): Probl´em dominuj´ıc´ı mnoˇziny jasnˇe patˇr´ı do N P a jeho ´uplnost je dok´az´ana n´asleduj´ıc´ım schematick´ym polynomi´aln´ım pˇrevodem. s s s f f f s f s s s
→
s
s
s
s H
s f
s
f s
s
s
G
Pro dan´y graf H vytvoˇr´ıme graf G pˇrid´an´ım, pro kaˇzdou hranu e ∈ E(H), nov´eho vrcholu ve spojen´eho hranami do obou koncov´ych vrchol˚ u hrany e. (Tak se vlastnˇe z kaˇzd´e hrany stane troj´uheln´ık s tˇret´ım nov´ym vrcholem, viz naznaˇcen´y obr´azek.) ˇ ıseln´y parametr k z˚ C´ ustane tentokr´at nezmˇenˇen. Nyn´ı zb´yv´a dok´azat, ˇze G m´a vrcholov´e pokryt´ı velikosti k, pr´avˇe kdyˇz H m´a dominuj´ıc´ı mnoˇzinu velikosti tak´e k, coˇz nen´ı obt´ıˇzn´e. 2 Petr Hlinˇen´ y, FI MU Brno
16
FI: MA010: Barevnost a dalˇs´ı
Probl´ em 7.20. HC (Hamiltonovsk´ y cyklus) N´asleduj´ıc´ı probl´em je N P-´ upln´y: Vstup: Orientovan´y graf G. V´ystup: Lze v G naj´ıt orientovanou kruˇznici (cyklus) proch´azej´ıc´ı vˇsemi vrcholy?2 Probl´ em 7.21. HK (Hamiltonovsk´ a kruˇ znice) N´asleduj´ıc´ı probl´em je N P-´ upln´y: Vstup: Graf G. V´ystup: Lze v G naj´ıt kruˇznici proch´azej´ıc´ı vˇsemi vrcholy?
2
D˚ ukaz:
v s
s
s
s
Pv →
Pouˇzijeme snadn´y pˇrevod z pˇredchoz´ıho probl´emu HC. Kaˇzd´y vrchol v orientovan´eho grafu H nahrad´ıme tˇremi vrcholy tvoˇr´ıc´ımi cestu Pv d´elky 2 v grafu G. Orientovan´e hrany grafu H pˇrich´azej´ıc´ı do v pak pˇrivedeme do prvn´ıho vrcholu cesty Pv , hrany odch´azej´ıc´ı z v naopak vedeme z posledn´ıho vrcholu cesty Pv . 2 Petr Hlinˇen´ y, FI MU Brno
17
FI: MA010: Barevnost a dalˇs´ı
7.4
Pˇr´ıbˇ eh probl´ emu vrcholov´ eho pokryt´ı
Bylo nebylo, jednou se dva slovutn´ı informatici (pˇri surfov´ an´ı na moˇri?) zaˇcali zab´ yvat ot´ azkou, proˇc dva tak podobn´e“ probl´emy jako vrcholov´e pokryt´ı a dominuj´ıc´ı mnoˇzina maj´ı (pˇrestoˇze ” oba N P-´ upln´e) tak rozd´ıln´e algoritmick´e chov´ an´ı. . . Ale dost poh´ adek, v´ıce konkr´etn´ıch informac´ı ˇcten´ aˇr najde v [R. Downey and M. Fellows, Parameterized complexity, Springer 1999]. Mimo jin´e se dozv´ı, ˇze tato zd´ anlivˇe okrajov´ a ot´ azka dala vzniknout zcela nov´emu pohledu na v´ ypoˇcetn´ı sloˇzitost probl´em˚ u, kter´ y jde jaksi mimo“ ” klasickou polynomi´ aln´ı hierarchii a umoˇzn ˇuje docela rozumnˇe ˇreˇsit i nˇekter´e probl´emy, kter´e jsou jinak N P-tˇeˇzk´e. 2
Takˇze v ˇcem spoˇc´ıv´a z´asadn´ı rozd´ıl v naˇsich znalostech o ˇreˇsen´ı probl´em˚ u dominuj´ıc´ı mnoˇziny a vrcholov´eho pokryt´ı? • Pokud se v anal´yze zamˇeˇr´ıme na hodnotu parametru k vstupu, tak dominuj´ıc´ı mnoˇzinu velikosti k stejnˇe nedok´aˇzeme nal´ezt rychleji neˇz probr´an´ım prakticky vˇsech k-tic vrchol˚ u grafu G. To je i pro mal´e fixn´ı hodnoty k, tˇreba k = 10, 20 v praxi neprovediteln´e. 2 • Avˇsak vrcholov´e pokryt´ı velikosti k dok´aˇzeme nal´ezt jednoduch´ym algoritmem v ˇcase O(2k · n), coˇz pro mal´e fixn´ı hodnoty k d´av´a skvˇele pouˇziteln´y line´arn´ı algoritmus! Petr Hlinˇen´ y, FI MU Brno
18
FI: MA010: Barevnost a dalˇs´ı
Algoritmus 7.23. k-VC (vrcholov´ e pokryt´ı) Pro fixn´ı k vyˇreˇs´ıme n´asleduj´ıc´ı probl´em. Vstup: Graf G. V´ystup: Lze v G naj´ıt vrcholov´e pokryt´ı o velikosti nejv´yˇse k?
2
Pro inicializaci poloˇz´ıme C = ∅ a F = E(G). • Pokud F = ∅, vrac´ıme C jako vrcholov´e pokryt´ı. Jinak pokud |C| ≥ k, vrac´ıme odpovˇed’ NE. • Vybereme libovolnou hranu f = uv ∈ F a pro oba jej´ı konce x = u, v udˇel´ame: – C ′ = C ∪ {x} a F ′ vytvoˇr´ıme z F odebr´an´ım vˇsech hran vych´azej´ıc´ıch z vrcholu x v G. – Rekurzivnˇe zavol´ame tento algoritmus pro G, C ′ a F ′ .
2
Kolik tento algoritmus provede rekurzivn´ıch vol´an´ı celkem? Kaˇzd´y pr˚ uchod generuje dvˇe dalˇs´ı vol´an´ı, ale jen do fixn´ı hloubky k, takˇze ve v´ysledku bude ˇcas v´ypoˇctu jen O(2k · n). Pozn´ amka: Dnes je jiˇz zn´ amo, ˇze faktor 2k lze promyˇslenˇejˇs´ım pˇr´ıstupem vylepˇsit“ na mno” hem menˇs´ı z´ aklad mocniny. (2006: 1.2738k ) Petr Hlinˇen´ y, FI MU Brno
19
FI: MA010: Barevnost a dalˇs´ı
