Název: Dekompozice orientovaných a neorientovaných grafů
Překlad názvu: Decompositions of directed and undirected graphs
Autoři: Pelikánová, Petra ; Loebl, Martin (vedoucí práce) ; Klimošová, Tereza (oponent)
Typ dokumentu: Diplomové práce
Rok: 2021
Jazyk: cze
Abstrakt: [cze] [eng]
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... Eulerian graphs have a closed walk traversing each edge exactly once. Finding such a walk is a basic arc routing problem based on a road network. Most of the problems with applications in operational research are NP-hard. We describe a formal model of a road network and vehicle routes and formulate several arc routing problems motivated by winter road maintenance in the Czech Republic. The main part is focused on single vehicle routing problems on trees. We propose a new unfairness minimization problem for finding a vehicle route with properties that lead to a minimal number of resident complaints against unfair maintenance. Residents feel like they are skipped when the vehicle route has multiple trips and passes nearby without providing maintenance to their street. By reduction of the necklace splitting problem to the unfairness minimization problem we prove it is PPA-complete. Further, we define a restricted arc routing problem on trees which formalize condi- tions given by Czech legislation. We proved the existence of a polynomial algorithm for deciding whether a single vehicle route exists when there is a single priority for roads. If multiple priorities are used, we express conditions and conjectures when the problem has polynomial complexity. Finally, a utilization of the model is illustrated by an...
Klíčová slova: algoritmus; cyklus; dekompozice; eulerovská procházka; graf; algorithm; closed eulerian walk; cycle; decomposition; graph

Instituce: Fakulty UK (VŠKP) (web)
Informace o dostupnosti dokumentu: Dostupné v digitálním repozitáři UK.
Původní záznam: http://hdl.handle.net/20.500.11956/128181

Trvalý odkaz NUŠL: http://www.nusl.cz/ntk/nusl-448920


Záznam je zařazen do těchto sbírek:
Školství > Veřejné vysoké školy > Univerzita Karlova > Fakulty UK (VŠKP)
Vysokoškolské kvalifikační práce > Diplomové práce