Diplomová práce

Průsečíková čísla grafů

Graph crossing numbers

Bc. Marek Derňár
Anotace

V tejto diplomovej práci sa zaoberáme parametrom grafu, ktorý sa nazýva priesečníkové číslo grafu a vyjadruje najmenší počet priesečníkov dvojíc hrán pri nakreslení grafu v rovine. V tejto práci zhrnieme najdôležitejšie doteraz známe výsledky o tomto parametri a budeme sa podrobnejšie zaoberať jeho správaním sa pri odoberaní hrán z grafu.

Abstract

In this master thesis we study graph parameter called graph crossing number, which represents the smallest number of pairwise crossings of edges among all drawings in plane. In this thesis we resume the most important facts about this parameter and we are interested in its behaviour after deleting edges.

Klíčová slova
graf nakreslenie grafu priesečníkové číslo priesečnikovo-kritické grafy mininálne priesečníkovo-kritické grafy graph drawing of graph crossing number crossing-critical graphs minimal crossing-critical graphs
Zadání práce
Průsečíkové číslo grafu G udává minimální možný počet průsečíků dvojic hran při nakreslení G do roviny. Jedná se o výpočetně velmi obtížný parametr (NP-úplný), avšak mající zajímavé aplikace. Blíže viz http://en.wikipedia.org/wiki/Crossing_number_(graph_theory).
Diplomant bude studovat třídy grafů majících omezenou hodnotu průsečíkového čísla, jejich strukturální vlastnosti a případně tzv kritické grafy těchto tříd. Vedle toho se dotkne i souvisejících algoritmických otázek v teoretické rovině.
Administrativní informace
Práce zkontrolována:
13. 5. 2012 17:16, prof. RNDr. Petr Hliněný, Ph.D., učo 168881
Plný text práce
658,7 KB / soubor PDF
Jazyk práce
slovenština slovenština
Termín obhajoby
12. 6. 2012
Práce byla úspěšně obhájena

Vedoucí

prof. RNDr. Petr Hliněný, Ph.D., učo 168881
KTP FI MU

Oponent

doc. Mgr. Michal Kunc, Ph.D., učo 2906
ÚMS Ústavy PřF MU

Literatura

  • MOHAR, Bojan a Carsten THOMASSEN. Graphs on surfaces. Baltimore: The Johns Hopkins University Press, 2001, xi, 291. ISBN 0801866898.
  • BEINEKE, Lowell a Robin WILSON. Topics in Topological Graph Theory. Cambridge University Press, 2009. ISBN 978-0-521-80230-7.
Citovat tuto práci
Masarykova univerzita Přírodovědecká fakulta
Studijní program
Matematika
Obor

Práce na příbuzné téma

Seznam prací, které mají shodná klíčová slova.

Podobné práce
 
Název
Vložil
Vloženo
Práva
Archiv závěrečné práce Marek Derňár PřF N-MA MINF alvdw/6
Derňár, M.
5. 5. 2012
Složky
Soubory
Anotace anglicky annotation_english.txt
Derňár, M.
5. 5. 2012
Anotace česky annotation.txt
Derňár, M.
5. 5. 2012
Klíčová slova keywords.txt
Derňár, M.
5. 5. 2012
Plný text práce diplomkaDernar.pdf
Derňár, M.
10. 5. 2012
Posudek oponenta posudek_oponenta_Dernar.pdf
Kunc, M.
3. 6. 2012

  • Přidání souboru

    Soubor nebo složku lze nahrát pomocí tlačítka Přidat.

  • Další operace se soubory

    Podrobnosti lze zjistit označením příslušného řádku.

  • Pohled pro experty

    Pro častou práci je možné zvolit režim Více možností.

  • Vyhledávání souborů

    Vyhledávaný výraz můžete zadat přímo do adresního řádku.

  • Rychlý přístup k souborům

    Pomocí funkce Nedávné je možné se rychle vrátit k právě prohlíženým souborům. Oblíbené soubory je také možné označit Hvězdičkou.