Název:
Řešení optimalizačních problémů prohledáváním na vybraných třídách grafů
Překlad názvu:
Optimisation using graph searching on special graph classes
Autoři:
Chejnovská, Anna ; Gavenčiak, Tomáš (vedoucí práce) ; Šámal, Robert (oponent) Typ dokumentu: Bakalářské práce
Rok:
2015
Jazyk:
eng
Abstrakt: [eng][cze] For a given graph we define the minimum path cover as a minimum cardinality set of vertex disjoint paths covering all the vertices of the graph. This problem is one of the usual generalization of the Hamiltonian path problem. In this thesis we based our work on a paper Corneil et al. (2013) presenting a certifying algorithm for the minimal path cover problem on cocomparability graphs (the complement of graph of strict partial order). We first introduce this algorithm an then we experimentally examine its robustness to five operations on edges and vertices of the graph. We also analyse the impact of these operation on the size of the minimal path cover theoretically. Powered by TCPDF (www.tcpdf.org)Pro graf definujeme minimální pokrytí cestami jako nejmenší množinu vrcholově disjunktních cest, které pokrývají všechny vrcholy grafu. Tento problém je jedním z běžných zobecnění známého problému hledání Hamiltonovské cesty v grafu. V této práci vyjdeme ze článku Corneil et al. (2013), kde byl představen certifikující algoritmus pro hledání minimálního pokrytí cestami na cocomparability grafech (doplněk grafu relace neostrého částečného uspořádání). Tento algoritmus nejprve představíme, poté experimentálně prozkoumáme jeho robustnost vůči pěti operacím na hranách a vrcholech. Dopad těchto operací na velikost minimálního pokrytí cest rozebereme také teoreticky. Powered by TCPDF (www.tcpdf.org)
Klíčová slova:
aproximace; grafové třídy; optimalizace; prohledávání grafů; teorie grafů; approximation; graph classes; graph searching; graph theory; optimisation