|
|
Cops and robber game on directed complete graphs
Slívová, Veronika ; Gavenčiak, Tomáš (vedoucí práce) ; Jelínek, Vít (oponent)
BAKALÁŘSKÁ PRÁCE - ABSTRAKT Veronika Slívová Tato práce se zabývá hrou Cops and robber (četníci a zloděj) na turnajích (graf vzniklý zorientováním hran úplného grafu). Ukážeme, že na polapení zloděje stačí málo četníků, pokud turnaj obsahuje vrchol vysokého výstupního stupně. Naopak počet četníků potřebný k polapení zloděje na libovolném turnaji nelze omezit. Dále se práce zabývá cirkulárními turnaji a turnaji vzniklými cyklickou orientací každé trojice ze Steinerovského systému trojic. Vyvrátíme domněnku Geňi Hahna, že počet četníků potřebný k polapení zloděje na libovolném grafu, který vznikl orientací Steinerovského systému trojic, je omezený. Dokážeme, že k polapení zloděje na libovolném cirkulárním turnaji, potřebujeme také neomezený počet četníků. Prozkoumáme i variantu 2-rychlého četníka, který vyhraje hru na libovolném turnaji prvním tahem. Naopak na turnajích s vrcholy stejného výstupního stupně je 2-rychlý zloděj polapitelný triviálně nebo jej nelze chytit.
|
|
|
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...
|
|
|
Ekologie opylovacích sítí
Hadrava, Jiří ; Janšta, Petr (vedoucí práce) ; Novotný, Vojtěch (oponent)
Rostliny a opylovači jsou ve společenstvech uspořádáni do spletité sítě vztahů. Pochopení struktury této sítě může pomoci porozumět dynamice společenstev a principu udržování biodiverzity. Znalosti o pozicích druhů v síti zase mohou mít své uplatnění v ochraně přírody. Cílem této práce je nastínit základní metodické principy tohoto konceptu, poukázat na jeho možné nedostatky, utvořit základní přehled metod analýz opylovacích sítí (založených na teorii grafů) a popsat první z výsledků srovnávání struktur opylovacích systémů napříč geografickými oblastmi - jednu z nových možností, které tento přístup ekologii opylování přinesl.
|
|
|
Statistické zpracování rozsáhlých dat ve svozových úlohách
Šmídová, Zlata ; Karpíšek, Zdeněk (oponent) ; Šomplák, Radovan (vedoucí práce)
Bakalářská práce se zabývá statistickým zpracováním rozsáhlých dat v dopravních úlohách a vyhodnocením těchto dat pro účely následné optimalizace provozu. Statistické testy byly prováděny v programech Microsoft Excel a STATISTICA. Po sestavení matematického modelu byla zpracovaná data nahrána do databáze SQLite a do programu GAMS (General Algebraic Modeling System), který vypočítal dobu strávenou na jednotlivých úsecích tras. Výsledky jsou důležité pro řešení dopravních a logistických problémů, kterými se zabývá mnoho firem a společností. Uvedený přístup představuje novou techniku pro tvorbu okrajových podmínek v dopravních úlohách. Výstupem jsou kvalitní vstupní data pro optimalizaci v logistice.
|
|
|
Optimalizace železniční dopravy odpadů
Ambrozková, Anna ; Hrabec, Dušan (oponent) ; Pavlas, Martin (vedoucí práce)
Tato bakalářská práce se zabývá optimalizací železniční dopravy odpadů. Teoretická část je věnována teorii grafů a optimalizaci, kde zmiňujeme například reprezentaci grafů, toky v sítích nebo lineární programování. V praktické části se pak zaměřujeme na porovnání silniční a železniční sítě, motivační příklad a aplikaci na reálných datech v celé České republice.
|
|
|
Stochastic Optimization of Network Flows
Málek, Martin ; Holešovský, Jan (oponent) ; Popela, Pavel (vedoucí práce)
The master's thesis focuses on the stochastic optimization in network flow problems. The theoretical part covers three topics - the graph theory, the optimization and the progressive hedging algorithm. Within the optimization the main part is devoted to the stochastic programming and the two-stage programming. The progressive hedging algorithm includes also the scenario aggregation and the modification of the general algorithm to two-stage problems. The practical part deals with models using real-world data of collection of municipal waste within the Czech Republic, which were provided by the Institute of Process Engineering.
|
|
|
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
|
|
|
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ů.
|
|
|
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
|
|
|
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.
|
host ::
RSS.