Název: Barvení grafu a formální gramatiky
Překlad názvu: Graph coloring and formal grammars
Autoři: Elichová, Sára ; Holub, Štěpán (vedoucí práce) ; Barto, Libor (oponent)
Typ dokumentu: Bakalářské práce
Rok: 2022
Jazyk: cze
Abstrakt: [cze] [eng]
Tato práce se zabývá dvěma ekvivalentními reformulacemi problému čtyř barev. První z nich ukazuje spojitost barvení grafů s vektorovým součinem, druhá na ni navazuje a rozvíjí souvislost s formální gramatikou. Tyto reformulace a důkazy jejich ekvivalence s větou o čtyřech barvách jsou výsledky dvou prací, jejichž motivací je snaha o jednodušší důkaz slavného problému, který byl zatím dokázán jen za pomoci počítače. Přinášejí zajímavý úhel pohledu na problém barvení grafů a nabízejí možnost, jak jej uchopit novým způsobem, který by se mohl ukázat přístupnějším. Tato práce představí důkazy uvedené ve výchozí literatuře a doplní kroky, které tam nejsou podrobně zpracovány. Některé myšlenky se pokusí více formalizovat a přispět tak k lepší srozumitelnosti důkazů. 1 This thesis deals with two equivalent reformulations of the four color problem. The first of them shows the connection between graph coloring and the vector cross product; the se- cond one expands on it and develops a relation to a formal grammar. These reformulations together with the proofs of their equivalence to the four color theorem are the results of two articles motivated by the effort to find a simpler proof of the famous problem, which was proved only by computer. They bring an interesting perspective on the problem of graph coloring and give the possibility to look on it in a new way, which could turn out to be more approachable. This thesis presents the proofs introduced in the source li- terature and adds the steps that are not elaborated in detail by the authors. It aims to formalize some of the ideas and to contribute to the comprehensibility of the proofs. 1
Klíčová slova: věta o čtyřech barvách|vektorový součin|binární strom; four color theorem|vector cross product|binary tree

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

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


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