Název: Generování grafů
Překlad názvu: Generating graphs
Autoři: Mohelníková, Lucie ; Dvořák, Zdeněk (vedoucí práce) ; Jelínek, Vít (oponent)
Typ dokumentu: Bakalářské práce
Rok: 2012
Jazyk: cze
Abstrakt: [cze] [eng]
Název práce: Generování grafů Autor: Lucie Mohelníková Katedra: Katedra aplikované matematiky Vedoucí bakalářské práce: Mgr. Zdeněk Dvořák,Ph.D., Informatický ústav Univerzity Karlovy Abstrakt: Zabýváme se generováním grafů z vybraných tříd, zejména pak grafů nakreslených na plochách. Zaměřujeme se na metodu generování za pomoci dekontrakcí vrcholů, pro níž je zásádní identifikace počátečních (ireducibilních) grafů. Uvádíme přehled výsledků o ireducibilních triangulacích a kvadrangulacích různých ploch, zejména pak nízkého rodu (rovina, projektivní rovina, Kleinova láhev). Hlavním přínosem této práce je identifikace 21 ireducibilních triangulací toru, čímž dokazujeme výsledek Lawrencenka bez použití výpočetní techniky. Klíčová slova: ireducibilní, triangulace, torus Title: Generating graphs Author: Lucie Mohelníková Department: Department of Applied Mathematics Supervisor: Mgr. Zdeněk Dvořák, Ph.D., Computer Science Institute of Char- les University Abstract: The main topic of this thesis are the methods used to generate graphs from prescribed classes, especially graphs embeddable in surfaces. An im- portant technique in this context is to generate the graphs by vertex decontracti- ons. The identification of initial (irreducible) graphs is crucial for this technique. We give an overview of the results regarding the irreducible triangulations and quadrangulations of various surfaces, especially the surfaces of low genus (sphere, projective plane, Klein bottle). The main result of this work is the identification 21 irreducible triangulations which proves the result of Lawrencenko without using of information technology. Keywords: irreducible, triangulations, torus
Klíčová slova: generování; grafy; generation; graph

Instituce: Fakulty UK (VŠKP) (web)
Informace o dostupnosti dokumentu: Dostupné v digitálním repozitáři UK.
Původní záznam: http://hdl.handle.net/20.500.11956/45582

Trvalý odkaz NUŠL: http://www.nusl.cz/ntk/nusl-484271


Záznam je zařazen do těchto sbírek:
Školství > Veřejné vysoké školy > Univerzita Karlova > Fakulty UK (VŠKP)
Vysokoškolské kvalifikační práce > Bakalářské práce