Univerzita Karlova v Praze Matematicko-fyzikální fakulta BAKALÁŘSKÁ PRÁCE. Josef Chludil. On-line algoritmy barvení bipartitních grafů

Univerzita Karlova v Praze Matematicko-fyzikální fakulta

BAKALÁŘSKÁ PRÁCE

Josef Chludil On-line algoritmy barvení bipartitních grafů Katedra aplikované matematiky

Vedoucí bakalářské práce: RNDr. Ondřej Pangrác, Ph.D. Studijný program: Informatika, Obecná informatika

2009

Rád bych poděkoval především vedoucímu této práce, panu RNDr. Ondřeji Pangrácovi, Ph.D., za trpělivost, dobré rady a směrování. Můj dík patří samozřejmě také mým přátelům, členům rodiny a všem, kteří mi umožnili se na práci řádně soustředit a přispěli tak k příjemné pracovní atmosféře, která vedla k jejímu zdárnému dokončení.

Prohlašuji, že jsem svou bakalářskou práci napsal samostatně a výhradně s použitím citovaných pramenů. Souhlasím se zapůjčováním práce a jejím zveřejňováním.

V Praze dne: 11.12 2009

Josef Chludil 2

OBSAH 1. Teoretická příprava

6

1.1 Grafy, on-line barvení, základní pojmy a definice ........................................... 6 1.2 Tvrzení o odhadech hranic on-line chromatických čísel .................................. 8 2. Popis algoritmů

11

2.1 Algoritmus First-Fit ........................................................................................ 11 2.2 Algoritmus Odd First-Fit ................................................................................ 14 2.3 Porovnání First-Fit a Odd First-Fit ................................................................. 18 3. Praktická část – testovaní na příkladech

20

3.1 Rozbor výsledků ............................................................................................. 21

4. Program

25

Literatura

29

3

Název práce: On-line algoritmy barvení bipartitních grafů Autor: Josef Chludil Katedra (ústav): Katedra aplikované matematiky Vedoucí bakalářské práce: RNDr. Ondřej Pangrác, Ph.D. e-mail vedoucího: [email protected]

Abstrakt: Instancí problému on-line barvení grafu je graf a pořadí jeho vrcholů, algoritmus potom barví popořadě vrcholy a jako informaci zná graf indukovaný předchozími vrcholy. Přirozeným algoritmem je First Fit, který obarví vrchol první přípustnou barvou. Tento algoritmus má ale slabiny, poměr mezi nalezeným a optimálním řešením může být až lineární vzhledem k počtu vrcholů grafu, a to i pro grafy bipartitní. Pro ty je ale znám algoritmus s logaritmickým aproximačním faktorem.

Klíčové slova: First-Fit, Odd First-Fit, online barveni grafů, bipartitní graf

Title: On-line algorithms for bipartite graph coloring Author: Josef Chludil Department: Department of Applied Mathematics Supervisor: RNDr. Ondřej Pangrác, Ph.D. Supervisor’s e-mail: [email protected]

Abstract: Instance of the on-line graph coloring problem is a graph together with a permutation of its vertices (viewed as a linear ordering of the vertex set). The goal is to color the graph with vertices taken in the given order using the information of the subgraph induced by previous vertices. The most natural algorithm is the First Fit algorithm using in each step the first possible color. Unfortunately optimum number of colors can be linear dependent on number of vertices of graph even for bipartite graphs. On the other hand, there is an algorithm with logarithmic approximation factor for this class of graphs.

Keywords: First-Fit, Odd First-Fit, on-line graph coloring, bipartite graph

4

Úvod Tato bakalářská práce navazuje na ročníkový projekt, jehož úkolem bylo implementovat algoritmy on-line barvení pro třídu bipartitních grafů. Hlavním záměrem mojí práce je vizualizace těchto algoritmů a vytvoření uživatelsky příjemného grafické prostředí pro práci s bipartitními grafy. V obecnosti je obor on-line barvení grafů rozsáhlý, zahrnuje jednoduché hříčky, problémy on-line rozvrhů, dynamické alokace paměti až po takzvaný “Broadcast problem“. Všechny tyto problémy můžeme převést na on-line barvení grafů. Výsledek mého snažení je program, který implementuje dva algoritmy on-line barvení a je vytvořen tak, aby jeho ovládání bylo jednouché pro každého. Nabízí různé možnosti zadávání vstupních dat a to jak vstup ze souboru, tak generování náhodného vstupu nebo editaci. Program pracuje s bipartitními grafy, to znamená i s jejich podtřídami, jako například rozsáhlou skupinou grafů, které nazýváme stromy.

5

Kapitola 1 Teoretická příprava Tato kapitola slouží k bližšímu seznámení s grafy a teorií grafů. Představím některé základní definice a pojmy, se kterými budu dále pracovat.

1.1 Grafy, on-line barvení, základní pojmy a definice Graf G je uspořádaná dvojice (V, E) kde V = { v1, v2, ... , vp} je neprázdná množina vrcholů a E = { e1, e2, ... eq } je množina hran.

Obrázek 1.1: Graf na 7 vrcholech Každá hrana e ∈ E je neuspořádaná dvojice vrcholů z V, e={v, v’}, kde v, v ∈ V jsou vrcholy z V. Nechť u a v jsou vrcholy grafu G. Pokud jsou u a v sousední, můžeme psát u~v. Potom N(v)={w∈V: w~v } je množina sousedních vrcholů vrcholu v. Stupeň vrcholu v značíme deg(v)=| N(v)|. Vrchol stupně 0 nazýváme izolovaný. H je podgraf grafu G, pokud platí V(H) V G H je indukovaný podgraf grafu G, pokud platí V(H) V G G

G

Komponenta grafu G je maximální souvislý podgraf grafu G. Souvislý graf G=(V, E) neobsahující kružnici nazýváme stromem. Bipartitní graf G=(V, E) je takový graf, pokud množinu vrcholů V můžeme rozdělit na dvě disjunktní podmnožiny V1 a V2, tak že hrany spojují pouze vrcholy V1 s vrcholy V2. G =(V, E), V={u1,…, un} {v1,…, vm}, E={{u,v}: u∈V1 a v∈V2} Příklady některých důležitých grafů 6

Úplný graf Kn (kde n>1) V={1, ... , n}, E=(

)

Úplný bipartitní graf Kn,m (kde n,m>1) E ={{ui, vj}}, i=1, ... , n, j=1, ... , m Klika grafu G je podgraf grafu G, takový, že je úplný graf. Klikovost grafu ω(G) je rovna velikosti největší kliky grafu G. Nezávislá množina grafu G je taková množina jeho vrcholů, žádné dva vrcholy nejsou spojeny hranou. Značíme α(G). Řekneme, že grafy G a H jsou izomorfní, jestliže existuje bijektivní zobrazení f: V(G) V(H) a to tak, že vrcholy u a v z grafu G jsou sousední a vrcholy f(u) a f(v) jsou sousední v H. Když graf G je isomorfní grafu H potom píšeme G≈H. Obarvení grafu je zobrazení c: V {1,..,k}, pro každou hranu e={u, v} kde u, v∈V platí c(u)≠c(v). Chromatické číslo (G) je nejmenší počet barev potřebný pro obarvení G. Strom je zvláštním příkladem bipartitního grafu. O bipartitních grafech i o stromech můžeme říct, že jsou 2-obarvitelné, to znamená, že (G) 2. On-line graf je uspořádaná trojice (V, E, ), kde G=(V, E) je graf a úplné uspořádání na V. (Dále budeme uvažovat V konečnou.) Pořadí nazveme vstupní sekvencí.

je

on-line graf vzniklý prvními n členy , Vn={v1 vn} vrcholy z V. Algoritmus A, který správně obarvil vrcholy on-line grafu je on-line algoritmus barvení pokud barva n-tého vrcholu vn je jednoznačně určena isomorfismem . Algoritmus A barví vrcholy grafu G, právě jeden vrchol v daný moment z jednoznačně určeného pořadí v1 vn a ve stejný čas je pevně určena barva vrcholu vn. Algoritmus v danou chvíli vidí pouze indukovaný graf Gn. AOL (G) označme množinu všech on-line barvících algoritmů pro graf G. Počet barev, které algoritmus A použije na obarvení grafu označíme ). Maximum z A( ) pro všechny možné vstupní sekvence označíme A( třída grafů, potom maximum A(G), nebo též A-chromatické číslo. Když je označíme A( ). On-line chromatické číslo pro A(G) pro všechny G z třídy označíme ol( ). ol( ) je minimum všech on-line algoritmů A v A( ).

7

je třída grafů (v ideálním případě nekonečná). AOL(G) je množina všech algoritmů barvící graf G. Pokud A∈AOL(G) pro všechny G∈ potom říkáme, že A je on-line barvící algoritmus pro a píšeme A∈AOL( ). Algoritmus A∈AOL( ) nazveme kompetitivním (pozn.: anglicky competitive) pro , jestliže existuje funkce f, taková že A(G) f( (G)) pro každý graf G∈ a je on-line kompetitivním když A(G) f( ol( )) pro každý graf G z . Pokud = (V, E, ) je on-line graf, potom (v)=| (v)|.

(v)={w∈V : w~v a w v} a

Množinu {1,…, n} budeme značit [n]. Pro sekvenci σ={σ1,…, σn} se podsekvence tvaru σ={σ1,…, σi} bude nazývat iniciační sekvence σ a podsekvence tvaru σ={σi,…, σn} se bude nazývat konečná sekvence σ. Délku sekvence σ budeme značit |σ|. Binární logaritmus z čísla n budeme značit lg(n).

1.2 Tvrzení o odhadech hranic on-line chromatických čísel Tvrzení 1: (Gyárfás and Lehel) Pro všechna přirozená čísla k existuje strom Tk s 2k-1 vrcholy takový, že pro každý on-line barvící algoritmus A platí A(Tk)≥k. Důkaz: Nejprve definujme strom Tk. Nechť D={σ : σ je klesající posloupnost přirozených čísel}. Pro σ∈D, nechť Vσ = {τ ∈ D : σ je iniciační sekvence τ}. Nechť Tσ je strom na vrcholech množiny Vσ takový že τ sousedí s τ’ právě když |τ|+1=|τ’| a τ’∈Vσ nebo obráceně. σ nazveme kořenem Tσ a dále budeme používat zápis ,..., místo ( ). Zvláště pak Tk=T(k). Dodatek: pokud τ je konečná sekvence σ, potom existuje izomorfismus z Tτ do Tσ to značí τˆρ do σˆρ. Tak Tk-(k) = Tk,1+…+Tk,k-1. Vložením (k) zpět vidíme, že (1) Tk ≈ Tk-1+Tk-1+e, kde e je hrana spojující kořen se dvěma kopiemi Tk-1 a kořen Tk-1+Tk-1+e může být také jedním z koncových bodů e. Platí tedy že |Vk|=2k-1. Nechť Sk,i = Tk,1+...+Tk,i. Rozhodující vlastnost Tk, kterou využijeme (2) pro nějaké i < k, existuje vložení Sk,i do Tk které mapuje (k, i) do (k) a je rozšiřitelné na automorfizmus Tk. To znamená, že on-line barvící algoritmus vidí jenom podgraf isomorfní Sk,i a nemůže rozlišit mezi (k,i) a (k). Nebo ještě jinak on-line barvící algoritmus vidí indukovaný podgraf na prvních k vrcholech z pořadí. Vlastnost (2) se snadno dokáže pomocí indukce na k-i. Základní krok k-i=1 vyplývá okamžitě z vlastnosti (1). Indukční krok 8

z indukčního předpokladu aplikací na uspořádanou dvojici {k-1, i} a ze základního kroku. Nechť Pk je částečné uspořádání na Sk,k-1 a to takové, že x Pk y právě tehdy když x ∈ Tk,i, y ∈ Tk,j a i < j. Můžeme tvrdit, že pro každé přirozené číslo k a on-line barvící algoritmus A, existuje úplné uspořádání z Sk,k-1 takové, že rozšiřuje Pk a A obarví každý vrchol (k,1), ...,(k,k-1) rozdílnou barvou když Sk,k-1 je z pořadí . Z toho vyplývá, jestliže (k) je poslední v pořadí, potom A použije k-tou barvu na obarvení vrcholu (k). Pomocí indukce předpokládejme, že jsme to dokázali pro případ k=m a rozmysleme případ k=m+1. Protože Sk,m-1≈ Sm,m-1, potom existuje pořadí takové, že A barví do Sk,m-1 v pořadí , algoritmus A použije rozdílné barvy na množinu Q={(k,1),…,(k,m-1)}. Nechť B je on-line barvící algoritmus, který obarví Tk,m stejně jako algoritmus A Tk,m≈Tm po prvním obarvení Sk,m-1 v pořadí . Pokud použijeme indukci na B místo A, existuje pořadí Tk,m rozšiřující vzor Pm, tak, že když použijeme algoritmus A na Sk,m v pořadí ,A využije rozdílné barvy na množinu R={(k,m,1),…,(k,m,m-1)}. Když algoritmus A použije stejnou barvu na obě množiny Q a R, potom (k, m) obarví novou barvou a jsem hotov. Jinak obarvíme nějaký kořen (k,m,i) novou barvou α. Protože rozšiřuje vzor Pm, čase barvení (k,m,i) algoritmem B je viditelný pouze podgraf Tk,m≈Tm, který je isomorfní Sm,i. Podle vlastnosti (2) můžeme znovu uspořádat Vk,m tak, že (k, m) vypadá jako (k, m, m-1) a je obarvena barvou α algoritmem A. ■

Věta 1: (Lovász, Saks, a Trotter). Existuje on-line algoritmus barvení A takový, že pro každý on-line 2obarvitelný graf G na n vrcholech platí A(G) 2*lg(n). Důkaz: Uvažujme vstupní sekvenci v1 v2 vn on-line 2-obarvitelného grafu . Náleží-li vi do určité partity (I1, I2) v souvislé komponentě grafu kam vi patří, do nezávislé množiny tak, že vi ∈ I1. Algoritmus A obarví vrchol vi přinejmenším barvou, která nebyla použita na obarvení nějakého vrcholu z partity I2. Stačí ukázat, že když algoritmus A použije alespoň t barev na nějakou komponentu , potom je tato komponenta tvořena nejméně vrcholy. Budeme postupovat indukcí přes i, přičemž základní krok je triviální. Pro indukční krok pozorujeme, že když algoritmus A obarví vrchol vi barvou k+2, potom musel algoritmus A obarvit barvou k nějaký vrchol vp ∈ I2 a barvou k+1 musel obarvit ještě nějaký vrchol v komponentě I2. Jestliže A musel barvou k obarvit nějaký vrchol vq v komponentě I1. Když A obarvil vrcholy vp a vq stejnou barvou, potom vp a vq musí být v jiných komponentách grafu , kde r=max{p,q}. Nyní podle indukčního předpokladu, každá z těchto 9

komponent musí být složena z nejmíň s vrcholem vi v grafu musí mít nejméně

vrcholů a tak komponenta vrcholů. ■

Shrnutí Tvrzení 1 ukazuje, že nemůžeme určit hranice on-line chromatického čísla grafu pouze pomocí chromatického čísla grafu, a to ani v případě stromu. V druhé části tvrzení jsme odvodili netriviální hranice pro on-line chromatické číslo pro graf na n vrcholech v závislosti na jejich chromatickém čísle a n. Tímto jsme si určili hranici pro nejlepší on-line barvící algoritmus. Tato hranice je logaritmická vzhledem k počtu vrcholů. Ve Větě 1 jsme si dokázali, že existuje on-line barvící algoritmus, který obarví třídu bipartitních (tedy i podtřídu stromů) s nejvýše 2*lg(n). V důkazu je naznačeno, jak takový algoritmus funguje. Dále ho budeme nazývat Odd FirstFit algoritmem.

10

Kapitola 2 Popis algoritmů V této části popíši oba implementované algoritmy, ukážu, v čem se liší, jaké jsou případy, kdy algoritmus použije nejvíce barev pro daný graf na n vrcholech a kdy je lepší použít který algoritmus.

2.1 Algoritmus First-Fit Algoritmus First-Fit patří do rodiny takzvaných hladových algoritmů. Při online barvení barví vrchol první přípustnou barvou. V každém kroku musí obarvit vrchol, přičemž „vidí“ pouze indukovaný podgraf z vrcholů pořadí. Nikde si vrcholy neuchovává pro případné pozdější barvení a jednou již obarvené vrcholy nemůže přebarvovat. Bohužel tato strategie nemusí nutně vést k optimálnímu obarvení (což není neobvyklé pro hladové algoritmy). Příklady obarvení:

Obrázek 2.1: Obarvení grafu G pomocí First-Fit algoritmu, pořadí 3, 4, 5, 6, 7, 8}

= {1, 2,

Obrázek 2.2: Obarvení grafu G pomocí First-Fit algoritmu, pořadí 1, 2, 3, 7, 8, 5}

= {6, 4,

11

First-Fit formální popis Vstup: On-line bipartitní graf G = (V, E, ). Výstup: Obarvení grafu G. Algoritmus: Seznam barev C={1} Pro všechny vi ∈ dělej

// iniciační seznam barev

 Zjistíme barvy sousedů Ci a (vi) v indukovaném podgrafu Gi.  Pokud | (vi)| = 0, potom vi je izolovaný, vi obarvíme barvou 1 a pokračujeme dalším vrcholem vi+1  Pokud existují nějaké volné barvy Cj =C \ Ci, vrchol obarvíme první volnou barvou cj1 a pokračujeme dalším vrcholem vi+1.  Pokud |Cj|=0, není žádná barva volná, vrchol obarvíme barvou c =|C|+1, barvu c přidáme do seznamu barev C a pokračujeme dalším vrcholem vi+1. Konec ■

Obrázek 2.3: Barvení grafu G pomocí First-Fit algoritmu, pořadí ={1,2,3,4,5,6,7,8}

12

Kdy First-Fit selhává? Nyní předvedu, jak lze zkonstruovat on-line graf s počtem vrcholů n, který First-Fit obarví barvami. Tím ukážu protipříklad proti kompetitivitě First-Fit algoritmu pro třídu bipartitních grafů. Předpoklady: Vrcholy V si rozdělím na dvě disjunktní množiny podle partit. Partita A={a1,…, an} a partita B ={b1,…, bn}. Dále předpokládáme bez ujmy na obecnosti, že velikost partit A a B je stejná. Pořadí ={a1, bj,…, an, bn}. Konstrukce: Chceme, aby vrcholy byly obarveny barvami, to znamená, že v každé partitě musí být každý vrchol obarven jinou barvou. Toho docílíme tak, že G = Km,m – M, kde Km,m je úplný bipartitní graf na n vrcholech, m= a M je množina hran taková M = {{ai,bi}∈ E, i∈[n]}. Potom First-Fit obarví vrcholy ai a bi barvou i. Obrázek 4 ilustruje tento případ. Tento návod nám dává protipříklad proti kompetitivně First–Fit algoritmu pro bipartitní grafy.

Obrázek 2.4: Graf G obarvený First-Fit algoritmem s pořadím ={1,5,2,6,3,7,4,8}

Obrázek 2.5: Graf G’ obarvený First-Fit algoritmem s pořadím ={1,2,3,4,5,6,7,8}

Kompetitivita First-Fit algoritmu Tvrzení 2: (Gyárfás a Lehel). Pro každý strom T platí ol(T) = FF(T). Důkaz: Poznamenejme, že maximální stupeň stromu Tk, který jsme tvořili v důkazu Tvrzení 1 je k-1. Takže FF(Tk) k a podle Tvrzení 1 FF(T) =k. Můžeme 13

ukázat indukcí přes k, že pro jakýkoliv strom T, když First-Fit obarví vrchol v stromu T barvou k, potom T obsahuje kopii Tk s kořenem v. Z toho vyplývá, že First-Fit je optimální on-line barvící algoritmus pro stromy. První krok indukce je triviální, proto rozmysleme indukční krok. Když First-fit obarví vrchol v barvou k+1, potom pro všechny přirozená čísla i k v je sousední s vrcholem vi, který First-Fit obarvil barvou i. Z indukčního předpokladu víme, že vi je kořen kopie Ui z Ti v T-v. Když T je bez cyklů, potom různé Ui jsou v různých komponentách T-v. Z toho vyplývá, že {v} je kopie Tk+1. Shrnutí Algoritmus First-Fit je velmi rychlý, snadno implementovatelný, prostorově nenáročný. Bohužel není vhodný pro všechny třídy grafů a to ani pro všechny bipartitní grafy. Použitelný je na on-line barvení stromů. Pro třídu stromů je First-Fit kompetitivní a dokonce nejlepší možný.

2.2 Algoritmus Odd First-Fit Algoritmus Odd First-Fit je modifikací First-Fit algoritmu. Modifikace vychází z Věty 1, použitím vylepšení se zvýší efektivita algoritmu. Vylepšení spočívá v tom, že si v průběhu barvení udržujeme seznamy barev pro jednotlivé partity. Když přidáváme barvu tak přidáme takovou barvu, která není v seznamu barev druhé partity. Oba dva seznamy tak budou stejně velké, ale liší se v posledních dvou barvách.

Obrázek 2.6: Graf G obarvený Od First-Fit algoritmem s pořadím ={2,5,9,6,1,4,8,7,3}

14

Obrázek 2.7: Graf G obarvený Od First-Fit algoritmem s pořadím ={1,5,2,6,3,7,4,8,9}

Odd First-Fit formální popis Vstup: On-line bipartitní graf G = (V, E, ). Výstup: Obarvení grafu G. Algoritmus: Algoritmus udržuje seznamy použitých barev C={C1,a, C1,b, C2,a, C2,b, ..., Cn,a, Cn,b} pro každou partitu každé komponenty G a seznam komponent K={1,2,..,n}. Pro všechny vi ∈ dělej:  Zjistíme sousedy (vi), jejich barvy Ci, partitu a komponenty Ki v indukovaném podgrafu .  Pokud | (vi)| = 0, potom vi nemá žádného souseda, je tedy izolovaný, vrchol obarvíme barvou 1 a pokračujeme dalším vrcholem vi+1.  Pokud vi má | (vi)|>0, ale |Ki|=0, sousedi nepatří do žádné komponenty, potom vi spojuje izolované vrcholy, tj. vzniká nová komponenta, C(vi)= 2, vytvoříme nové seznamy Cja a Cjb barev pro vzniklou komponentu kj a tu přidáme do seznamů komponent K. Oba seznamy barev Cja a Cjb přidáme do seznamů barev C. Pokračujeme dalším vrcholem vi+1.  Pokud |Ki|>0, potom spojujeme komponenty, sloučíme zároveň i seznamy barev pro jednotlivé komponenty k∈Ki do Cja a Cjb. Cja a Cjb vložíme do seznamu barev C. (dále uvažujeme bez újmy na obecnosti, že vi patří do partity a). o Pokud existují nějaké volné barvy Cv = Cj,a\Ci, vrchol vi obarvíme první volnou barvou cv1 a pokračujeme dalším vrcholem vi+1. o Pokud |Cv|=0, žádná volná barva není, potom přidáme novou barvu c do seznamu barev Cja. Barva c= Max(Cjb)+1. Barva c je rozdílová pro Cja a Cjb. C(vi)=c a pokračujeme dalším vrcholem vi+1. Konec ■ 15

Obrázek 2.8: Barvení grafu G pomocí Odd First-Fit algoritmu, pořadí ={7, 6, 2, 5, 9, 1, 8, 4, 3} Konstrukce grafů s maximálním použitým počtem barev pro daný počet vrcholů Nejprve si ukažme, kdy Odd First-Fit je nucen přidat novou barvu. Budeme vycházet z Věty 1: Když nově přidaným vrcholem spojujeme dvě komponenty, které jsou stejné. Tj. mají stejnou velikost, jsou stejně obarveny. To znamená, že mají stejné seznamy barev pro odpovídající partity. Komponenty spojíme tak, že nový vrchol spojí dohromady seznamy barev těch partit, které se liší v jedné barvě. Tímto přijdeme o výhodu dvou rozdílných barev, a proto ho musíme obarvit novou barvou.

16

Obrázek 2.9: Situace když Odd First-Fit přidává novou barvu. Vrchol 9 spojuje dvě komponenty: první komponenta s vrcholy{1,2,3,4} druhá komponenta s vrcholy {5,6,7,8}. Vrchol 9 bude obarven novou barvou. Pořadí pro barvení ={1,5,2,6,3,7,4,8,9} Druhý případ vychází z prvního, takovým to spojením jsme docílili toho, že oba seznamy barev se liší ve velikosti a o jednu barvu, a to o nově přidanou. Do partity s kratším seznamem barev přidáme vrchol, který je spojen se všemi vrcholy druhé partity. V seznamu barev pro partitu, kam jsem vložil vrchol, není žádná barva, kterou můžu vrchol obarvit, proto do seznamu barev pro danou partitu přidám novou barvu a tou vrchol obarvím.

Obrázek 2.10: Situace při barvení vrcholu 10. Seznamu barev pro partitu kam patří, není žádná barva, kterou bych mohl použít, proto ho obarvím novou barvou. Pořadí pro barvení ={1,5,2,6,3,7,4,8,9,10} Graf obarvený maximálním možným počtem barev pro daný počet vrcholů vypadá tak, že vytváříme komponenty s nejmenším počtem vrcholů pro daný počet barev a ty následně spojujeme. Z Věty 1 víme, že počet použitých barev bude asymptoticky logaritmický k počtu vrcholů. Zároveň víme, že Odd FirstFit splňuje kompetitivní podmínku pro třídu bipartitních grafů – z odhadu Věty 1.

17

2.3 Porovnání First-Fit a Odd First-Fit Porovnáme případy grafů, kdy oba algoritmy barví graf největším možným počtem barev pro daný počet vrcholů. Příklad 1: Případ grafu G = Km,m – M, kde Km,m je úplný bipartitní graf na n vrcholech, m= a M je množina hran taková M = {{ai,bi}∈ E, i∈[n]}. Graf je rozdělen rovnoměrně na partity A={a1,…, an} a B={b1,…, bn}. Algoritmy barví v pořadí ={a1, bj,…, an, bn}. First-fit ho obarví barvami. Odd First–Fit si povede mnohem lépe. Podobně konstruovaný graf s více jak n> 8 obarví 4 barvami.

Obrázek 2.11: Vlevo graf G obarven First-Fitem 5 barvami. Vpravo obarveno Odd First-Fitem 4 barvami, pořadí ={1,6,2,7,3,8,4,9,5,10}. Příklad 2: Případ grafu, který Odd First-Fit obarví 2*lg(n), kde n je počet vrcholů. Tento příklad ilustruje Obrázek 2.10. First-Fit bude graf na obrázku barvit při stejném pořadí stejně. Komponenty{1,2,3,4,5} a {6,7,8,9,10} obarví stejně jako Odd First-Fit, když přidáme vrchol 9 First-Fit bude muset přidat také novou barvu a u vrcholu 10 to bude podobné. Příklad 3: Ukážeme si případ, kdy First-Fit barví lépe. Takový graf bude vycházet z Věty 1. Nejprve obarvíme dvě komponenty{v1,v2} a {v3,v4}. C(v1)=1, C(v2)=2, C(v3)=1, C(v4)=2. Následující vrchol v5 je spojí tak, že přidáme hrany {v2,v5} a {v3,v5} do podgrafu. Potom ho budeme muset obarvit novou barvou C(v5)=3. Toto je pro oba algoritmy stejné. Následující vrchol v6 připojíme pomocí hran {v1,v6} a {v4, v6}. CFF(v6)=3 a COFF(v6)=4. Tento případ ilustruje Obrázek 2.12.

18

Obrázek 2.12: Algoritmus First-Fit byl úspěšnější než Odd First-Fit při barvení grafu G, pořadí ={1,2,3,4,5,6} Shrnutí Popsal jsem algoritmus on-line barvení Odd First-Fit, kompetitivní algoritmus pro třídu bipartitních grafů. Porovnal sem ho s dalším algoritmem - FirstFitem. Oproti First-Fitu má Odd First-Fit složitější implementaci, je prostorově náročnější a pomalejší, ale dosahuje lepších výsledků (toto potvrdím v praktické části).

19

Kapitola 3 Praktická část – testovaní na příkladech. V teoretické části jsem popsal různé aspekty související s on-line barvením grafů a jejich předpokládané praktické výsledky. Připravil jsem si testovací pořadí a testovací grafy, abych ukázal, jak se oba algoritmy chovají. Jelikož doprovodný program vznikal z jednoduché implementace postupným přidáváním dalších vlastností, mohl jsem použít jednoduchou počáteční verzi k testování. Při testování bylo důležité určit počáteční parametry testů. Když si uvědomíme, kolik pro jeden konkrétní graf existuje různých pořadí – pro graf na n vrcholech je to n!. Je jasné, že pro rozumě velký graf jsem je všechny testovat nemohl. Proto jsem si zvolil množinu náhodně vygenerovaných pořadí. Dále bylo nutné určit, na jakých grafech je budu vlastně testovat. Pro testování během vývoje jsem vytvořil nástroj pro generování náhodného grafu, kde si uživatel může navolit různé parametry. Tohoto nástroje jsem následně využil v praktické části. Snažil jsem se, abych testy prováděl systematicky a s nějakým řádem. Ideální by bylo testovat grafy v nějaké třídě či skupině. Pro mě se stala pojítkem pravděpodobnost hrany při náhodném generování grafu. Popis vstupních parametrů testu Během vývoje jsem při testování obarvil několik stovek grafů, a tak jsem získal představu o velikosti grafu a počtu pořadí. Jak jsem již napsal dříve, testování jsem si rozdělil na skupinu grafů se stejnou pravděpodobností hrany. Neřešil jsem krajní případy, že pravděpodobnost hrany je 0% nebo 100%, tam je obarvení jasné. Jako počet vrcholů daných grafů jsem určil číslo 100. Poměr partit byl 1:1. Dále pro každou pravděpodobnost hrany jsem vygeneroval 200 různých náhodných grafů. Na všechny tyto grafy jsem použil 600 různých náhodně generovaných pořadí, která jsem vygeneroval dopředu a používal je na všechna barvení. Pro každou pravděpodobnost bylo provedeno 120000 obarvení oběma algoritmy.

20

3.1 Rozbor výsledků Grafy s malým počtem hran Skupina grafů s maximální pravděpodobností hrany do 6% včetně. Na této skupině barví First-Fit lépe než Odd First-Fit, jeho obarvení je ve více případech lepší než při obarvení Odd First-Fitem (Graf 3). Maximální počet barev, který oba dva algoritmy použijí je stejný (Graf 1). 14

12

10

8

6

4

2

0 0

5 10 15 20 25 30 35 40 45 50 55 60 65 70 75 80 85 90 95 100 Pravděpodobnost hran Průměrná FF barva Max FF barva

Průměrná OFF barva Max OFF barva

Graf 1: Průměrné barvy při barvení jednotlivých algoritmů a největší počet použitých barev Maximální počet barev použitý pro skupinu Na Grafu 1 jsou znázorněny nejvyšší počty barev ve skupině grafů pro jednotlivé pravděpodobnosti. Nejvyšší počet barev použitý Odd First-Fitem byl 6. Podle Věty 1, ale na 100 vrcholech lze zkonstruovat graf, který by Odd 21

First-Fit obarvil 13 barvami. First-Fit použil nejvíce 13 barev, horní hranice pro obarvení grafu na 100 vrcholech je 50 barev. 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 0

5 10 15 20 25 30 35 40 45 50 55 60 65 70 75 80 85 90 95 100 Pravděpodobnost hrany FF MAX barva Max rozdíl FF - OFF

OFF MAX barva Max rozdíl OFF - FF

Graf 2: Maximální rozdíly mezi počtem barev při obarvení obou algoritmů Grafy s pravděpodobností hrany od 7% S rostoucím počtem hran se situace obrací a začíná být úspěšnější barvení Odd First-Fitem. Od 10% pravděpodobnosti hrany už nenastane situace, že by First-Fit byl lepší než Odd First-Fit (Graf 3). S rostoucí pravděpodobností ubývá případů, kdy by byl Odd First-fit lepší. Největší rozdíly v obarvení First-Fit byl v testech lepší maximálně o 2 barvy, a to se mu dařilo hlavně u grafů s nižší pravděpodobností hran. Odd First-Fit byl lepší až o 9 barev. Největších rozdílů dosahoval při barvení těch grafů, kde First-Fit barvil s největším počtem barev.

22

130000 120000 110000 100000 90000 80000 70000 60000 50000 40000 30000 20000 10000 0 0

5 10 15 20 25 30 35 40 45 50 55 60 65 70 75 80 85 90 95 100 Pravděpodobnost hran FF lepší OFF

OFF lepší FF

Stejně

Graf 3: V kolika případech byly jednotlivé algoritmy lepší než druhý nebo obarvily graf stejným počtem barev Vysvětlivky pro grafy: Pravděpodobnost hrany: Pravděpodobnost s jakou se hrany vyskytují v grafu. FF lepší OFF: Počet případů, kdy First-Fit použil na obarvení grafu s daným pořadím méně barev než Odd First-Fit. OFF lepší FF: Počet případů, kdy Odd First-Fit použil na obarvení grafu s daným pořadím méně barev než First-Fit. Stejně: Počet případů, kdy oba algoritmy použijí na obarvení grafu s daným pořadím stejný počet barev. FF Max barva: Nejvyšší počet použitých barev First-Fitem na obarvení grafů při dané pravděpodobnosti. OFF Max barva: Nejvyšší počet použitých barev Odd First-Fitem na obarvení grafů při dané pravděpodobnosti. Max rozdíl FF - OFF: Největší rozdíl v použitém počtu barev na graf ve skupině grafů s danou pravděpodobností, kdy FF použil méně barev. Max rozdíl OFF - FF: Největší rozdíl v použitém počtu barev na graf ve skupině grafů s danou pravděpodobností, kdy OFF použil méně barev.

23

Konfigurace testovacího počítače Test jsem spustil na počítači s dvoujádrovým procesorem Intel D925, osazeným 2Gbi paměti typu DDR II a s nainstalovanými Windows XP SP3 CZ s Microsoft .NET Framework 3.0. Testovací program běžel 18 hodin. Shrnutí Na reálných datech se ukázalo, že First-Fit lze úspěšně použít na řídké grafy s pravděpodobností pro hrany do 6% včetně. Na grafy s větší pravděpodobností se hodí více Odd First-Fit, dosahuje výrazně lepších výsledků. Od pravděpodobnosti 90% procent může být výhodné použít na online barvení First-Fit, to zvláště tam, kde bavíme velké grafy, a záleží nám na rychlosti barvení. First-Fit se téměř vyrovná v počtu stejně obarvených grafů Odd First-Fitu. V málo případech obarví hůře. Je potřeba připomenout, že u pravděpodobnosti hrany nad 99% hrozí případ, že budeme barvit graf, který First-Fit obarví až barvami, kde n je počet vrcholů daného grafu. Tyto rizika může kompenzovat jeho rychlost.

24

Kapitola 4 Program V této kapitole představím přiložený program. Tento program byl vytvořen jako součást ročníkového projektu a bakalářské práce na Matematicko-Fyzikální fakultě Univerzity Karlovy v Praze. Vedoucí této práce byl RNDr. Ondřej Pangrác Ph.D. Program implementuje algoritmy on-line barvení bipartitních grafů. Minimální systémové požadavky Tento program funguje na operačním systému Microsoft Widows 2000 a vyšší s nainstalovaným Microsoft .NET Framework 3.0. Potřebné místo na pevném disku do 1MB. Instalace a spuštění programu 1. Vložte přiložené CD do mechaniky 2. Zkopírujte si na Váš pevný disk program Pepo.exe 3. Spusťte program Pepo.exe Uživatelské rozhraní programu Hlavní okno je rozděleno na dvě části. Část vlevo obsahuje plochu pro vykreslování, pravá část je tvořena ovládacími tlačítky. Ovládání programu První potřebujeme načíst nebo vygenerovat graf, se kterým budeme pracovat. Graf můžeme načíst ze souboru nebo náhodně vygenerovat. Dále pro barvení budeme potřebovat pořadí. Zde máme možnost načtení ze souboru nebo náhodného vygenerování. Soubory s grafem i s pořadí popíši dále.

Operace s grafem Graf můžeme nakreslit, pokud má do 100 vrcholů, všechny grafy můžeme vypsat textově do nového okna. Graf můžeme visuálně editovat, pokud je opět do 100 vrcholů. Graf lze také uložit do souboru.

Editace grafu Editace nabízí tyto možnosti: přidání a odebrání vrcholů a hran. Vrcholy, které chceme vymazat, musíme nejprve označit myší. Smažou se všechny označené vrcholy. Pro přidání nebo odebrání je potřeba označit dvojice příslušných 25

vrcholů. Pokud je označeno více vrcholů program nic neprovede. Změny se provádí na kopii původního grafu, proto je lze kdykoliv zrušit. Pokud chceme provedené změny zachovat, musíme je uložit. On-line barvení Když máme graf i pořadí načteny nebo vygenerovány, můžeme barvit, k tomu slouží tlačítka First-Fit a Odd First-Fit. V sloupečku pod tlačítky se objeví text s počtem barev použitých při obarvení. Operace s obarveným grafem Obarvený graf můžeme nakreslit, pokud má do 100 vrcholů, všechny grafy můžeme textově vypsat do nového okna. Postup můžeme animovat opět příslušnými tlačítky. K ovládání animace slouží i tlačítka Zpět, Dopředu a Nakonec – slouží k ruční animaci, klikání myší. Animaci můžeme v libovolném místě zrušit. Práce s obrázkem Obrázku grafu můžeme měnit velikost. Změnu děláme bud klikáním na tlačítka + a – nebo myší posuvníkem. V animaci se používá poslední hodnota a nelze ji v průběhu animace měnit. Obrázek grafu můžeme ukládat do souboru *.bmp. Možnosti a omezení programu Program pracuje s bipartitními grafy, do třídy bipartitních grafů patří i stromy. S těmi umí pracovat, ale zobrazuje je jako bipartitní graf. Visuálně zobrazí graf až se 100 vrcholy. Umí pracovat i s většími grafy, ale ty zobrazí pouze textově. Celkový počet vrcholů grafu, se kterým pracuje, je 9999. Při generování větších grafů je potřeba počítat s mírným prodlením. Je třeba si uvědomit, pokud máme graf s např.: 2000 vrcholy, rozdělením partit 1:1 a s libovolnou pravděpodobností hrany, úplný bipartitní graf má 1000000 hran a pro každou hranu musí určit, jestli v grafu bude nebo nebude. Při generování náhodného grafu je možné volit jeho parametry. Počet vrcholů může být 1 až 9999. Poměr partit je udán dvěma celými čísly v rozmezí 0 až 255. Poměr těchto čísel bude brán jako poměr partit generovaného grafu. Poslední možností nastavení generování je pravděpodobnost, s jakou se budou hrany vyskytovat v grafu, vstup je od 0 do 100, tedy 0% až 100%. Popis vstupního souboru s grafem Na řádku jsou napsáni všichni sousedé daného vrcholu. Tedy přirozená čísla oddělená mezerou nebo tabelátorem. Jméno vrcholu odpovídá číslu řádku, 26

začínající od 1. Pokud vrchol nemá žádné sousedy, příslušný řádek zůstane prázdný. Zápis grafu je ukončen znakem “x“ na nové řádce. Vše, co je za tímto znakem, bude ignorováno. Pokud část zápisu grafu před x obsahuje jiné znaky než číslice, mezery a tabelátory, daný graf nebude načten. Soubor s pořadím Je soubor s libovolnou permutací všech vrcholů grafu. Tj. řádek s přirozenými čísly oddělený mezerou nebo tabelátorem.

Obrázek 4.1. Spuštěná aplikace Pepo.

27

Obrázek 4.2: okno spuštěného programu Pepo, ve kterém se zadávají parametry pro generování náhodného grafu. Přiložené CD obsahuje: Spustitelnou verzi programu Pepo (Pepo.exe) Zdrojový kód programu Pepo Uživatelský manuál k programu Pepo Programátorskou dokumentaci k programu Pepo Program byl otestován na počítačích s operačními systémy MS Windows 2000 a Windows XP, kde běžel bez problémů.

28

Literatura [1] Jiří Matoušek, Jaroslav Nešetřil: Kapitoly z diskrétní matematiky, 2. vydání, Nakladatelství Karolinum, Praha, 2002 [2] Amos Fiat, Gerhard J. Woeginger: Online Algorithms: The State of the Art, Lecture Notes in Computer Science, Springer e-books, 1998

29