CSP pocházející z kombinatorické topologie
| Thesis title in Czech: | CSP pocházející z kombinatorické topologie |
|---|---|
| Thesis title in English: | CSP coming from combinatorial topology |
| Key words: | Násobně propletený graf|CSP|algoritmy |
| English key words: | Multiply linked graph|CSP|algorithms |
| Academic year of topic announcement: | 2024/2025 |
| Thesis type: | Bachelor's thesis |
| Thesis language: | |
| Department: | Department of Applied Mathematics (32-KAM) |
| Supervisor: | prof. RNDr. Martin Tancer, Ph.D. |
| Author: | Patrik Zavoral - assigned and confirmed by the Study Dept. |
| Date of registration: | 21.03.2025 |
| Date of assignment: | 27.03.2025 |
| Confirmed by Study dept. on: | 27.03.2025 |
| Date of electronic submission: | 16.07.2025 |
| Guidelines |
| Graf je k-násobně propletený, pokud každé jeho vnoření do R^3 obsahuje k-tici cyklů z nichž každé dva jsou propletené (v topologickém smyslu). Existence násobně propletených grafů je známá, ale známé konstrukce vedou k obrovským grafům. Například není známo, jestli úplný graf K_9 je trojnásobně propletený. Tuto úlohu lze přirozeně formulovat jako tzv. "Constraint satisfaction problem" (CSP). Pro graf K_9 například dostáváme CSP se 189 proměnnými, které mohou nabývat hodnot 0 nebo 1 a dále 280 omezeními v nichž se vyskytují 27-ární relace. Toto CSP je už příliš velké, aby šlo naivně projít všechny možnosti. Na druhou stranu toto CSP vykazuje vysokou míru symetrie (je na něm jistá struktura vektorového prostoru a také symetrie pocházející ze symetrií K_9), která by měla pomoci k jeho řešení. To lze případně kombinovat s jinými technikami na řešení CSP.
Cílem práce je řešit výše zmíněné CSP, popř. další pocházející z jiných nastavení parametrů. Ideální by bylo navrhnout vhodný algoritmus (který doběhne) pro vyřešení CSP pro K_9. Dá se předpokládat, že algoritmus bude adaptivní ve smyslu, že bude uzpůsobovat svůj běh na základě získaných mezivýsledků. Vzhledem k tomu, že ale nejsou záruky, že takový algoritmus se podaří navrhnout, práci lze považovat za úspěšnou při dosažení jiných cílů. Těmi mohou například být vyřešení CSP pro jiné malé husté grafy (například K_9 bez hrany); navržení a provedení vhodných náhodných experimentů pro dolní odhady; teoretické vylepšení odhadů (když už je příslušné CSP příliš velké, tak řešení nemá). Práce bude vypracována anglicky. |
| References |
| Brailsford, S.C., Potts, C.N. and Smith, B.M., 1999. Constraint satisfaction problems: Algorithms and applications. European journal of operational research, 119(3), pp.557-581.
Conway, J.H. and McA. Gordon, C., 1983. Knots and links in spatial graphs. Journal of Graph Theory, 7(4), pp.445-453. Flapan, E., Mellor, B., and Naimi, R. 2008, Intrinsic linking and knotting are arbitrarily complex, Fund. Math. 201(2), 131--148 Winter, M., 2024. Do triple-linked graphs exist? MathOverflow question, https://mathoverflow.net/questions/465865/do-triple-linked-graphs-exist |