Student prostuduje doporučenou literaturu s cílem rozhodnout, zda Thomasonův algoritmus pro nalezení druhé Hamiltonovské kružnice v kubickém grafu potřebuje exponenciálně mnoho kroků při spuštění na libovolnou hranu Krawczykova grafu. Vodítkem může být počítačový experiment.
Seznam odborné literatury
Kathie Cameron: Thomason's algorithm for finding a second hamiltonian circuit through a given edge in a cubic graph is exponential on Krawczyk's graphs. Discrete Mathematics 235(1-3): 69-77 (2001)
Adam Krawczyk: The complexity of finding a second Hamiltonian cycle in cubic graphs. J. Comput. Syst. Sci. 58 (3): 641-647 (1999)
Andrew Thomason: Hamiltonian cycles and uniquely edge colourable graphs. Ann. Discrete Math. 3: 259-268 (1978)
Předběžná náplň práce
Andrew Thomason navrhl elegantní algoritmus pro nalezení druhé Hamiltonovské kružnice v kubickém grafu, čímž podal alternativní důkaz Smithovy věty. Později Adam Krawczyk zkonstruoval příklad grafu, ve kterém Thomasonův algoritmus potřebuje exponenciálně mnoho kroků při spuštění na určitou hranu. Bylo by zajímavé vědět, zda tento algoritmus potřebuje exponenciálně mnoho kroků při spuštění na libovolnou hranu Krawczykova grafu.
Předběžná náplň práce v anglickém jazyce
Andrew Thomason designed an elegant algorithm for finding a second Hamitonian cycle in a cubic graph. By this he reproved Smith's theorem. Later Adam Krawczyk constructed an example of a graph for which the algorithm requires an exponential number of steps, when started on a specific edge of the graph. It would be interesting to know if the algorithm requires exponential time when started on any edge of the graph.
- zadáno a potvrzeno stud. odd.