|
|
Vlastnosti síťových centralit
Pokorná, Aneta ; Hartman, David (vedoucí práce) ; Balko, Martin (oponent)
Potřeba porozumět komplexním sítím roste společně s jejich složitostí a mírou závis- losti lidstva na těchto sítích. Síťové centrality pomáhají rozpoznávat klíčové prvky kom- plexních sítí. Mezilehlostní (angl. betweenness) centralita je síťová centralita založená na nejkratších cestách. Přesněji řečeno, příspěvěk dvojice vrcholů u, v vrcholu w ̸= u, v je zlomek nejkratších uv-cest vedoucích vrcholem w. Mezilehlostní centralita je potom součet příspěvků vrcholu w od všech dvojic vrcholů u, v ̸= w. V této práci shrnujeme výsledky o přesných hodnotách mezilehlosti a odhadech na její hodnoty. Dále zlepšu- jeme jeden již existující odhad a formulujeme jeho přesnější znění pro r-regulární grafy. Hlavními přínosy této práce jsou dva výsledky týkající se mezilehlostně uniformních grafů, jejichž vrcholy mají stejnou hodnotu mezilehlosti. Přinášíme důkaz tvrzení, že všechny mezilehlostně uniformní grafy řádu n s maximálním stupněm n − k mají průměr ne- jvýše k, čímž jsme vyřešili domněnku uvedenou v literatuře. Dále dokazujeme tvrzení, že mezilehlostně uniformní grafy neisomorfní cyklům, které jsou zároveň buď vrcholově nebo hranově transitivní, jsou 3-souvislé, čímž jsme částečně vyřešili další domněnku. 1
|
|
|
Generalized Moran process
Svoboda, Jakub ; Šámal, Robert (vedoucí práce) ; Balko, Martin (oponent)
Moránův proces je model používaný k simulaci evolučních dynamik. Ve struk- turované populaci se objeví lépe přizpůsobený jedinec, mutant. Evoluce je simu- lována v krocích. V jednom kroku, jedinec je vybrán proporcionálně ke své fitness a rozšíří se na místo svého souseda. V této práci, vysvětlujeme Moránův proces, prezentujeme základní výsledky a definujeme vlastní variantu. Pracujeme v prostředí, kde každý jedinec má fitness v závislosti na svém typu a vrcholu, který obývá. V modifikovaném modelu dokážeme dvě věty o počtu kroků, který proces udělá než se dostane do stabilního stavu. Ukážeme, že na úplném grafu proces udělá polynomiálně mnoho kroků. Najdeme také graf, kde proces udělá expo- nenciálně mnoho kroků ale v normálním modelu jich udělá stejně jako v úplném grafu. 1
|
|
|
Ant colony optimization
Kovács, Peter ; Pangrác, Ondřej (vedoucí práce) ; Balko, Martin (oponent)
V práci sa venujem porovnávaniu metaheuristiky Ant Colony s inými metaheuristikami ako Simulated Annealing, Tabu Search alebo hladné al- goritmy. Metaheuristiky som porovnával na probléme obchodného cestujú- ceho, pri ofarbovaní grafu a množinovom pokrytí. V práci sú podrobne rozo- braté implementácie metaheuristík na jednotlivé problémy. Pri porovnávaní je braná do úvahy hlavne výsledná cenu riešenia, ale aj čas. V práci je snaha identifikovať, v ktorých prípadoch je vhodné použiť Ant Colony. Ant Colony v prípade množinového pokrytia a problému obchodného cestujúceho funguje spoľahlivo pri veľkých instanciách.
|
|
|
Structure and enumeration of permutation classes
Karpilovskij, Mark ; Jelínek, Vít (vedoucí práce) ; Balko, Martin (oponent)
Definujeme operaci složení dvou dědičných tříd permutací pomocí standardního skládání permutací jako funkcí a zkoumáme vlastnosti a strukturu permutačních tříd s ohledem na tuto operaci. Převážně se zabýváme otázkou, zda lze danou permutační třídu složit z jejích vlastních podtříd. Ukážeme příklady tříd, které lze složit ze dvou vlastních podtříd, příklady tříd, které jdou složit ze tří, ale ne ze dvou vlastních podtříd a také několik příkladů tříd, které nelze složit z žádného konečného počtu vlastních podtříd. Powered by TCPDF (www.tcpdf.org)
|
|
|
Ramsey-type results for ordered hypergraphs
Balko, Martin ; Valtr, Pavel (vedoucí práce)
Ramseyovské výsledky pro uspořádané hypergrafy Martin Balko Abstract Představíme uspořádaná Ramseyova čísla, která jsou obdobou Ramseyových čísel pro grafy s lineárně uspořádanými vrcholy. Studujeme růst uspořádaných Ramseyových čísel uspořádaných grafů vzhledem k počtu vrcholů. Nalezneme uspořádaná párování se superpolynomiálními uspořádanými Ramseyovými čísly. Ukážeme, že uspořádaná Ramseyova čísla uspořádaných grafů s omezenou dege- nerovaností a intervalovým chromatickým číslem jsou nanejvýš poly- nomiální. Dokážeme, že uspořádaná Ramseyova čísla jsou nanejvýš polynomiální pro uspořádané grafy s omezenými délkami hran. Nalezne- me 3-regulární grafy se superlineárními uspořádanými Ramseyovými čísly nad všemi uspořádáními. Poslední dva výsledky řeší problémy od autorů Conlon, Fox, Lee a Sudakov. Odvodíme přesnou formuli pro uspořádaná Ramseyova čísla mono- tónních cyklů a použijeme ji k získání přesné formule pro geomet- rická Ramseyova čísla cyklů, která byla představena Károlyim a spol. Vyvrátíme domněnku Peterse a Szekerese o zesílení slavné Erd˝osovy- Szekeresovy domněnky nad uspořádanými hypergrafy. Dokážeme přesnou formuli pro minimální počet...
|
|
|
Viditelnostní grafy
Král, Karel ; Valtr, Pavel (vedoucí práce) ; Balko, Martin (oponent)
V předložené práci se zabýváme viditelnostními grafy, se zaměřením na domněnku ,,velká přímka či velká klika." Pro danou množinu bodů P v rovině řekneme, že se dva body vidí, právě když otevřená úsečka mezi nimi neobsahuje žádný bod z P. Vrcholy viditelnostního grafu jsou body z P a dva body jsou spo- jeny hranou, právě když na sebe vidí. Kára a spol. vyslovili domněnku, že každá dost velká konečná množina bodů obsahuje buď ℓ bodů na jedné přímce nebo její viditelnostní graf má klikovost aspoň k. V práci zobecňujeme domněnku na širší třídu grafů a tím poskytujeme alternativní důkaz pro k = ℓ = 4. Dále shrneme dosavadní související poznatky. Zesílíme pozorování o výskytu Hamiltonovy kružnice ve viditelnostních grafech. Charakterizujeme asymptotické chování hra- nové barevnosti viditelnostních grafů. Ukážeme, že pro daná n, ℓ, k lze počítačově rozhodnout, zda původní domněnka platí. Zároveň provedeme počítačové exper- imenty jak pro zobecněnou, tak pro původní domněnku. 1
|
|
|
Grid representations of graphs and the chromatic number
Balko, Martin ; Valtr, Pavel (vedoucí práce) ; Kratochvíl, Jan (oponent)
Mřížková nakreslení grafů a chromatické číslo Martin Balko 1. srpna 2012 Katedra (ústav): Katedra aplikované matematiky Vedoucí diplomové práce: doc. RNDr. Pavel Valtr Dr. e-mail vedoucího: valtr@kam.mff.cuni.cz Abstrakt V předložené práci se zabýváme mřížkovými nakresleními grafů a jejich souvislostmi s grafovými obarveními. Mřížkové nakreslení grafu zobrazuje vrcholy na body mřížky Zd a hrany na úsečky, které se vyhýbají bodům odpovídajícím nekoncovým vrcholům. Nejdříve dokážeme, že graf je qd - obarvitelný, d, q ≥ 2, právě tehdy, když má mřížkové nakreslení, ve kterém každá úsečka protíná nanejvýš q mřížkových bodů. Poté se věnujeme mřížkovým nakreslením s omezeným počtem sloupců, kde představíme nové NP-úplné úlohy a rozšíříme některé známé výsledky. Také ukážeme ostrý dolní odhad na plochu mřížkového nakreslení pro úplné vyvážené k-partitní grafy, čímž dokážeme domněnku D. R. Wooda. Nakonec pro libovolný rovinný graf nalezneme rovinné mřížkové nakreslení, kde každá úsečka obsahuje pouze dva mřížkové body. Tím potvrdíme domněnky od autorů D. Flores Pe˝nalozy a F. J. Zaragoza Martineze. Klíčová slova: mřížková nakreslení, mřížka, chromatické číslo, rovina
|
|
|
Implementace hry Dots and Boxes
Balko, Martin ; Šámal, Robert (oponent) ; Pangrác, Ondřej (vedoucí práce)
Název práce: Implementace hry Dots and Boxes Jméno autora: Martin Balko Katedra (ústav): Katedra aplikované matematiky Vedoucí bakalářské práce: RNDr. Ondřej Pangrác, Ph.D. e-mail vedoucího: pangrac@kam.mff.cuni.cz Abstrakt: Předložená práce se zabývá analýzou populární logické hry Dots and Boxes a jejích zobecněných verzí. Zaměřuje se také na nejrůznější metody a algoritmy řešení umělé inteligence protivníků. Výsledkem práce je implementace rozšířené verze této hry, ve které je možné editovat vlastní hrací plochy, hrát proti více soupeřům na několika úrovních obtížnosti a používat různá ohodnocení map. Klíčová slova: Dots and Boxes, Nimstring, Pokročilé počítání řetězů
|
|
|
Ramsey-type results for ordered hypergraphs
Balko, Martin ; Valtr, Pavel (vedoucí práce) ; Conlon, David (oponent) ; Nešetřil, Jaroslav (oponent)
Ramseyovské výsledky pro uspořádané hypergrafy Martin Balko Abstract Představíme uspořádaná Ramseyova čísla, která jsou obdobou Ramseyových čísel pro grafy s lineárně uspořádanými vrcholy. Studujeme růst uspořádaných Ramseyových čísel uspořádaných grafů vzhledem k počtu vrcholů. Nalezneme uspořádaná párování se superpolynomiálními uspořádanými Ramseyovými čísly. Ukážeme, že uspořádaná Ramseyova čísla uspořádaných grafů s omezenou dege- nerovaností a intervalovým chromatickým číslem jsou nanejvýš poly- nomiální. Dokážeme, že uspořádaná Ramseyova čísla jsou nanejvýš polynomiální pro uspořádané grafy s omezenými délkami hran. Nalezne- me 3-regulární grafy se superlineárními uspořádanými Ramseyovými čísly nad všemi uspořádáními. Poslední dva výsledky řeší problémy od autorů Conlon, Fox, Lee a Sudakov. Odvodíme přesnou formuli pro uspořádaná Ramseyova čísla mono- tónních cyklů a použijeme ji k získání přesné formule pro geomet- rická Ramseyova čísla cyklů, která byla představena Károlyim a spol. Vyvrátíme domněnku Peterse a Szekerese o zesílení slavné Erd˝osovy- Szekeresovy domněnky nad uspořádanými hypergrafy. Dokážeme přesnou formuli pro minimální počet...
|
host ::
RSS.