|
|
Advanced methods of searching the game tree of 3-dimensional Tic-Tac-Toe
Dvořák, Pavel ; Valla, Tomáš (vedoucí práce) ; Šámal, Robert (oponent)
V této práci zkoumáme poziční hry, zejména pak vícerozměrné piškvorky. Porovnáváme existující pokročilé algoritmy (Pn-search, Db-Search, λ-search) pro řešení pozic v pozičních hrách. Algoritmy nasazujeme na domény her 43 a 53 , což jsou první netriviální připady trojrozměrných piškvorek. Paralelizujeme Pn-search pro případ, kdy existuje více počátečních pozic. Pn-search aplikujeme jako jed- novláknovou úlohu a řešíme, jak sdílet transpoziční tabulku s vyřešenými poz- icemi. Hlavním a čistě teoretickým výsledkem je charakterizace grupy auto- morfismů kombinatorické krychle nd se stejnou množinou linií jako vícerozměrné piškvorky. Toto je zobecnění Silvera [The American Mathematical Monthly, Vol. 74, No. 3, 1967], který popsal automorfismy hry 43 . 1
|
|
|
Kružnice a párování v grafech
Tesař, Karel ; Pangrác, Ondřej (vedoucí práce) ; Šámal, Robert (oponent)
O grafu řekneme, že je k-linkovaný, pokud pro každých k dvojic jeho vrchol· existují navzájem disjunktní cesty, které dané dvojice spojují. Existuje vztah mezi k-linkovaností a vrcholovou souvislostí grafu. V této práci hledáme vztah mezi vrcholovou souvislostí grafu a vlastností, že každých k jeho disjunktních hran leží na společné kružnici. Tento problém se dá řešit pomocí k-linkovanosti. Naším cílem je dosáhnout lepších odhad· na souvislost, resp. jiných postačujících podmínek než těch, které jsou známe pro k-linkovanost. 1
|
|
|
Lipschitzovská zobrazení diskrétních množin
Kaluža, Vojtěch ; Matoušek, Jiří (vedoucí práce) ; Šámal, Robert (oponent)
V této práci se zabýváme Feigeho otázkou existence konstantně lipschitzov- ské bijekce každé n2 -prvkové podmnožiny S ⊂ Z2 na pravidelnou mřížku n × n bodů v Z2 . Uvedeme řešení tohoto problému v případě, že body v S jsou uspořá- dány ve tvaru dlouhého obdélníku nebo ve tvaru čtverce bez vnitřku. Hlavní částí práce je rešerše článků Buraga a Kleinera [2] a McMullena [12], zabývajících se problémem existence bilipschitzovsky neekvivalentních separovaných sítí, který je podobný Feigeho problému. Dle těchto článků zkonstruujeme separovanou síť v R2 bilipschitzovsky neekvivalentní Z2 na základě konstrukce kladné omezené měřitelné funkce, která není Jakobiánem žádného bilipschitzovského homeomor- fismu skoro všude. Ukážeme McMullenovu konstrukci takové funkce a doplníme důkaz její správnosti. 1
|
|
|
Petersenovské obarvení a jeho varianty
Bílková, Hana ; Šámal, Robert (vedoucí práce) ; Dvořák, Zdeněk (oponent)
Petersenovské obarvení 3-regulárního grafu G je ekvivalentní tzv. normálnímu obarvení za použití pěti barev. Normální obarvení je dobré hranové obarvení ta- kové, že každá hrana je spolu se svými čtyřmi sousedy obarvena dohromady třemi nebo pěti různými barvami. Podle Jaegerovy hypotézy lze každý 3-regulární graf bez mostů petersenovsky obarvit. Platnost hypotézy by dokázala další zajímavá tvrzení pro 3-regulární grafy. V tomto textu se budeme zabývat normálním obar- vením pro větší počet barev. Z Jaegerovy věty o nenulovém Z2 3 -toku plyne, že každý graf bez mostů lze normálně obarvit sedmi barvami. Zde dokážeme exis- tenci obarvení devíti barvami pro grafy s mostem, s řezem velikosti dva nebo s trojúhelníkem nezávisle na Jaegerově větě. Důkaz využívá myšlenku Andersenova důkazu existence silného hranového obarvení 3-regulárních grafů deseti barvami. V závěru řekneme, jak by mohl jít důkaz dokončit pro zbylé třídy 3-regulárních grafů. 1
|
|
|
Quoridor implementation
Boroš, Martin ; Pangrác, Ondřej (vedoucí práce) ; Šámal, Robert (oponent)
Cieľom tejto práce je analýza hry Quoridor a následný návrh a implementácia rozhodovacích algoritmov pre počítačových hráčov. Quoridor je relatívne nová dosková hra pre dvoch alebo štyroch hráčov. Abstraktne je ju možné chápať ako problém hľadania najkratšej cesty v grafe s tým, že je možné odoberať hrany v grafe. V úvode práce si predstavíme Quoridor, jeho históriu a pravidlá. Následne navrhneme vhodnú notáciu a reprezentáciu hry. Ďalej pojednávame o rozhodovacích algoritmoch pri hre dvoch hráčov a potrebných zmenách a vylepšeniach rozhodovania pri hre štyroch hráčov. Na záver si predstavíme aplikáciu, ktorá bola vyvinutá vrámci tejto práce.
|
|
|
Graph coloring problems
Lidický, Bernard ; Fiala, Jiří (vedoucí práce) ; Paulusma, Daniel (oponent) ; Šámal, Robert (oponent)
Název práce: Varianty problému obarvení Autor: Bernard Lidický Katedra: Katedra aplikované matematiky Vedoucí disertační práce: doc. RNDr. Jiří Fiala, Ph.D. Abstrakt: V této práci studujeme barvení grafů. Práce je rozdělena do tří částí, kde každá část se zabývá jinou variantou barvení. V první části se zabýváme 6-kritickými grafy na plochách a 6-kritickými grafy s malým počtem křížení. Hlavními výsledky jsou kompletní seznam 6-kritických grafů na Kleinově láhvi a 6-kritických grafů s křížícím číslem nejvýše čtyři. Druhá část je věnována vybíravosti rovinných grafů bez krátkých cyklů. Ukazu- jeme, že rovinné grafy bez 3-,7- a 8-cyklů jsou 3-vybíravé a že rovinné grafy bez trojúhelníků a s jistým omezením na 4-cykly jsou též 3-vybíravé. V poslední části se zaměřujeme na novější variantu barvení - vlnové barvení. Jde o koncept, který je motivovaný přiřazováním frekvencí a má zohlednit, že různé frekvence mají různý dosah. Zabýváme se pak zlepšováním odhadů nutného počtu barev k obarvení čtvercové a šestiúhelníkové mřížky. Klíčová slova: kritické grafy, seznamové barvení, vlnové barvení, rovinné grafy, krátké cykly
|
|
|
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ů
|
|
|
Structural properties of graphs---probabilistic and deterministic point of view
Hladký, Jan ; Pawlas, Zbyněk (oponent) ; Šámal, Robert (vedoucí práce)
V práci zkoumáme bipartitní podgrafy náhodného kubického grafu. Ukážeme, že hranově maximální bipartitní podgraf náhodného kubického grafu na n vrcholech má asymptoticky skoro jistě méně než 3 2 ·0.9351n hran. Dále ukážeme, že počet vrcholů vrcholově maximálního indukovaného bipartitnho podgrafu náhodného kubického grafu asymptoticky skoro jistě leží v intervalu [0.75n; 0.9082n]. K získání dolního odhadu zkonstruujeme randomizovaný algoritmus na hledání velkého indukovaného biparitního podgrafu v náhodném kubickém grafu. V závěru práce diskutujeme důsledky pro grafové homomorfismy, zejména pro Nešetřilovu Pětiúhelníkovou domněnku.
|
|
| |
|
| |
host ::
RSS.