|
|
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
|
|
|
Duhové aritmetické posloupnosti a extremální množiny v mřížkách
Voborník, Jan ; Šámal, Robert (vedoucí práce) ; Pangrác, Ondřej (oponent)
Když jsou čísla $1,\ldots,tn$ obarvena $t$ barvami (každá je užita $n$-krát), existuje mezi nimi duhová aritmetická posloupnost délky $k$. (Duhová aritmetická posloupnost je taková, která nemá žádné dva členy stejné barvy.) Toto platí pro $t>k^3$. Označme $T_k$ nejmenší takové $t$, pro které to platí. Hypotéza Jungiće a spol. říká, $T_k=O(k^2)$. Problém souvisí s extremálními problémy diskrétních hyperkrychlí. Představujeme metodu s mřížkami (diskrétní hyperkrychle, které mohou obsahovat nerozlišitelné prvky), která může vést k vylepšení odhadu $T_k$ až na $O(k^2\log k)$. V práci vyřešíme několik extremálních problémů v mřížkách, které mají důsledky v různých partiích matematiky. Například pomocí mřížek dokážeme hranovou isoperimetrickou nerovnost pro Hammingovu krychli, nalezneme bipartitní graf s maximálním součtem druhých mocnin stupňů a konvexní množinu $M\subseteq [0,b]\times[0,a]$ maximalizující funkci $G(M)=\int_{x=0}^a \lambda_1(M_x)^2+\int_{y=0}^b \lambda_1(M_y)^2$. Powered by TCPDF (www.tcpdf.org)
|
|
|
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
|
|
|
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
|
|
|
Minimal counterexamples to flow conjectures
Korcsok, Peter ; Šámal, Robert (vedoucí práce) ; Goodall, Andrew (oponent)
Říkáme, že graf má nikde-nulový k-tok, pokud umíme každé hraně přiradit její směr a přirozené číslo (<k) jako tok tak, aby pro každý vrchol $v$ byl celkový přítok a odtok stejný. Tutte vyslovil v roce 1954 hypotézi, že každý graf bez mostů má nikde-nulový 5-tok, a tato hypotéza je stále otevřená. Kochol v nedávné práci představil výpočetní metodu na dokázání, že minimální protipříklad nemůže obsahovat krátkou kružnici (až do délky 10). V této práci poskytujeme ucelený přehled této metody a protože Kochol nezveřejnil svou implementaci (a pro nezávislé ověrení metody), doplňujeme náš zdrojový kód, ktorý potvrzuje Kocholovy výsledky a rozšiřuje je: dokázali jsme, že minimální protipříklad neobsahuje kružnici kratší než 12. Powered by TCPDF (www.tcpdf.org)
|
|
|
Varianty Eberhardovy věty
Šimečková, Zuzana ; Šámal, Robert (vedoucí práce) ; Fiala, Jiří (oponent)
Pro nakreslení rovinného grafu definujme posloupnost (pk) = (p3,p4, . . . ) po- čtů k-hranných stěn - k-úhelníků. Důsledkem Eulerova vzorce o rovinných grafech pro kubické grafy splňuje p vztah ∑ k>=3 (6 − k)pk = 12. Je celkem přirozené ptát se, jak vypadají p, pro která existuje odpovídající graf. Eberhard ukázal, že po- kud p splňuje výše uvedenou rovnost, pak existuje rovinný kubický graf, který odpovídá p až na počet šestiúhelníků. DeVos a kol. dokázali obdobu věty, kde je povoleno k p přidat pětiúhelníky a sedmiúhelníky. V této práci na jejich výsledky navazujeme, využijeme jejich důkazové strategie a díky navrženému programu na- jdeme stavební bloky, které autorům k zobecnění věty chyběly. Výsledkem práce je následující věta: pro každou dvojici r,s ∈ N splňující s < 6 < r < 14, s,r nesou- dělné, platí následující věta: pro každou posloupnost p nezáporných celých čísel splňující ∑ k>=3 (6 − k)pk = 12 existuje nekonečně mnoho kubických rovinných grafů, které p odpovídají až na r-úhelníky a s-úhelníky. 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
|
|
|
Persistentní homologie a neuronové sítě
Černý, Marek ; Šámal, Robert (vedoucí práce) ; Tancer, Martin (oponent)
Hluboké učení prakticky vyřešilo nejrůznější problémy počítačového vidění v průběhu poslední dekády. V práci používáme grupy persistentní homologie z výpočetní topolo- gie k analýze prostorů vnitřních representací příznaků v konvolučních neuronových sítích (CNN). Pozorovali jsme souvislost mezi souhrny homologických persistentních grup rozhodovací hranice a chybou tréninku sítě ResNet-18 v průběhu fenoménu hlubokého dvojitého pok- lesu. Navíc jsme se zaměřili na zvlaštní případ souhrnu, který poukazuje na analogii dvojitého sestupu ve směru epoch, což by mohlo vést lepšímu pochopení vnitřních repre- sentací v průběhu kriticky parametrizovaného režimu sítě. V hlavní části navrhujeme a porovnaváme několik přístupů k procesingu samotných modelů CNN sítí pomocí persistentní homologie. Naše nejlepší metoda zvaná Derivo- vatelný persistentní estimátor kvality (DPAE) dosahuje vysoké přesnosti v predikci kval- ity CNN sítí (tj. R2 skore téměř 0.99). DPAE je topologicky optimalizovatelná end-to-end architektura zahrnující derivovatelný výpočet persistence. Co více, DPAE metoda předčí i původní metodu využívající klasického strojového učení, které byla vytvořena přímo pro dataset, který používáme k testování. Veřejně dáváme k dispozici zdrojový kód jak metody DPAE tak ostatních prezentovaných experimentů. 1
|
|
|
Identification of bilinear systems
Kršková, Iveta ; Mareš, Martin (vedoucí práce) ; Šámal, Robert (oponent)
Názov práce: Identifikácia bilineárnych systémov Autor: Iveta Kršková Katedra: Katedra aplikovanej matematiky Vedúci práce: Mgr. Martin Mareš, Ph.D., Katedra aplikovanej matematiky V tejto práci sa venujeme štúdiu identifikácie systémov s bilineárnou štruktúrou. Náš hlavný záujem tkvie v identifikácii chemických reakčných sieti s biologickým pozadím. Identifikácia takýchto systémov je extrémne užitočná. Pokiaľ takýto model získame, môže byť použitý na riadenie určitých procesov v ľudskom tele. Za účelom správneho prevedenia tak komplexného procesu ako je systémova identifikácia, najskôr študujeme vlastnosti lineárnych a bilineárnych systémov dôležitých z hľadiska systémovej identifikácie. Vhodnosť bilineárnych systémov na modelovanie chemických reakčných sieti je diskutovaná. Niekoľko prístupov používaných na odhad parametrov je preštudovaných. Identifikačná metóda navrhnutá Juangom je implementovaná a rozsi- ahlo študovaná na príklade systému popisujúceho rast peptidového reťazca. Spôsob ako vhodne zvoliť parametre pri procedúre identifikácie bilineárnych systémov je ilustrovaná na spomínanom príklade. Skúsenosti získané s Juangovou metódovou sú uvedené v zá- vere. 1
|
|
|
Structural properties of random networks with dynamics
Gajdová, Anna ; Hartman, David (vedoucí práce) ; Šámal, Robert (oponent)
Reálné systémy jsou často reprezentovány pomocí takzvaných komplexních sítí. Tyto sítě mají charakeristickou konektivitní strukturu danou specifikami studovaných systémů. Jelikož často nejsou dostupná dostatečná data či jsou tato nepřesná, častým postupem je modelovat tyto systémy na úrovni této konektivity pomocí náhodných sítí replikující specifické vlastnosti, například snadnou propojitelnost, modularitu či specifickou řídkost. Reprezentace těchto vlastností v základních síťových modelech je hojně prozkoumaná oblast. Pokud je ovšem přítomnost hran řízena speciálními rozděleními či pokud je k celkovému modelu přidán ještě prvek dynamiky celého grafu, tak se stává analýza takových modelů složitější. Práce si klade za cíl prozkoumat vlastnosti takto dynamicky závislých náhodných modelů. 1
|
host ::
RSS.