|
|
Steinerovská barvení kubických grafů
Tlustá, Stanislava ; Fiala, Jiří (vedoucí práce) ; Šámal, Robert (oponent)
Tento text se zabývá barvením kubických grafů a shrnuje dostupné poznatky o tzv. Steinerovském barvení, což je hranové barvení, kde barvy stýkající se u jednoho vrcholu tvoří trojici nějakého částečného Steinerova systému. Velká pozornost je věnována zejména projektivním a afinním systémům. Následně je vyslovena postačující podmínka pro univerzalitu systému a je konstatováno, že všechny ostatní úplné tranzitivní systémy ji splňují. Součástí práce jsou také postupy vedoucí k nalezení obarvení pomocí Fanovy roviny, afinního systému Z3 3 a univerzálního systému s označením F7 S⊠ 3 vzniklého součinem Fanovy roviny s triviálním systémem. Nakonec je prezentován algoritmus použitelný pro ostatní systémy a kubické grafy s omezenou stromovou šířkou.
|
|
|
3-Coloring Graphs on Torus
Pekárek, Jakub ; Dvořák, Zdeněk (vedoucí práce) ; Šámal, Robert (oponent)
Dvořák et al. dokázali, že 4-kritická graf bez trojúhelníků vnořený v toru má pouze omezeně mnoho stěn délky větší než 4 a velikost těchto stěn je také omezena. V této práci studujeme operaci redukce těchto vnořených grafů pomocí sjednocení protějších vrcholů ve 4-stěnách. Představíme počítačem asistovaný důkaz ukazující, že existují právě čtyři 4-kritické grafy bez trojúhelníků vnořené do toru, které jsou irreducibilní, tedy na ně není možné použít redukci bez vzniku trojúhelníků. Pomocí tohoto výsledku ukážeme několik vlastností, které nutně platí pro jakýkoliv 4-kritický graf bez trojúhelníků vnořený v toru. Především ukážeme, že každý takový graf má nejvýše čtyři 5-stěny nebo 6-stěnu a dvě 5-stěny nebo 7-stěnu a 5-stěnu, a k tomu alespoň sedm 4-stěn.
|
|
|
Hamiltonovské kružnice v Kneserových grafech
Hulcová, Tereza ; Šámal, Robert (vedoucí práce) ; Gregor, Petr (oponent)
V této práci se budeme zabývat existencí hamiltonovských kružnic v Kneserových grafech: graf K(n, k) obsahující jako množinu vrcholů všechny k-tice z n prvků. Hranou jsou spojeny pouze disjunktní dvojice. Lovászova hypotéza o vrcholově tranzitivních gra- fech implikuje hamiltonovskost K(n, k) pro n ≥ 2k + 1. Chen ukázala, že K(n, k) jsou hamiltonovské pro n ≥ 3k, později vylepšila svůj výsledek na n ≥ 2.6k + 1. V obou pří- padech použila Baranyaiho rozklad. Nedávný důkaz hypotézy středních vrstev umožnil dokázat, že bipartitní Kneserovy grafy obsahují hamiltonovskou kružnici. S některými ze zmíněných důkazů seznámíme čtenáře podrobněji.
|
|
|
Game variants of graph labeling
Jedličková, Nikola ; Šámal, Robert (vedoucí práce) ; Fiala, Jiří (oponent)
Značkovanie na grafe, nazývané tiež labeling, je zobrazenie z množiny vrcholov alebo hrán do množiny značiek L ⊆ N∪{0}. Popri prehl'ade doteraz známych hracích variant predstavíme aj nový typ labelingu - ESD labeling a s ním súvisiacu hraciu variantu, ktorá bola inšpirovaná článkom Tuzu. ESD labeling na grafe G je prosté zobrazenie φ : V (G) → {1, . . . , n}, kde pre každé dve rôzne hrany platí, že súčet značiek na ich koncových vrcholoch je rôzny. Okrem otázky existencie ESD labelingu sa budeme zaoberat' aj hracou variantou, kde labeling po- stupne vytvárajú dvaja hráči. 1
|
|
|
Poziční hry s efektivní vítěznou strategií
Svoboda, Jakub ; Šámal, Robert (vedoucí práce) ; Valla, Tomáš (oponent)
V práci zkoumáme hry, ve kterých dva hráči obarvují hrany nekonečného úplného grafu a snaží se vytvořit určitý, cílový, podgraf obarvený svou barvou. Nejprve se budeme uvažovat situaci, kdy cílový podgraf je úplným grafem a uká- žeme, že první hráč má vyhrávající strategii, když je cílový podgraf úplný graf na nejvýše třech vrcholech. Potom lehce změníme podmínky hry a ukážeme, že první hráč má vyhrávající strategii, pokud může omezit graf, na kterém se hraje, nebo zahrát několik tahů navíc. Nakonec budeme uvažovat hru, v níž musí být minorem cílového podgrafu úplný graf. Ukážeme vyhrávající strategii pro malou velikost úplného grafu, který musí být minorem cílového podgrafu a zamyslíme se nad důvody, proč by první hráč měl vyhrát jakoukoliv hru tohoto typu. 1
|
|
|
Algoritmus pro dokreslování rovinných nakreslení
Hora, Martin ; Jelínek, Vít (vedoucí práce) ; Šámal, Robert (oponent)
Tento text se zabývá problémem dokreslování rovinných grafů. Vstupem pro- blému je graf G, jehož podgraf je již nakreslen do roviny. Cílem je pak rozhodnout, zda lze do roviny dokreslit i zbytek grafu G, a získat tak rovinné nakreslení G. Již bylo dokázáno, že lze dokreslitelnost rovinných grafů řešit v lineárním čase. Avšak všechny známé lineární algoritmy jsou poměrně komplikované, a pravděpodobně proto nebyla zveřejněna žádná jejich implementace. V práci představíme nový jednodušší lineární algoritmus řešící dokreslitelnost a dokážeme jeho korektnost. Dále pak k této práci přiložíme implementaci tohoto algoritmu v programovacím jazyce C++. 1
|
|
|
Matching covers of cubic graphs
Slívová, Veronika ; Šámal, Robert (vedoucí práce) ; Rollová, Edita (oponent)
Hypotéza Berge a Fulkersona říká, že každý kubický graf bez mostů lze pokrýt šesti perfektními párováními tak, aby každá hrana byla obsažena právě ve dvou z nich. Další hypotéza od Berge říká, že každý kubický graf bez mostů lze pokrýt pomocí pěti perfektních párování. Obě hypotézy jsou zkoumány přes čtyřicet let. Abreu a kol. [2016] vytvořili novou třídu kubických grafů, zvanou treelike snarky a ukázali, že grafy z této třídy nemohou být pokryty méně než pěti perfektními párováními. My ukážeme, že jejich dolní odhad na počet perfektních párování je těsný. Bergovu domněnku dokonce dokážeme pro větší třídu grafů. Nakonec ukážeme, že také Berge-Fulkersonova hypotéza platí pro třídu treelike snarků.
|
|
|
Zobrazování mnohostěnů v různých dimenzích
Ondráček, Lukáš ; Šámal, Robert (vedoucí práce) ; Mareš, Martin (oponent)
Práce se zabývá implementací aplikace pro vykreslování tří- a vícerozměrných mnohostěnů s možností plynulé rotace. Aplikace Geometric Figures pro Linux a Windows je napsána v jazyce C s použitím OpenGL a podporuje zásuvné moduly psané v Pythonu. K vykreslování je použita iterovaná perspektiva s barvením hran podle jejich polohy. Aplikace dále umožňuje hledání konvexního obalu množiny bodů, řezy tělesa nadrovinou, stelaci, vytvoření geometricky duálního tělesa a odřezávání částí tělesa; vše nezávisle na počtu rozměrů. Výhodou této aplikace oproti již existujícím je její snadná rozšiřitelnost pomocí modulů a otevřenost zdrojového kódu. Powered by TCPDF (www.tcpdf.org)
|
|
|
Průnikové reprezentace grafů
Töpfer, Martin ; Jelínek, Vít (vedoucí práce) ; Šámal, Robert (oponent)
Průnikový graf je graf, ve kterém mezi dvěma vrcholy vede hrana, právě když jim odpovídající objekty se protínají. Tato práce se zabývá průnikovými grafy L-útvarů (tzv. L-grafy) a jejich speciálním případem, kdy konce všech L-útvarů jsou na jedné přímce (tzv. vnějškovými L-grafy). Po přehledu, co platí o L-grafech, používáme podobné postupy na vnějškové L-grafy. Ukážeme, že intervalové grafy, tětivové grafy (circular graphs) a vnějškově rovinné grafy jsou vnějškové L-grafy. Poté charakterizujeme vnějškové L-grafy pomocí uspořádání vrcholů bez zakázaných vzorů. Powered by TCPDF (www.tcpdf.org)
|
|
|
Souvislost a resilience grafů
Novotná, Jitka ; Pangrác, Ondřej (vedoucí práce) ; Šámal, Robert (oponent)
Graf je k-resilientní, jestliže pro každý jeho vrchol existují lokální routovací tabulky takové, že podle nich lze z každého vrcholu dojít do jednoho označeného jako cíl. Existuje domněnka, že k-resilience je ekvivalentní hranové (k+1)-souvislosti. Toto dokazujeme pro hranově 3-souvisle grafy a hranově 4-souvislé rovinné triangulace. Při důkazu používáme nezávislé orientované kostry. Dvě kostry jsou nezávislé, pokud žádnou hranu nepoužijí ve stejné orientaci. Pro k=3,4 ukazujme, že graf má k nezávislých koster, právě tehdy když je hranově k-souvislý. Kostry hledáme konstruktivně pomocí redukcí částí grafu. Některé redukce mohou být použity i pro obecný k-souvislý případ. Powered by TCPDF (www.tcpdf.org)
|
host ::
RSS.