Cesty, kružnice a párování v hyperkrychli
Základní pojmy- n-dimenzionální hyperkrychle
- je graf, jehož vrcholy jsou posloupnosti čísel 0 a 1 délky n a hranou jsou spojeny právě ty vrcholy, jejichž posloupnosti se liší právě v jedné pozici. Značí se Q_n. Například čtverec je 2-dimenzionální hyperkrychle a klasická krychle je 3-dimenzionální hyperkrychle. Parita vrcholu je parita (sudost či lichost) počtu jedniček v posloupnosti. Hyperkrychle je bipartitní graf, protože hranou jsou spojeny jen vrcholy různé parity.
- Párování
- je množina hran daného grafu taková, že každý vrchol je incidentní s nejvýše jednou hranou párování. Párování je perfektní, pokud každý vrchol je incidentní právě s jednou hranou párování.
- Hamiltonovská kružnice
- je kružnice procházející všemi vrcholy daného grafu.
L. Gros [1] v roce 1872 dokázal, že hyperkrychle obsahuje Hamiltonovskou kružnici, a Frank Gray si v roce 1947 patentoval postup na její sestrojení známé jako Gray codes. Od té doby řada lidí studuje, za jakých omezujících podmínek lze Hamiltonovskou kružnici v hyperkrychli sestrojit.
Rozšiřování párování v hyperkrychli na Hamiltonovskou kružnici
Dokázal [4] jsem, že každé perfektní párování v hyperkrychli lze rozšířit na Hamiltonovskou kružnici. Ruskey a Savage [5] položili obecnější otázku, zda každé (nejen perfektní) párování lze rozšířit na Hamiltonovskou kružnici. Tato otázka je hodně těžká, a proto má smysl studovat i její speciální případy, kde zadaná párování mají různé speciální vlastnosti.
Existuje i jiná třída grafů, ve které lze každé perfektní párovaní rozšířit na Hamiltonovskou kružnici? Úplný graf na vrcholech grafu G označme K(G). Ve článku [4] se dokazuje silnější výsledek, který tvrdí, že pro každé perfektní párovaní P v K(Q_d) existuje perfektní párování R v Q_d takové, že sjednocení P a R dává Hamiltonovskou kružnici. Tuto vlastnost mají úplné grafy a úplné bipartitní grafy. Podaří se vám najít další? Co třeba kartézský součin úplných (bipartitních) grafů?
Dlouhé cesty a kružnice v hyperkrychli s chybnými vrcholy.
Nechť F je množina vrcholů hyperkrychle, kterých se říká chybné nebo vadné, a hyperkrychli bez těchto vadných vrcholů značíme Q_n-F. Našim cílem je hledat co nejdelší cesty a kružnice v Q_n-F. Je snadné nahlédnout, že obecně není možné najít Hamiltonovskou kružnici ani cestu v Q_n-F. Buď můžeme přidat paritní podmínky na F, hledat kružnice délky 2^n - 2 |F| (cesty délky 2^n - 2 |F| - 2 se zadanými koncovými vrcholy) nebo kombinovat tyto možnosti.
Fu [8] dokázal, že pro každou množinu chybných vrcholů F v Q_n velikosti nejvýše n - 2 existuje cesta délky alespoň 2^n - 2 |F| - 2 mezi předepsanými dvěma vrcholy. Ve společném článku s Petrem Gregorem [6] jsme dokázali, že počet chyb je možné zvýšit na 2n - 4, pokud oba předepsané vrcholy u a v mají alespoň jednoho souseda různého od F, u, v. Snadno nahlédnete, že počet chyb je v těchto větách maximální. Jaký je maximální počet chyb, pokud zvýšíme počet zdravých sousedů koncových vrcholů na dva či více?
V navazujícím článku [7] jsem dokázali, že pro každou množinu chybných vrcholů F v Q_n velikosti nejvýše (n^2 + n - 4) / 4 a každou dvojicí vrcholů u a v takové, že u i v sousedí s nejvýše třemi vrcholy F, existuje cesta v Q_n-F mezi u a v délky alespoň 2^n - 2 |F| - 2. Jaká je maximální možná velikost F, aby tato věta platila? Jaká je maximální velikost z F, pokud předepsané koncové vrcholy nemají ani jednoho chybného souseda? Zůstane velikost F kvadratická, i když se zvýší počet chybných sousedů předepsaných koncových vrcholů (Tj. rozhodněte zda pro každé k existuje polynom f_k(n) kvadratický v n takový, že pro každou množinu chybným vrcholů F v Q_n velikosti nejvýše f_k(n) a kažkou dvojici vrcholů u a v takové, že u i v sousedí s nejvýše k vrcholy z F, existuje cesta v Q_n-F mezi u a v délky alespoň 2^n - 2 |F| - 2.)?
Reference
[1] L. Gros: Théorie du Baguenodier, Aimé Vingtrinier, Lyon, 1872.[2] N. Castaneda, V. Gochev, I. Gotchev and F. Latour: On path coverings of hypercubes with one faulty vertex. Submitted.
[3] M. Lewinter and W. Widulski: Hyper-Hamilton laceable and caterpillar-spannable product graphs, Comput. Math. Appl. 34 (1997), 99-104.
[4] J. Fink. Perfect matchings extend to Hamilton cycles in hypercubes. J. Comb. Theory, Ser. B, 97(6):1074-1076, 2007.
[5] F. Ruskey and C.D. Savage. Hamilton cycles that extend transposition matchings in cayley graphs of sn. SIAM Journal on Discrete Mathematics, 6(1):152-166, 1993.
[6] J. Fink and P. Gregor. Long paths and cycles in hypercubes with faulty vertices. Information Sciences, 179:3634-3644, 2009.
[7] J. Fink and P Gregor. Long cycles in hypercubes with optimal number of faulty vertices. Manuscript, 2009.
[8] J.-S. Fu. Longest fault-free paths in hypercubes with vertex faults. Information Sciences, 176(7):759-771, 2006.