Konstrukce Grayových kódů se speciálními vlastnostmi
| Název práce v češtině: | Konstrukce Grayových kódů se speciálními vlastnostmi |
|---|---|
| Název v anglickém jazyce: | Construction of Gray codes with special properties |
| Klíčová slova: | Grayův kód, párování, problém Ruskey - Savage, hyperkrychle |
| Klíčová slova anglicky: | Gray code, matching, Ruskey-Savage problem, hypercube |
| Akademický rok vypsání: | 2016/2017 |
| Typ práce: | bakalářská práce |
| Jazyk práce: | čeština |
| Ústav: | Katedra softwaru a výuky informatiky (32-KSVI) |
| Vedoucí / školitel: | doc. RNDr. Tomáš Dvořák, CSc. |
| Řešitel: | skrytý - zadáno a potvrzeno stud. odd. |
| Datum přihlášení: | 23.04.2017 |
| Datum zadání: | 03.05.2017 |
| Datum potvrzení stud. oddělením: | 04.05.2017 |
| Datum a čas obhajoby: | 06.09.2017 00:00 |
| Datum odevzdání elektronické podoby: | 24.07.2017 |
| Datum odevzdání tištěné podoby: | 21.07.2017 |
| Datum proběhlé obhajoby: | 06.09.2017 |
| Oponenti: | RNDr. Jiří Fink, Ph.D. |
| Zásady pro vypracování |
| 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]. |
| Seznam odborné literatury |
| [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 |