Title: | Zobecněné hamiltonovské kružnice |
Other Titles: | Generalized Hamiltonian cycles |
Authors: | Kabela, Adam |
Advisor: | Teska, Jakub |
Referee: | Holub, Přemysl |
Issue Date: | 2012 |
Publisher: | Západočeská univerzita v Plzni |
Document type: | diplomová práce |
URI: | http://hdl.handle.net/11025/3683 |
Keywords: | hamiltonovská kružnice;r-trestle;tuhost;chordální grafy;rovinné grafy;shortness exponent;zakázané podgrafy |
Keywords in different language: | hamiltonian cycle;r-trestle;toughness;chordal graphs;planar graphs;shortness exponent;forbidden subgraphs |
Abstract: | V této práci ukážeme různé souvislosti mezi hamiltonovskými kružnicemi, r-trestly a tuhostí grafu. Budeme sledovat, jak se tyto souvislosti mění, pokud namísto obecných grafů uvažujeme chordální grafy nebo rovinné grafy. Zmíníme další možná zobecnění hamiltonovských kružnic a jejich vzájemné vztahy, a v neposlední řadě také souvislost hamiltonovských kružnic a r-trestlů se zakázanými podgrafy. Práce obsahuje nové výsledky související s touto problematikou. Konkrétně jsou to chordální grafy a chordální rovinné grafy s relativně velkou tuhostí, které nemají r-trestle. Tyto grafy vylepšují horní odhad pro shortness exponent třídy 1-tuhých chordálních rovinných grafů. Ukážeme také dvojici zakázaných podgrafů, která zajistí, že daný graf má r-trestle. |
Abstract in different language: | This thesis shows the relations among the hamiltonian cycle, the r-trestle and the toughness of a graph and how the relations change considering general graphs, chordal graphs and planar graphs. Some other relations dealing with generalizing hamiltonicity, the toughness of a graph and also the hamiltonicity and forbidden subgraphs are mentioned. As the original results we present chordal graphs and chordal planar graphs with high toughness and no r-trestle. These graphs improves the upper bound on the shortness exponent of the class of 1-tough chordal planar graphs. We also present a sufficient condition on forbidden subgraphs for a graph to have an r-trestle. |
Rights: | Plný text práce je přístupný bez omezení. |
Appears in Collections: | Diplomové práce / Theses (KMA) |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
DP_Adam_Kabela.pdf | Plný text práce | 619,28 kB | Adobe PDF | View/Open |
PV-Kabela.pdf | Posudek vedoucího práce | 133,67 kB | Adobe PDF | View/Open |
PO-Kabela.pdf | Posudek oponenta práce | 255,03 kB | Adobe PDF | View/Open |
P-Kabela.pdf | Průběh obhajoby práce | 36,32 kB | Adobe PDF | View/Open |
Please use this identifier to cite or link to this item:
http://hdl.handle.net/11025/3683
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.