|
|
Generating graphs
Mohelníková, Lucie ; Dvořák, Zdeněk (advisor) ; Jelínek, Vít (referee)
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
|
|
|
Group connectivity of graphs
Mohelníková, Lucie ; Šámal, Robert (advisor) ; Pangrác, Ondřej (referee)
Název práce: Grupová souvislost graf· Autor: Lucie Mohelníková Katedra: Informatický ústav Univerzity Karlovy Vedoucí diplomové práce: Mgr. Robert 'ámal,Ph.D., Informatický ústav Univerzi- ty Karlovy Abstrakt: Zabývali jsme se grupovou souvislostí graf·, zejména pak Z2 2- a Z4- souvislostí. Implementovali jsme v jazyce C++ test, zda je graf grupově souvislý a pomocí něho hledáme grafy, které jsou grupově souvislé v jedné ze zkoumaných grup a v druhé nikoliv. Zkoumali jsme grafy, které vzniknou podrozdělením hran několika speciálních graf· např. K4 a krychle. Hlavním přínosem této práce je nalezení dvou graf·, které jsou Z4-souvislé a nejsou Z2 2-souvislé. Pomocí druhé nezávislé implementace testu na grupovou souvislost napsané v jazyce Prolog s využitím CSP jsme ověřili, že tyto grafy jsou Z4-souvislé. Analyticky jsme dokázali, že jeden z nalezených graf· není Z2 2-souvislý. Klíčová slova: grupová souvislost, toky, grupa
|
|
|
Group connectivity of graphs
Mohelníková, Lucie ; Šámal, Robert (advisor) ; Pangrác, Ondřej (referee)
Název práce: Grupová souvislost graf· Autor: Lucie Mohelníková Katedra: Informatický ústav Univerzity Karlovy Vedoucí diplomové práce: Mgr. Robert 'ámal,Ph.D., Informatický ústav Univerzi- ty Karlovy Abstrakt: Zabývali jsme se grupovou souvislostí graf·, zejména pak Z2 2- a Z4- souvislostí. Implementovali jsme v jazyce C++ test, zda je graf grupově souvislý a pomocí něho hledáme grafy, které jsou grupově souvislé v jedné ze zkoumaných grup a v druhé nikoliv. Zkoumali jsme grafy, které vzniknou podrozdělením hran několika speciálních graf· např. K4 a krychle. Hlavním přínosem této práce je nalezení dvou graf·, které jsou Z4-souvislé a nejsou Z2 2-souvislé. Pomocí druhé nezávislé implementace testu na grupovou souvislost napsané v jazyce Prolog s využitím CSP jsme ověřili, že tyto grafy jsou Z4-souvislé. Analyticky jsme dokázali, že jeden z nalezených graf· není Z2 2-souvislý. Klíčová slova: grupová souvislost, toky, grupa
|
|
|
Generating graphs
Mohelníková, Lucie ; Dvořák, Zdeněk (advisor) ; Jelínek, Vít (referee)
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
|
guest ::
