|
|
Vlastnosti grafů velkého obvodu
Volec, Jan ; Kráľ, Daniel (vedoucí práce) ; Sereni, Jean-Sébastien (oponent)
V práci zkoumáme dva náhodné procesy pro kubické grafy velkého obvodu. První proces nalezne pravděpodobnostní distribuci na hranových řezech takovou, že každá hrana je v náhodně vybraném řezu s pravděpodobností alespoň 0.88672. Jako důsledek odvodíme dolní odhad na velikost největšího řezu pro kubické grafy velkého obvodu a pro náhodné kubické grafy, a dále též horní odhad na váhu nejmenšího zlomkového pokrytí hranovými řezy pro kubické grafy velkého obvodu. Druhý proces nalezne pravděpodobnostní distribuci na nezavislých množinách takovou, že každý vrchol je v nezávislé množině s pravděpodobností alespoň 0.4352. Z toho plyne dolní odhad na velikost největší nezavíslé množiny pro kubické grafy velkého obvodu a pro náhodné kubické grafy, a dále též horní odhad na zlomkovou barevnost pro kubické grafy velkého obvodu.
|
|
| |
|
|
Immersions and edge-disjoint linkages
Klimošová, Tereza ; Dvořák, Zdeněk (vedoucí práce) ; Kráľ, Daniel (oponent)
Grafové imerze jsou přirozená analogie k intenzivně zkoumanému konceptu grafových minorů a topologických grafových minorů, ale teorie v této oblasti je mnohem méně rozvinutá. V práci se zabýváme hledáním postačujících podmínek pro existenci imerzí a vlastnostmi grafů, které neobsahují imerzi daného grafu. Dokazujeme, že velká stromová šířka hranově čtyřsouvislého grafu implikuje existenci imerze libovolného čtyřregulárního grafu na malém počtu vrcholů, a že velký maximální stupeň hranově třisouvislého grafu implikuje existenci imerze libovolného třiregulárního grafu na malém počtu vrcholů.
|
|
|
Structural Graph Theory
Hladký, Jan ; Kráľ, Daniel (vedoucí práce) ; Keevash, Peter (oponent) ; Krivelevich, Michael (oponent)
disertační práce Structural graph theory Jan Hladký V práci se zabýváme domněnkou Loebla, Komlóse a Sósové, která je kla- sickým problémem extremální teorie grafů. Dokážeme následující slabou verzi domněnky: pro libovolné α > 0 existuje číslo k0 takové, že pro každé k > k0 a každý n-vrcholový graf G obsahující alespoň (1 2 + α)n vrcholů stupně ale- spoň (1 + α)k platí, že G obsahuje každý strom T na k vrcholech jako podgraf. Důkaz tohoto výsledku sleduje strategii běžnou v přístupech využívajících Szemerédiho regularity lemma: nejdřív je graf G rozložen a v tomto rozkladu je nalezena kombinatorická struktura s vhodnými vlastnostmi. V posledním kroku je strom T vnořen do G pomocí této struktury. Rozklad zaručený původním regularity lemmatem je ovšem triviálni pokud je G řídký. Abychom obešli toto omezení, vyvineme rozkladovou techniku která umožňuje postihnout i strukturu řídkých grafů: každý graf může být rozložen do vrcholů s velkým stupněm, regulárních párů (ve smyslu regularity lemmatu) a dvou dalších částí, které mají jisté expandující vlastnosti. Výsledky v této práci byly dosaženy s následujícími spolupracovníky: János Komlós, Diana Piguet, Miklós Simonovits, Maya Jakobine Stein,...
|
|
|
Datové struktury pro setříděné ukládání dat
Bulánek, Jan ; Koucký, Michal (vedoucí práce) ; Kráľ, Daniel (oponent)
V předložené práci studujeme dvě varianty přihrádkovací hry. Tato hra je použita v důkazu spodniho odhadu časové složitosti vkládání prvků do setříděného pole. Ukážeme, že tyto varianty přihrádkovací hramy jí až na konstantní faktor ekvivalentní časovou složitost. Dále ukážeme výhody použití setříděných polí z hlediska vyrovnávacích pamětí. Na závěr ukážeme jednu možnou implementaci vyhledávání datové struktury s použití velikosti n1+e.
|
|
|
Rothova věta o aritmetických posloupnostech
Krkavec, Michal ; Klazar, Martin (vedoucí práce) ; Kráľ, Daniel (oponent)
Název práce: Rothova věta o aritmetických posloupnostech Autor: Michal Krkavec Katedra: Katedra aplikované matematiky Vedoucí bakalářské práce: doc. RNDr. Martin Klazar, Dr., Katedra aplikované matematiky Abstrakt: V předložené práci se zabýváme vlastnostmi množin přirozených čí- sel neobsahujících aritmetické posloupnosti. Cílem této práce je podat přehled a srovnání analytických a kombinatorických důkazů Rothovy věty, která tvrdí, že každá množina s kladnou horní asymptotickou hustotou obsahuje aritmetic- kou posloupnost délky tři. Zaměříme se také na vývoj poznatků od Erd˝osovy- Turánovy domněnky přes Rothovu větu až ke slavné Szemerédiho větě, která podala odpověď pro aritmetické posloupnosti libovolné délky k. V závěru práce se seznámíme s odhady čísla r3(n), které odpovídá největší velikosti podmnožiny A ⊆ [n], jež neobsahuje žádné aritmetické posloupnosti délky tři. Ukážeme dvě konstrukce, jak takové množiny A ⊆ [n] vybrat. Klíčová slova: Aditivní teorie čísel, Aritmetická posloupnost, Rothova věta, Elki- nova konstrukce
|
|
|
Rozklady grafů
Škoda, Petr ; Kráľ, Daniel (vedoucí práce) ; Fiala, Jiří (oponent)
Submodulární rozkladové funkce zobecňují známé druhy stromových rozkladů grafů. Pro každé pevné k existují polynomiální algoritmy, které rozhodují, zda je stromová či větvená šířka nejvýše k. My ukážeme, že neexistuje algoritmus, který by rozhodoval, zda je šířka dané submodulární rozkladové funkce nejvýše dva v čase menším než exponenciálním. Dále popíšeme novou duální strukturu pro submodulární rozkladové funkce podobnou volným zámotkům pro souvislostní funkce.
|
|
|
Optimalizace na grafech s omezenou stromovou šířkou přes vlastnosti vyjádřitelné v MSOL
Koutecký, Martin ; Kolman, Petr (vedoucí práce) ; Kráľ, Daniel (oponent)
Courcellova věta mluví o výpočetní složitosti rozhodovacích problémů defino- vaných formulemi monadické logiky druhého řádu nad relačními strukturami s omezenou stromovou šířkou. Pro pevnou stromovou šířku a vstupní formuli dává Courcellova věta algoritmus, který formuli rozhodne v lineárním čase nad strukturou dané stro- mové šířky. Práce podává samostatný důkaz Courcellovy věty pomocí metod teorie konečných modelů. Dále obsahuje důkazy všech potřebných prerekvizit hlavního důkazu, zejména v teorii konečných modelů široce využívané Ehrenfeuchtovy-Fraïssého věty. Práce též obsahuje implementaci algoritmu plynoucího z tohoto důkazu. Nakonec nastiňuje aktuální stav výzkumu dané oblasti a z něj plynoucí možnosti. 1
|
|
|
Optical and magneto-optical properties of Heusler compounds
Král, Daniel ; Veis, Martin (vedoucí práce) ; Mistrík, Jan (oponent)
Cílem této práce bylo studium Heuslrových sloučenin pomocí optických a magneto-optických (MO) metod. V případě první sloučeniny, Co2FeGa0.5Ge0.5, jsme studovali výskyt strukturálního disorderu za pomoci spektroskopické elipsometrie, MO spektroskopie a MO Kerrovy magnetome- trie. Experimentální výsledky jsme poté porovnali s teoretickými modely. Doplnili jsme také výsledky našich spolupracovník·, a to včetně X-ray difrakce, atomic-force mikroskopie a ab initio výpočt·, abych potvrdili naši interpretaci naměřených výsledk·. Bylo zjištěno, že strukturální disorder je vskutku pozorovatelný pomocí metod, kterých jsme využili. Jeho výskyt se projevil změnou elektronové struktury vzork·. V případě druhé sloučeniny, Fe2MnGa, jsme vyšetřovali vliv obsahu Fe složky na optické a MO vlastnosti tohoto materiálu. Zjistili jsme, že atomy Fe ovlivňují koncentraci volných elektron·, čímž dodávají sloučenině kovový charakter (v porovnání s Ni2MnGa). Zároveň zvyšují optickou a MO odezvu v blízké infra-červené oblasti spektra. Dále bylo zjištěno, že vzorek s nejvyšším obsahem Fe má nulovou magnetizaci. 1
|
|
|
Zakázané minory pro apexové třídy grafů
Klimošová, Tereza ; Kráľ, Daniel (vedoucí práce) ; Dvořák, Zdeněk (oponent)
V předložené práci se zabýváme hledáním minimálních zakázaných minorů, neboli obstrukcí, pro třídu apexů částečných 2-stromů. Jelikož je tato třída uzavřená na minory, má podle Robertson-Seymourovy věty konečnou množinu obstrukcí. Množina obstrukcí je jedna z možných charakterizací každé třídy uzavřené na minory. V práci analyzujeme strukturu obstrukcí pro třídu apexů částečných 2-stromů a díky její znalosti nacházíme všechny obstrukce s výjimkou speciálního typu obstrukcí, které mají path-width 3. Při hledání obstrukcí využíváme znalosti obstrukcí pro příbuzné třídy grafů.
|
host ::
RSS.