Grupová souvislost grafů

• Název práce v češtině: Grupová souvislost grafů
• Název v anglickém jazyce: Group connectivity of graphs
• Klíčová slova: grupová souvislost
• Klíčová slova anglicky: group connectivity
• Akademický rok vypsání: 2013/2014
• Typ práce: diplomová práce
• Jazyk práce: čeština
• Ústav: Informatický ústav Univerzity Karlovy (32-IUUK)
• Vedoucí / školitel: doc. Mgr. Robert Šámal, Ph.D.
• Řešitel: skrytý - zadáno a potvrzeno stud. odd.
• Datum přihlášení: 13.03.2014
• Datum zadání: 13.03.2014
• Datum potvrzení stud. oddělením: 21.03.2014
• Datum a čas obhajoby: 09.09.2014 10:00
• Datum odevzdání elektronické podoby: 19.07.2014
• Datum odevzdání tištěné podoby: 21.07.2014
• Datum proběhlé obhajoby: 09.09.2014
• Oponenti: RNDr. Ondřej Pangrác, Ph.D.

Zásady pro vypracování

Pojem grupové souvislosti (zavedeno v [1]) zobecňuje jak běžnou souvislost, tak (zejména) pojem nenulového toku v grafech. Několik ekvivalentních definic dává tomuto pojmu eleganci, jeho užitečnost tkví v možnosti jej použít na induktivní tvorbu nenulových toků. Navzdory tomu není stále tento pojem do hloubky prozkoumán.

Řešitel(ka) implementuje test, zda daný graf je souvislý vzhledem k dané grupě. Implementace musí být dostatečně efektivní, aby umožnila experimentální ověřování různých hypotéz, se zaměřením na problém ([2]), zda Z_4-souvislost je ekvivalentní Z_2^2-souvislosti. V závislosti na výsledcích experimentů bude součástí práce i teoretické vysvětlení zjištěných vlastností grupové souvislosti.

Seznam odborné literatury

[1] François Jaeger, Nathan Linial, Charles Payan, Michael Tarsi: Group Connectivity of Graphs--A Nonhomogeneous Analogue of Nowhere-Zero Flow Properties. Journal of
Combinatorial Theory, Series B 56, no. 2 (1992), 165–182.

[2] Nathan Linial: personal communication

[3] Cun-Quan Zhang: Integer flows and cycle covers of graphs. Monographs and Textbooks in Pure and Applied Mathematics, 205. Marcel Dekker, Inc., New York, 1997.