|
|
Hamiltonicity of hypercubes without k-snakes and k-coils
Pěgřímek, David ; Gregor, Petr (vedoucí práce) ; Fink, Jiří (oponent)
Had (cívka) je indukovaná cesta (cyklus) v hyperkrychli. Jsou známí především problé- mem hada v krabici (cívky v krabici) snažící se najít nejdelšího hada (cívku) v hyperkrychli. Jejich zobecnění k-hadi (k-cívky) zachovávají vzdálenosti mezi každými dvěma svými vr- choly, které jsou vzdálené nejvýše k−1 v hyperkrychli. Studujeme je v souvislosti s Lockeho hypotézou. Ta říká, že vyvážené množině F ⊆ V (Qn) vadných vrcholů v hyperkrychli veli- kosti 2m se lze vyhnout Hamiltonovským cyklem pokud n ≥ m+2 a m ≥ 1. My ukazujeme, že pokud S je k-had (k-cívka) pro n ≥ k ≥ 6 (n ≥ k ≥ 7), pak Qn −V (S) je Hamiltonovsky laceabilní. Pro fixované k může být počet vrcholů k-cívky až exponenciální vzhledem k n. Představujeme pojem draka, což je indukovaný strom v hyperkrychli a jeho zobecnění na k-draka, který zachovává vzdálenost mezi každými dvěma svými vrcholy, které jsou vzdá- lené nejvýše k − 1 v hyperkrychli. Dokazujeme specifické lemma které bylo v Bakalářské práci pouze ověřeno počítačem a dokončuje tak důkaz tvrzení o Hamiltonovské laceabilitě hyperkrychlí bez n-draků.
|
|
|
Probabilistic Methods in Discrete Applied Mathematics
Fink, Jiří ; Loebl, Martin (vedoucí práce) ; Koubek, Václav (oponent) ; Sereni, Jean-Sébastein (oponent)
Jedním ze základních problémů moderní statistické fyziky je snaha porozumět \mbox{frustraci} a chaosu. Základním modelem je konečně dimenzionální Edwards-Anderson Ising model. V této práci zavádíme zobecnění tohoto modelu. Studujeme množinové systémy uzavřené na symetrické rozdíly. Ukážeme, že významnou otázku, zda groundstate v Ising modelu je jednoznačný, lze studovat v těchto množinových systémech. Krewerasova hypotéza říká, že každé perfektní párování v hyperkrychli $Q_n$ lze rozšířit na Hamiltonovskou kružnici. Tuto hypotézu jsme dokázali. Matching graf $\mg{G}$ grafu $G$ má za vrcholy perfektní párování v $G$ a hranami jsou spojeny ty dvojice perfektních párování, jejichž sjednocení tvoří Hamiltonovskou kružnici v $G$. Dokážeme, že matching graf $\mg{Q_n}$ je bipartitní a souvislý pro $n \ge 4$. Toto dokazuje Krewerasovu hypotézu, že graf $M_n$ je souvislý, kde $M_n$ vznikne z grafu $\mg{Q_n}$ kontrakcí vrcholů $\mg{Q_n}$, které odpovídají izomorfním perfektním párováním. Cesta v $Q_n$ vyhýbající se zadaným $f$ chybným vrcholům se nazývá dlouhá, jestliže její délka je alespoň $2^n - 2f - 2$. Analogicky kružnice je dlouhá, pokud její délka je alespoň $2^n - 2f$. Pokud jsou všechny chybné vrcholy ze stejné bipartitní třídy $Q_n$, pak jsou tyto délky nejlepší možné. Dokážeme, že pro každou množinu...
|
|
|
Optimization and Statistics
Fink, Jiří ; Loebl, Martin (vedoucí práce)
CONTENTS Nazev prace: Autor: Katedra. (ustav-): Vedouci diplomove prace: E-mail vedouci'ho: Klicova slova: Abstrakt: Optimization and Statistics Jifi Fink Katedra aplikovane matematiky Doc. RNDr. Martin Loebl, CSc. loebl@kam.mff,cuni.cz Edwards-Anderson Ising model, Teorie grafu, T-join, Gaussovska distribuce Jedmm ze zakladnich problemu modern! statisticke fyziky je'snada porozumet frus- traci a chaosu. Zakladnim modelem je konecne dimenzionalni Edwards-Anderson Ising model. V optimalizaci to odpovida zkournani minimalnich T-joinu v konecnych mfizkach s nahodnymi vahami na hranach. V teto praci studujeme "random join", coz je nahodna cesta mezi dvema pevne danymi vrcholy. Puvodni definice je pfilis slozita, a tak jsme ukazali jednodussi. Tato deiinice je pouzita k pfesnemu vypoctu "random join" na kruznici. Take jsme ukazali specialni algoritmus, ktery hleda cestu v mrizce s danymi hranami. Tento algoritmus muze byt pouzit k experimentalnimu stu.dovani "random join". Title: Author: Department: Supervisor: Supendsor's e-mail address: Keywords: Abstract: Optimization and Statistics Jiff Fink Department of Applied Mathematics Doc. RNDr. Martin Loebl: CSc. loebl@kam.mff.cuni.cz Edwards-Anderson Ising model, Graph theory, T-join, the Gaussian distribution One of the basic streams of modern statistics physics is...
|
|
|
Optimization and Statistics
Fink, Jiří ; Kratochvíl, Jan (oponent) ; Loebl, Martin (vedoucí práce)
Jedním ze základních problémů moderní statistické fyziky je snada porozumět frustraci a chaosu. Základním modelem je konečně dimenzionální Edwards-Anderson Ising model. V optimalizaci to odpovídá zkoumání minimálních T-joinů v konečných mřížkách s náhodnými váhami na hranách. V této práci studujeme "random join", což je náhodná cesta mezi dvěma pevně danými vrcholy. Původní definice je příliš složitá, a tak jsme ukázali jednodušší. Tato definice je použita k přesnému výpočtu "random join" na kružnicí. Také jsme ukázali speciální algoritmus, který hledá cestu v mřížce s danými hranami. Tento algoritmus může být použit k experimentálnímu studování "random join".
|
host ::
RSS.