Barvení grafu a formální gramatiky

• Název práce v češtině: Barvení grafu a formální gramatiky
• Název v anglickém jazyce: Graph coloring and formal grammars
• Klíčová slova: věta o čtyřech barvách|vektorový součin|binární strom
• Klíčová slova anglicky: four color theorem|vector cross product|binary tree
• Akademický rok vypsání: 2021/2022
• Typ práce: bakalářská práce
• Jazyk práce: čeština
• Ústav: Katedra algebry (32-KA)
• Vedoucí / školitel: doc. Mgr. Štěpán Holub, Ph.D.
• Řešitel: skrytý - zadáno a potvrzeno stud. odd.
• Datum přihlášení: 10.09.2021
• Datum zadání: 04.10.2021
• Datum potvrzení stud. oddělením: 25.10.2021
• Datum a čas obhajoby: 12.09.2022 09:00
• Datum odevzdání elektronické podoby: 15.07.2022
• Datum odevzdání tištěné podoby: 25.07.2022
• Datum proběhlé obhajoby: 12.09.2022
• Oponenti: doc. Mgr. Libor Barto, Ph.D.

Zásady pro vypracování

Student se seznámí s redukcí problému čtyř barev na otázku dvojzančnosti jisté formální gramatiky a srozumitelně ji představí.

Seznam odborné literatury

Bobbe Cooper, Eric Rowland, Doron Zeilberger, Toward a language theoretic proof of the four color theorem,
Advances in Applied Mathematics, Volume 48, Issue 2, 2012, Pages 414-431, ISSN 0196-8858, https://doi.org/10.1016/j.aam.2011.11.002.
Louis Kauffman, Map coloring and the vector cross product, Journal of Combinatorial Theory, Series B 48 (1990) 145-154.

Předběžná náplň práce

Slavný problém ukázat, že každý rovinný graf je obarvitelný čtyřmi barvami, byl zatím dokázán jen pomocí rozsáhlé analýzy případů. Existuje naděje, že ekvivalentní popis pomocí stromů jednoduché formální gramatik by mohl důkaz zjednodušit. Půjde o představení těchto snah.