Konstrukce Grayových kódů se speciálními vlastnostmi

Abstract

A (cyclic) Gray code is a (cyclic) sequence of all n-bit strings in which consecutive strings differ in a single bit. Ruskey and Savage in 1993 asked whether every matching in a hypercube can be extended to a cyclic Gray code. An affirmative answer is known for perfect matchings (Fink, 2007) while the ge- neral case is still open. The main contribution of this thesis is a generalization of Fink's result to Gray codes with prescribed ends. The characterization of perfect matchings extendable in this way is verified for n = 5 with the assistance of a com- puter, which is useful as a basis for the inductive proof of the general statement. The other part of the thesis is focused on smallest maximal matchings in hyper- cubes which could possibly form especially hard instances of the Ruskey-Savage problem. We devise a novel method which provides - in particular for small di- mensions - maximal matchings of smaller size than the classical asymptotically optimal construction (Forcade, 1973). An adjusted program from the first part is then applied to test the Ruskey-Savage problem over these matchings, however, the extending Gray code is always discovered. 1

(Cyklický) Grayův kód řádu n je (cyklická) posloupnost všech n- bitových řetězců, v nichž se sousední řetězce liší vždy 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 cyklický Grayův kód. Problém je stále otevřený, pozitivní řešení je však známo pro každé perfektní párování (Fink, 2007). Hlavním výsledkem práce je zobecnění Finkova výsledku na Grayův kód s předepsanými koncovými vrcholy. Charakterizace takto rozšiřitelných perfektních párování je pro n = 5 ověřena na počítači, tento výsledek slouží jako báze induktivního důkazu tvrzení pro vyšší dimenze. Druhá část práce se soustředí na problém maximálních párování v hy- perkrychlích co nejmenší velikosti, která jsou perspektivním kandidátem na ne- gativní řešení problému Ruskey-Savage. Je zde navržena nová metoda, která dává především pro malé dimenze párování menší velikosti nežli klasická asymptoticky optimální konstrukce (Forcade, 1973). Upravený program z první části je následně využit k testování problému Ruskey-Savage pro tato párování, rozšiřující Grayův kód je však vždy nalezen. 1