|
|
Algebraic, Structural, and Complexity Aspects of Geometric Representations of Graphs
Zeman, Peter ; Klavík, Pavel (vedoucí práce) ; Nešetřil, Jaroslav (oponent)
Title: Algebraic, Structural and Complexity Aspects of Geometric Representations of Graphs Author: Peter Zeman Department: Computer Science Institute Supervisor: RNDr. Pavel Klavík Supervisor's e-mail: klavik@iuuk.mff.cuni.cz Keywords: automorphism groups, interval graphs, circle graphs, comparability graphs, H-graphs, recognition, dominating set, graph isomorphism, maximum clique, coloring Abstract: We study symmetries of geometrically represented graphs. We describe a tech- nique to determine the automorphism group of a geometrically represented graph, by understanding the structure of the induced action on all geometric representations. We prove that interval graphs have the same automorphism groups as trees, and for a given interval graph, we construct a tree with the same automorphism group which answers a question of Hanlon [Trans. Amer. Math. Soc 272(2), 1982]. For permutation and circle graphs, we give an inductive characterization by semidirect and wreath prod- ucts. We also prove that every abstract group can be realized by the automorphism group of a comparability graph/poset of the dimension at most four. We also study H-graphs, introduced by Biró, Hujter, and Tuza in 1992. Those are intersection graphs of connected subgraphs of a subdivision of a graph H. This thesis is the first comprehensive...
|
|
|
Automorphism Groups of Geometrically Represented Graphs
Zeman, Peter ; Klavík, Pavel (vedoucí práce) ; Nedela, Roman (oponent)
V tejto práci skúmame grupy automorfizmov grafov s vel'mi silnou štruktúrou. Pravdepodobne jeden z prvých výsledkov v tomto smere je Jordanova charakterizácia triedy grúp automorfizmov stromov T z roku 1869. Prekvapivo, grupy automorfizmov prienikových grafov boli študované iba vel'mi málo. Aj pre vel'mi pochopené triedy prienikových grafov, je štruktúra ich grúp auto- morfizmov neznáma. Hlavná otázka, ktorou sa zaoberáme je, či sa z dobrej znalosti reprezentácií prienikového grafu geometrických objektov dá zrekonštruovat' jeho grupa automorfizmov. V práci skúmame hlavne intervalové grafy. Intervalové grafy sú prienikové grafy intervalov na reálnej osi. Sú jednou z naj- starších a najviac študovaných tried prienikových grafov. Náš hlavný výsledok ho- vorí, že trieda grúp automorfizmov intervalových grafov I je rovnaká ako trieda grúp automorfizmov stromov T . Navyše ukazujeme postup ako pre daný intervalový graf skonštruovat' strom s rovnakou grupou automorfizmov a tak isto obrátene, pre daný strom skonštruujeme intervalový graf. 1
|
|
|
Algebraic, Structural, and Complexity Aspects of Geometric Representations of Graphs
Zeman, Peter ; Klavík, Pavel (vedoucí práce) ; Nešetřil, Jaroslav (oponent)
Title: Algebraic, Structural and Complexity Aspects of Geometric Representations of Graphs Author: Peter Zeman Department: Computer Science Institute Supervisor: RNDr. Pavel Klavík Supervisor's e-mail: klavik@iuuk.mff.cuni.cz Keywords: automorphism groups, interval graphs, circle graphs, comparability graphs, H-graphs, recognition, dominating set, graph isomorphism, maximum clique, coloring Abstract: We study symmetries of geometrically represented graphs. We describe a tech- nique to determine the automorphism group of a geometrically represented graph, by understanding the structure of the induced action on all geometric representations. We prove that interval graphs have the same automorphism groups as trees, and for a given interval graph, we construct a tree with the same automorphism group which answers a question of Hanlon [Trans. Amer. Math. Soc 272(2), 1982]. For permutation and circle graphs, we give an inductive characterization by semidirect and wreath prod- ucts. We also prove that every abstract group can be realized by the automorphism group of a comparability graph/poset of the dimension at most four. We also study H-graphs, introduced by Biró, Hujter, and Tuza in 1992. Those are intersection graphs of connected subgraphs of a subdivision of a graph H. This thesis is the first comprehensive...
|
|
|
Automorphism Groups of Geometrically Represented Graphs
Zeman, Peter ; Klavík, Pavel (vedoucí práce) ; Nedela, Roman (oponent)
V tejto práci skúmame grupy automorfizmov grafov s vel'mi silnou štruktúrou. Pravdepodobne jeden z prvých výsledkov v tomto smere je Jordanova charakterizácia triedy grúp automorfizmov stromov T z roku 1869. Prekvapivo, grupy automorfizmov prienikových grafov boli študované iba vel'mi málo. Aj pre vel'mi pochopené triedy prienikových grafov, je štruktúra ich grúp auto- morfizmov neznáma. Hlavná otázka, ktorou sa zaoberáme je, či sa z dobrej znalosti reprezentácií prienikového grafu geometrických objektov dá zrekonštruovat' jeho grupa automorfizmov. V práci skúmame hlavne intervalové grafy. Intervalové grafy sú prienikové grafy intervalov na reálnej osi. Sú jednou z naj- starších a najviac študovaných tried prienikových grafov. Náš hlavný výsledok ho- vorí, že trieda grúp automorfizmov intervalových grafov I je rovnaká ako trieda grúp automorfizmov stromov T . Navyše ukazujeme postup ako pre daný intervalový graf skonštruovat' strom s rovnakou grupou automorfizmov a tak isto obrátene, pre daný strom skonštruujeme intervalový graf. 1
|
|
|
Évariste Galois a jeho teorie
Richter, Lukáš ; Kvasz, Ladislav (vedoucí práce) ; Jančařík, Antonín (oponent)
NÁZEV: Évariste Galois a jeho teorie AUTOR: Lukáš Richter KATEDRA: Katedra matematiky a didaktiky matematiky VEDOUCÍ PRÁCE: prof. RNDr. Ladislav Kvasz, Dr. ABSTRAKT: První část bakalářské práce pojednává o životě významného francouzského matematika 19. století Évarista Galoise, zakladatele moderní algebry. Zaměřuje se na léta jeho školních docházky, setkání s matematikou, neúspěšné přijímací zkoušky, vyloučení ze školy, jeho matematická díla a neblahé zkušenosti s francouzskou Akademií věd. V průběhu života měl dvakrát problémy se zákonem, byl souzen a jednou uvězněn. Na sklonku svého krátkého života se nešťastně zamiloval a v souvislosti s tím zemřel v souboji. Druhá část se zabývá řešením polynomických rovnic prvního až čtvrtého stupně pomocí vzorců, které byly známy již za Galoisova života. Každý z uvedených vzorců je srozumitelně odvozen metodou vhodnou i pro středoškoláky a jeho použití předvedeno na příkladu. Ve třetí části jsou uvedeny základy Galoisovy teorie a je ukázána neřešitelnost polynomických rovnic stupně nejméně 5. Některé poučky jsou představeny na příkladech. KLÍČOVÁ SLOVA: Évariste Galois, polynomické rovnice, rozšiřování číselných těles, grupy automorfismů, Galoisova teorie
|
host ::
RSS.