Název: Hamiltonovské kružnice v hyperkrychlích s odstraněnými vrcholy
Překlad názvu: Hamiltonovské kružnice v hyperkrychlích s odstraněnými vrcholy
Autoři: Pěgřímek, David ; Gregor, Petr (vedoucí práce) ; Dvořák, Tomáš (oponent)
Typ dokumentu: Bakalářské práce
Rok: 2013
Jazyk: eng
Abstrakt: [eng] [cze]
In 2001 Stephen Locke conjectured that for every balanced set F of 2k faulty vertices in the n-di- mensional hypercube Qn where n ≥ k + 2 and k ≥ 1 the graph Qn − F is hamiltonian. So far the conjecture remains open although partial results are known; some of them with additional conditions on the set F. We explore hamiltonicity of Qn − F if the set of faulty vertices F forms certain isometric subgraph in Qn. For an odd (even) isometric path P in Qn the graph Qn − V (P) is Hamiltonian laceable for every n ≥ 4 (resp. n ≥ 5). Although a stronger result is known, the method we use in proving the theorem allows us to obtain following results. Let C be an isometric cycle in Qn of length divisible by four for n ≥ 6. Then the graph Qn −V (C) is Hamiltonian laceable. Let T be an isometric tree in Qn with odd number of edges and let S be an isometric tree in Qm with even number of edges. For every n ≥ 4, m ≥ 5 the graphs Qn −T and Qm −S are Hamiltonian laceable. A part of the proof is verified by a computer. 1 V roce 2001 Stephen Locke vyslovil hypotézu, že pro každou vyváženou množinu F obsahující 2k vadných vrcholů n-rozměrné hyperkrychle Qn, kde n ≥ k +2 a k ≥ 1, je graf Qn −F hamiltonovský. Hypotéza je stále otevřená, byť jsou již známá částečná řešení, někdy i s různými podmínkami na F. V této práci prozkoumáme hamiltonovskost grafu Qn −F, pokud množina vadných vrcholů F tvoří určitý izometrický podgraf v Qn. Pro lichou (resp. sudou) izometrickou cestu P v Qn je graf Qn − V (P) Hamiltonovsky laceabilní pro každé n ≥ 4 (resp. n ≥ 5). Přestože je znám silnější výsledek, metoda důkazu nám umožnila získat následující výsledky. Nechť C je izometrický cyklus v Qn délky dělitelné čtyřmi pro n ≥ 6. Pak je graf Qn − V (C) Hamiltonovsky laceabilní. Buď T izometrický strom v Qn s lichým počtem hran a S izometrický strom v Qm se sudým počtem hran. Pak pro každé n ≥ 4, m ≥ 5 jsou grafy Qn − T a Qm − S Hamiltonovsky laceabilní. Část důkazu je ověřena počítačem. 1
Klíčová slova: Hamiltonovská laceabilita; hyperkrychle; izometrický cyklus; izometrický strom; vadný vrchol; fault tolerance; Hamiltonian laceability; hypercube; isometric cycle; isometric tree

Instituce: Fakulty UK (VŠKP) (web)
Informace o dostupnosti dokumentu: Dostupné v digitálním repozitáři UK.
Původní záznam: http://hdl.handle.net/20.500.11956/53491

Trvalý odkaz NUŠL: http://www.nusl.cz/ntk/nusl-493335


Záznam je zařazen do těchto sbírek:
Školství > Veřejné vysoké školy > Univerzita Karlova > Fakulty UK (VŠKP)
Vysokoškolské kvalifikační práce > Bakalářské práce