Grupová souvislost grafů

• Thesis title in Czech: Grupová souvislost grafů
• Thesis title in English: Group connectivity of graphs
• Key words: grupová souvislost
• English key words: group connectivity
• Academic year of topic announcement: 2013/2014
• Thesis type: diploma thesis
• Thesis language: čeština
• Department: Computer Science Institute of Charles University (32-IUUK)
• Supervisor: doc. Mgr. Robert Šámal, Ph.D.
• Author: hidden - assigned and confirmed by the Study Dept.
• Date of registration: 13.03.2014
• Date of assignment: 13.03.2014
• Confirmed by Study dept. on: 21.03.2014
• Date and time of defence: 09.09.2014 10:00
• Date of electronic submission: 19.07.2014
• Date of submission of printed version: 21.07.2014
• Date of proceeded defence: 09.09.2014
• Opponents: RNDr. Ondřej Pangrác, Ph.D.

Guidelines

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.

References

[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.