| Název: | Zobecněné hamiltonovské kružnice |
| Další názvy: | Generalized Hamiltonian cycles |
| Autoři: | Kabela, Adam |
| Vedoucí práce/školitel: | Teska, Jakub |
| Oponent: | Holub, Přemysl |
| Datum vydání: | 2012 |
| Nakladatel: | Západočeská univerzita v Plzni |
| Typ dokumentu: | diplomová práce |
| URI: | http://hdl.handle.net/11025/3683 |
| Klíčová slova: | hamiltonovská kružnice;r-trestle;tuhost;chordální grafy;rovinné grafy;shortness exponent;zakázané podgrafy |
| Klíčová slova v dalším jazyce: | hamiltonian cycle;r-trestle;toughness;chordal graphs;planar graphs;shortness exponent;forbidden subgraphs |
| Abstrakt: | 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. |
| Abstrakt v dalším jazyce: | 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. |
| Práva: | Plný text práce je přístupný bez omezení. |
| Vyskytuje se v kolekcích: | Diplomové práce / Theses (KMA) |
Soubory připojené k záznamu:
| Soubor | Popis | Velikost | Formát | |
|---|---|---|---|---|
| DP_Adam_Kabela.pdf | Plný text práce | 619,28 kB | Adobe PDF | Zobrazit/otevřít |
| PV-Kabela.pdf | Posudek vedoucího práce | 133,67 kB | Adobe PDF | Zobrazit/otevřít |
| PO-Kabela.pdf | Posudek oponenta práce | 255,03 kB | Adobe PDF | Zobrazit/otevřít |
| P-Kabela.pdf | Průběh obhajoby práce | 36,32 kB | Adobe PDF | Zobrazit/otevřít |
Použijte tento identifikátor k citaci nebo jako odkaz na tento záznam:
http://hdl.handle.net/11025/3683Všechny záznamy v DSpace jsou chráněny autorskými právy, všechna práva vyhrazena.