|
|
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...
|
|
|
Prvky teorie grafů v učivu matematiky na 1.stupni základní školy
Mutinová, Tatiana ; Kloboučková, Jaroslava (vedoucí práce) ; Slezáková, Jana (oponent)
Prvky teorie grafů v učivu matematiky na 1. stupni základní školy Ing. Tatiana Mutinová, 2014 Abstrakt Tato diplomová práce je zaměřena na teorii grafů, a to zejména na prvky, které jsou použitelné ve vyučování matematiky na 1. stupni základní školy. Dále se zabývá důvody, proč je potřebné grafové úlohy do výuky matematiky zařazovat. V teoretické části jsou uvedeny základní pojmy a definice z vybraných částí teorie grafů a na příkladech je ukázáno využití teorie grafů při řešení situací z reálného života. Praktická část mapuje současný stav uplatnění některých prvků teorie grafů v učivu matematiky na 1. stupni základní školy. Obsahuje také ukázku série gradovaných úloh a pracovní listy využitelné při zavádění a procvičování některých grafových pojmů. Experiment s mozaikami, který byl proveden v rámci této diplomové práce, je ukázkou propojení matematického a nematematického prostředí a badatelsky orientované výuky u dětí mladšího školního věku. Klíčová slova: matematika, teorie grafů, vrchol grafu, stupeň vrcholu grafu, hrana grafu, problém dvou barev, dítě mladšího školního věku
|
|
|
Computational Complexity in Graph Theory
Jelínková, Eva ; Kratochvíl, Jan (vedoucí práce) ; Manlove, David (oponent) ; Fiala, Jiří (oponent)
Název práce: Výpočetní složitost v teorii grafů Autor: Eva Jelínková Katedra: Katedra Aplikované Matematiky Vedoucí disertační práce: Prof. RNDr. Jan Kratochvíl, CSc., Katedra Aplikované Matematiky Abstrakt: Zabýváme se problémy teorie grafů, zejména z hlediska výpočetní složitosti. V první části práce se věnujeme výpočetní složitosti problémů sou- visejících se Seidelovým přepnutím grafů. Uvažujeme rozhodující problém, zda daný graf lze přepnout tak, aby obsahoval nejvýše daný počet hran. Dokážeme, že tento problém je NP-úplný, dokonce i pro grafy s omezenou hustotou. Částečně tak odpovídáme na otázku Matouška a Wagnera [Dis- crete Comput. Geom. 52, no. 1, 2014]. Popisujeme také nekonečně mnoho grafů H, pro které je NP-těžké rozhodnout, zda pro daný graf existuje graf, který je s ním ekvivalentní v přepnutí, a zároveň neobsahuje H jako induko- vaný podgraf. Tímto řešíme otevřený problém Kratochvíla, Nešetřila a Zýky [Annals of Discrete Math. 51, 1992]. Ve druhé části práce se zabýváme tématem párování s preferencemi. Zaměřujeme se na problém trhu s domy, konkrétně na model s duplicitními domy. Popisujeme 2-aproximační algoritmus pro maximální počet spoko- jených agentů v případě,...
|
|
|
Počítačové modelování větvených polymerů
Preisler, Zdeněk ; Uhlík, Filip (vedoucí práce) ; Netopilík, Miloš (oponent)
V této práci studujeme vlastnosti větvených polymerů v dobrém rozpouštědle. Zaměřili jsme se na problematiku související s gelovou permeační chromatografií (SEC) a predikci elučního chování náhodně větvených polymerů. Vyvinuli jsme software pro generování sobě se vyhýbajících procházek (SAW) pro libovolně větvenou architektoru bez cyklů na kubické mřížce pomocí metody Monte Carlo (MC) ověřený pomocí škálování různých architektur: lineární, 3-ramenná hvězdice, 6-ti ramenná hvězdice a asymetrická hvězdice. Vypočítali jsme distribuční koeficienty a kalibrační křivky SEC pro různé architektury a ověřili, že hydrodynamický poloměr je vhodnější pro predikci elučního objemu než gyrační poloměr. Dále jsme navrhli velice rychlou (i když přibližnou) metodu pro odhad středních hodnot gyračního a hydrodynamického poloměru založenou na výsledcích z teorie grafů korigovaných na lepší shodu s MC. Závěrem ukazujeme výpočet ochuzené vrstvky metodou MC a self-consistent field (SCF) pro polymery a jejich srovnání. Ukazujeme také jak lze zlepšit SCF výpočty pro lepší shodu s MC výsledky.
|
|
| |
|
|
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ů.
|
|
|
Graph labeling
Böhm, Martin ; Mareš, Martin (vedoucí práce) ; Balyo, Tomáš (oponent)
Práce představuje výsledky v oblasti schémat pro značkování grafů, která kódují sousednost vrcholů. Tato schémata mají praktické aplikace v oblasti paralelních algoritmů, souvisí však i s teorií univezál- ních grafů. Práce se soustředí na moderní metodu Traversal and Jumping, jejíž důkaz správnosti je zjednodušen a opraven. Také se zabýváme hledáním malých univerzálních grafů hrubou silou. 1
|
|
|
Teorie grafů a její výskyt ve školské matematice
Glasová, Ester ; Novotná, Jarmila (vedoucí práce) ; Dvořák, Petr (oponent)
Teorie grafů a její výskyt ve školské matematice Diplomová práce se zabývá možnostmi zařazení některých úloh z teorie grafů do výuky na gymnáziu a základní škole. Obsahuje potřebnou teorii pro učitele; je v ní uvedeno několik příkladů, kde se vyskytla teorie grafů ve školské matematice na základní škole, a také popsáno několik všeobecně známých úloh, k jejichž řešení se používá teorie grafů. Součástí práce jsou i přípravy dvou vyučovacích hodin. Tématem první z nich je kreslení jedním tahem a Eulerovský tah obecně. Druhá je věnována bludištím, labyrintům, jejich přetváření na graf a zkoumání možných algoritmů na procházení bludištěm. V experimentální části autorka zkoumá, zda jsou žáci schopni pochopit vybrané části z teorie grafů a zda jim připadá, že je tato látka zábavnější než matematika, na kterou jsou ze školy zvyklí. Výsledky tohoto experimentu jsou srovnávány pro děti ze základní školy a víceletého gymnázia.
|
|
|
Meze pro vzdálenostně podmíněné značkování grafů
Kupec, Martin ; Fiala, Jiří (vedoucí práce) ; Dvořák, Zdeněk (oponent)
Problém λ − L(p, q)-značkování je přiřadit vrcholům grafu značky {0, . . . , λ} tak, aby sousední vrcholy měly značky od sebe vzdálené alespoň p a vrcholy se společným sousedem značky od sebe vzdáleny alespoň q. Zabýváme se výpočení složitostí tohoto problému a stanovujeme hraniční hodnoty λ, p a q, pro které se tento problém stává NP těžký. Důkaz je veden promocí dvou různých redukcí. Jedna je z NAE-3SATu, druhá z problémů hranového dobarvení před- barveného grafu. 1
|
|
|
Architektura regulační sítě metabolismu
Geryk, Jan ; Flegr, Jaroslav (vedoucí práce) ; Cvrčková, Fatima (oponent) ; Šafránek, David (oponent)
Předkládaná disertační práce se zabývá modularitou metabolických sítí a především architekturou regulační sítě metabolismu, která reprezentuje přímé regulační interakce mezi metabolity a enzymy. V první práci se zabývám problematikou tzv. "modularity measure", což je kvantitativní míra modularity sítě používaná pro účely identifikace modulů. Bylo zjištěno, že při maximalizaci této veličiny v síti může dojít k chybnému sloučení dvou jednoznačne vyjádřených modulů v jeden. Maximální velikost modulu u kterého existuje riziko, že je tvořen dvěma moduly je známa jako rozlišovací limit modularity measure. V mé první práci je tento rozlišovací limit zobecněn, což umožňuje nahlédnout jeho podstatu v použití nulového modelu. Zároveň je zde ukázáno, že riziko chybného sloučení existuje i v případě větších modulů, než bylo uváděno v původní práci. Druhá práce je zaměřena na otázku, jak se změní modularita metabolické sítě E.coli po přidání regulačních vazeb. Bylo zde ukázáno, že modularita mírně nicméně signifikantně vzroste, zaměříme-li se na modulární jádro sítě. Identifikované moduly jsou funkčně interpretovatelné jako regulačně autonomí části metabolismu. Zvýšení modularity vzhledem k nulovému modelu lze považovat za nepřímý důsledek potřeby lokální regulace některých částí metabolické sítě. Vznik...
|
host ::
RSS.