Název: Generování jednoduchých nakreslení grafů
Překlad názvu: Generating simple drawings of graphs
Autoři: Čermák, Filip ; Balko, Martin (vedoucí práce) ; Valtr, Pavel (oponent)
Typ dokumentu: Bakalářské práce
Rok: 2021
Jazyk: eng
Abstrakt: [eng] [cze]
In this thesis, we study the crossing numbers of complete graphs. After introducing a long history of the old problem of determining the crossing number of Kn, we survey the recent progress on the Harary-Hill conjecture by compiling proofs of this conjecture for special classes of drawings of Kn. We also create a program for generating a database of all simple drawings of Kn with n ≤ 8. We implement another program that visualizes these drawings and allows the user to create its own simple drawings of general graphs. The visualizer also captures the structure of crossings of the displayed drawings. We use our programs to verify a conjecture by Balko, Fulek, and Kynčl for small cases and we find a mistake in a paper by Mutzel and Oettershagen. 1 V této práci se zabýváme průsečíkovými čísly úplných grafů. Nejprve uvedeme dlouhou historii velmi starého problému týkajícího se určení průsečíkového čísla Kn a poté ukážeme současný pokrok v Hararyho-Hillově domněnce postupným procházením jejích důkazů pro speciální třídy nakreslení Kn. Vytvoříme program pro generování databáze všech jednoduchých nakreslení Kn, kde n ≤ 8. Rovněž implementujeme program vizualizující tato nakreslení a umožňující uživateli vytvořit vlastní jednoduchá nakreslení obecných grafů. Vizualizér navíc zachycuje strukturu průsečíků zobrazených nakreslení. Naše pro- gramy využijeme k ověření domněnky Balka, Fulka a Kynčla pro malé případy a odhalíme chybu v článku autorů Mutzela a Oettershagena. 1
Klíčová slova: průsečíkové číslo|úplný graf|k-hrany|kumulované k-hrany|Hararyho--Hillova domněnka; crossing number|complete graph|k-edges|cumulated k-edges|the Harary--Hill conjecture

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/127958

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


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