Národní úložiště šedé literatury Nalezeno 28 záznamů.  1 - 10dalšíkonec  přejít na záznam: Hledání trvalo 0.00 vteřin. 
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...
Nekonečné matroidy
Böhm, Martin ; Pangrác, Ondřej (vedoucí práce) ; Loebl, Martin (oponent)
Práce prezentuje aktuální pokroky v oblasti teorie nekonečných matroidů. V práci jsou zadefinovány a dokázány základní vlastnosti nekonečných matroidů a předvedeny známé třídy těchto struktur. Práce se zaměřuje na problematiku souvislosti nekonečných matroidů a poukazuje na vztahy některých matroidových operací se souvislostí. Hlavní výsledek práce ukazuje existenci nekonečných matroidů libovolné konečné souvislosti se speciálními vlastnostmi -- bez konečných kružnic a kokružnic. Powered by TCPDF (www.tcpdf.org)
Representation of special classes of combinatorial objects
Scholleová, Barbora ; Nešetřil, Jaroslav (vedoucí práce) ; Loebl, Martin (oponent)
V této práci se pokoušíme propojit poznatky ze dvou oblastí teorie grafů. Nejprve uvádíme základní pojmy týkající se homomorfismů grafů. Text směřuje k defi- nici nahrazovací operace užitím vhodného nahrazovacího grafu. Dále popisujeme vlastnosti stromové hloubky, jedné z význačných charakteristik každého grafu. Posléze se zabýváme reprezentacemi kategorií v kategorii Graph všech konečných grafů a Graphk všech konečných grafů se stromovou hloubkou nejvýše k.
Structural Graph Theory
Zamora, José ; Loebl, Martin (vedoucí práce) ; Sereni, Jean Sébastien (oponent) ; Fiala, Jiří (oponent)
V práci studujeme čtyři problémy ze strukturální teorie grafů. Nejprve se zabýváme strukturou grafů které mají nikde nenulový 5-tok. Podáme charakteri- zaci takových grafů pomocí existence (1, 2)−faktorů. Ve druhé části zavedeme nový typ dekorace vrcholů grafu, kterému říkáme aditivní barvení. Aditivní barvení je injektivní barvení s omezeními danými grafem. Studujeme strukturu grafů které mají tuto dekoraci, a související algoritmické otázky. Ve třetí časti studujeme hypotézu kterou formuloval před asi dvaceti lety R. Stanley: je pravda, že U-polynom rozlišuje neizomorfní stromy? Dokážeme tuto hypotézu pro stromy- housenky bez vrcholů stupně dva. O tento výsledek se v minulých letech snažila řada vědců, například S. Noble. Ve čtvrté části studujeme strukturu nekonečných grafů které mají uplný graf jako minor nebo topologický minor. Klíčová slova: graf, nikde nenulový tok, faktor grafu, barvení grafů, izomorfismus grafů, strom, U-polynom, minor, topologický minor.
Transport optimization
Šimora, Peter ; Kučera, Luděk (vedoucí práce) ; Loebl, Martin (oponent)
Vzhledem ke klesajícím zásobám ropy a stoupající populaci je potřebné zabývat se otázkou logistiky. V naší práci jsme zvolili železniční dopravu. Její výhody spočívají ve vybudovaném traťovém systému a vozovém parku. Optimalizaci a měření vykonáváme na železniční síti České republiky. Jednotlivé balíky generujeme na základě počtu obyvatel míst, ve kterých stanice leží. Pro každý balík volíme optimální přepravní trasu. Balíky přiřazujeme k vlakům tak, abychom zmenšili celkový počet najetých kilometrů a ukládáme je do jednotlivých vagónů tak, aby se jich tam vešel co největší možný počet. Měřeními jsme zjistili, že při optimálním počtu vygenerovaných balíků za hodinu je celkový počet najetých kilometrů vlaky v našem algoritmu o 36% menší jako u jednoduchého algoritmu.
Geometric and algebraic properties of discrete structures
Rytíř, Pavel ; Loebl, Martin (vedoucí práce) ; Serra, Oriol (oponent) ; Kaiser, Tomáš (oponent)
V práci se zabýváme dvou-dimenzionálními simpliciálními komplexy a lineárními kódy. Řekneme, že lineární kód C nad tělesem F je trojúhelníkově reprezentovatelný, pokud exis- tuje dvou-dimenzionální simpliciální komplex ∆ takový, že kód C je propíchnutým kódem jádra ker ∆ incidenční matice simpliciálního komplexu ∆ nad F a dim C = dim ker ∆. Tento simpliciální komplex nazveme geometrickou reprezentací kódu C. Dokážeme, že každý lineární kód nad prvotělesem je trojúhelníkově reprezentovatelný. Pro konečná prvotělesa sestrojíme geometrickou reprezentaci takovou, že váhový polynom kódu C je dán jednoduchou formulí váhového polynomu prostoru cyklů simpliciálního kom- plexu ∆. Tedy geometrická reprezentace kódu C určuje jeho váhový polynom. Naše motivace pochází z teorie pfaffiánovských orientací grafů, která poskytuje polyno- miální algoritmus pro výpočet váhového polynomu prostoru řezů grafu s omezeným rodem. Tento algoritmus využívá geometrických vlastností nakreslení grafu na orientovatelnou ri- emannovskou plochu. Prostor řezů je lineární kód a odpovídající graf je jeho užitečnou geometrickou reprezentací. Dále studujeme vnořitelnost geometrických reprezentací do euklidovských prostorů. Ukážeme, že každý binární lineární kód má geometrickou reprezentaci v R4 . Charakte- rizujeme binární lineární kódy, které...
Dekompozice orientovaných a neorientovaných grafů
Pelikánová, Petra ; Loebl, Martin (vedoucí práce) ; Klimošová, Tereza (oponent)
Eulerovské grafy lze nakreslit jedním uzavřeným tahem. Nalezení takového tahu ob- sahujícího každou hranu právě jednou je základním problémem hledání ideální trasy. Většina problémů založených na silniční síti, vyskytujících se v oblasti operační analýzy, je NP-těžkých. Vytvořili jsme formální model silniční sítě a tras vozidel díky němuž jsme formulovali několik problémů motivovaných zimní údržbou silnic v České republice. Hlavní pozornost je věnována trasování pro jedno vozidlo se silniční sítí popsanou grafem bez kružnic, tedy stromem. Představujeme nový minimalizační problém hledání trasy vozidla s vlastnostmi, které předcházejí stížnostem na nedostatečnou zimní údržbu. Stížnosti posílají většinou lidé, kteří mají pocit, že vozidlo jelo kolem a minulo je. Dokázali jsme, že tento problém je PPA-úplný tím, že jsme na něj převedli zajímavý kombinatorický problém "necklace splitting" (jak rozdělit uloupený náhrdelník s různými druhy kamenů férově mezi několik loupežníků s minimálním počtem roztržení, aby každý dostal od všech kamenů stejný počet jako ostatní). Dálší studovaný problém je hledání trasy se splněním podmínek daných českou le- gislativou. Dokázali jsme, že existuje polynomiální algoritmus, který pro stromy s jednou důležitostí silnic rozhodne, zda lze graf projet jedním vozidlem. V souvislosti s...
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...

Národní úložiště šedé literatury : Nalezeno 28 záznamů.   1 - 10dalšíkonec  přejít na záznam:
Chcete být upozorněni, pokud se objeví nové záznamy odpovídající tomuto dotazu?
Přihlásit se k odběru RSS.