|
|
Groups of automorphisms of graphs
Zeman, Peter ; Nedela, Roman (vedoucí práce) ; Felsner, Stefan (oponent) ; Širáň, Jozef (oponent)
Groups of automorphisms of graphs - abstrakt V tejto práci skúmame grupy automorfizmov špecifických tried grafov z štrukturál- neho a výpočetného hladiska. Pre intervalové, permutačné, tetivové a rovinné grafy sme odvodili induktívnu charakterizáciu grúp automorfizmov pomocou grupových súčinov. Pre chordálne grafy s ohraničenou listnatosťou sme dokázali, že problémy výpočtu grupy automorfizmov a testovania izomorfizmu sú fixed parameter tractable. Pre mapy na plochách sme popísali lineárny algoritmus, ktorý počíta grupu automorfizmov mapy na ploche s pevným rodom. 1
|
|
|
Extension Properties of Graphs and Structures
Klavík, Pavel ; Nešetřil, Jaroslav (vedoucí práce) ; Širáň, Jozef (oponent) ; Hell, Pavol (oponent)
Rozšiřovací vlastnosti grafů a struktur Pavel Klavík Hlavní motivace pro studium kreslení grafů a geometrických reprezentací je najít způ- soby, jak vizualizovat grafy efektivně, aby jejich struktura byla tak srozumitelná, jak je to jenom možné. V této práci se zaměřujeme na strukturální vlastnosti, které vyplývají z toho, že grafy mají určitý druh geometrických reprezentací. Studujeme dva druhy geo- metrických reprezentací: Průnikové reprezentace, ve kterých jsou vrcholy reprezentovány geometrickými množinami, zatímco hrany jsou kódovány jejich průniky, a rovinná vnoření rovinných grafů, což jsou kreslení grafů do roviny bez křížení hran. Z existence geomet- rické reprezentace lze vyvodit dodatečné informace o grafu. Hlavní myšlenka této práce je se ptát, jaká další informace se dá vyvodit ze struktury všech možných geometrických reprezentací. V části I studujeme problém rozšiřování částečných reprezentací pro průnikové reprezen- tace. Vedle grafu obsahuje vstup také částečnou reprezentaci, která předepisuje reprezentaci indukovaného podgrafu. Ptáme se, zdali je možné tuto částečnou reprezentaci rozšířit na plnou reprezentaci vstupního grafu, aniž bychom pozměnili předepsané množiny. Tento pro- blém jsem uvedl v roce 2010 ve své bakalářské práci. Popisujeme přehled známých výsledků pro řadu grafových tříd....
|
host ::
RSS.