Konstrukce Grayových kódů se speciálními vlastnostmi
| Thesis title in Czech: | Konstrukce Grayových kódů se speciálními vlastnostmi |
|---|---|
| Thesis title in English: | Construction of Gray codes with special properties |
| Key words: | Grayův kód, párování, problém Ruskey - Savage, hyperkrychle |
| English key words: | Gray code, matching, Ruskey-Savage problem, hypercube |
| Academic year of topic announcement: | 2016/2017 |
| Thesis type: | Bachelor's thesis |
| Thesis language: | čeština |
| Department: | Department of Software and Computer Science Education (32-KSVI) |
| Supervisor: | doc. RNDr. Tomáš Dvořák, CSc. |
| Author: | hidden - assigned and confirmed by the Study Dept. |
| Date of registration: | 23.04.2017 |
| Date of assignment: | 03.05.2017 |
| Confirmed by Study dept. on: | 04.05.2017 |
| Date and time of defence: | 06.09.2017 00:00 |
| Date of electronic submission: | 24.07.2017 |
| Date of submission of printed version: | 21.07.2017 |
| Date of proceeded defence: | 06.09.2017 |
| Opponents: | RNDr. Jiří Fink, Ph.D. |
| Guidelines |
| Grayův kód řádu n je posloupnost všech n-bitových řetězců, v níž se sousední řetězce liší vždy v jediném bitu [4]. Hyperkrychle řádu n je graf, jehož vrcholy jsou všechny n-bitové řetězce, přičemž hrany vedou mezi vrcholy, které se liší v jediném bitu. Ruskey a Savage v roce 1993 publikovali otázku, zdali lze každé párování v hyperkrychli rozšířit na Grayův kód [6]. Kreweras v roce 1996 navázal hypotézou, podle níž je odpověď pozitivní pro každé perfektní párování [5]. Hypotézu, kterou též popularizoval Knuth v monografii [4], vyřešil o deset let později mimořádně elegantním způsobem doktorand MFF UK Jiří Fink [1]. Práce [2] popisuje alternativní řešení, kde je požadovaný cyklus sestrojen metodou rozděl a panuj. Původní problém Ruskey - Savage pro libovolné párování však zůstává stále otevřený.
Hlavním cílem práce je zobecnění Finkova výsledku na hamiltonovské cesty v hyperkrychli s předepsanými koncovými vrcholy. Pro rozšíření induktivní konstrukce popsané v [2] bude kritické ověření báze indukce, které bude zřejmě třeba provést na počítači. Kvůli exponenciální explozi počtu rozšiřovaných párování bude nezbytné, důsledně omezovat počet instancí využíváním automorfismů hyperkychle. Na tento krok lze navázat rozšířením počítačových experimentů z perfektních na libovolná párování, což přirozeně směřuje k pokusu o počítačové ověření malých instancí původního problému Ruskey - Savage. Protože existence řešení je již experimentálně ověřena pro n ≤ 5 [7], přičemž prozkoumání vyšších dimenzí může být časově velmi náročné i při využití automorfismů, nadějnější cestou k dosažení částečného pokroku může být systematické generování a prověřování "těžkých" instancí problému. Jako perspektivní kandidát pro tento účel se nabízí konstrukce maximálních párování co nejmenší velikosti. Protože určení minimální velikosti maximálního párování v hyperkrychli je dalším dlouho otevřeným problémem, součástí práce může být i zlepšení klasické Forcadovy konstrukce z roku 1973 [3]. |
| References |
| [1] J. Fink, Perfect matchings extend to Hamilton cycles in hypercubes, J. Comb. Theory Ser. B 97 (2007), 1074–1076, http://dx.doi.org/10.1016/j.jctb.2007.02.007
[2] J. Fink, Matching graphs of hypercubes and complete bipartite graphs, Eur. J. Comb. 30 (2009), 1624–1629, http://dx.doi.org/10.1016/j.ejc.2009.03.007 [3] R. Forcade, Smallest maximal matchings in the graph of the d-dimensional cube, J. Comb. Theory Ser. B 14 (1973), 153-156, http://doi.org/10.1016/0095-8956(73)90059-2 [4] D. E. Knuth, The Art of Computer Programming, Volume 4, Fascicle 2: Generating All Tuples and Permutations, Addison-Wesley Professional, 2005 [5] G. Kreweras, Matchings and Hamiltonian cycles on hypercubes, Bull. Inst. Combin. Appl. 16 (1996), 87–91 [6] F. Ruskey, C. Savage, Hamilton cycles which extend transposition matchings in Cayley graphs of Sn, SIAM J. Discrete Math. 6 (1993), 152–166, http://dx.doi.org/10.1137/0406012 [7] E. Zulkoski, C. Bright, A. Heinle, I. Kotsireas, K. Czarnecki, V. Ganesh, Combining SAT solvers with computer algebra systems to verify combinatorial conjectures, J. Autom. Reasoning (2016), http://dx.doi.org/10.1007/s10817-016-9396-y |