Taits dohad - Taits conjecture - Wikipedia
V matematice Taitova domněnka uvádí, že „Každý 3 připojené rovinný kubický graf má Hamiltonovský cyklus (podél okrajů) skrz všechny jeho vrcholy Navrhl to P. G. Tait (1884 ) a vyvrácen W. T. Tutte (1946 ), který zkonstruoval protipříklad s 25 plochami, 69 hranami a 46 vrcholy. Několik menších protipříkladů s 21 plochami, 57 hranami a 38 vrcholy bylo později prokázáno minimem Holton & McKay (1988) Podmínka, že graf musí být 3-pravidelný, je nutná kvůli mnohostěnům, jako je kosočtverečný dvanáctistěn, který tvoří a bipartitní graf se šesti vrcholy čtyři stupně na jedné straně a osmi vrcholy tři stupně na druhé straně; protože jakýkoli hamiltonovský cyklus by musel střídat obě strany bipartice, ale mají nestejný počet vrcholů, kosočtverečný dvanáctistěn není hamiltonián.
Domněnka byla významná, protože pokud by byla pravdivá, znamenalo by to čtyřbarevná věta: jak popsal Tait, čtyřbarevný problém je ekvivalentní problému hledání 3-hranové barvy z bez můstku kubické planární grafy. V Hamiltonově kubickém rovinném grafu lze takové zbarvení hran snadno najít: v cyklu používejte střídavě dvě barvy a pro všechny zbývající hrany třetí barvu. Alternativně může být 4-zbarvení ploch hamiltonovského kubického rovinného grafu vytvořeno přímo pomocí dvou barev pro plochy uvnitř cyklu a dvou dalších barev pro plochy vně.
Tutteův protiklad
Tuttein fragment
Klíčem k tomuto příkladu je to, co je nyní známé jako Tuttein fragment, zobrazené vpravo.
Pokud je tento fragment součástí většího grafu, pak jakýkoli hamiltonovský cyklus v grafu musí jít dovnitř nebo ven z horního vrcholu (a buď jednoho z nižších). Nemůže jít v jednom spodním vrcholu a ven druhým.
Protiklad
Fragment lze poté použít ke konstrukci ne-hamiltoniánu Tutte graph, tím, že dohromady tři takové fragmenty, jak je znázorněno na obrázku. „Povinné“ hrany fragmentů, které musí být součástí jakékoli Hamiltonovské cesty fragmentem, jsou spojeny ve středním vrcholu; protože jakýkoli cyklus může používat pouze dvě z těchto tří hran, nemůže existovat žádný Hamiltonovský cyklus.
Výsledný Tutte graph je 3 připojené a rovinný, takže Steinitzova věta je to graf mnohostěnu. Celkově má 25 ploch, 69 okrajů a 46 vrcholů. Lze jej realizovat geometricky ze čtyřstěnu (jehož plochy odpovídají čtyřem velkým plochám na výkresu, z nichž tři jsou mezi dvojicemi fragmentů a čtvrtý z nich tvoří exteriér) vynásobením zkrácení tří jeho vrcholů.
Menší protiklady
Tak jako Holton & McKay (1988) ukazují, že existuje přesně šest 38-vrcholných ne-hamiltonovských mnohostěnů, které mají netriviální tříbřité řezy. Jsou vytvořeny nahrazením dvou vrcholů a pětiúhelníkový hranol stejným fragmentem, jaký byl použit v příkladu Tutte.
Viz také
- Grinbergova věta, nezbytná podmínka pro existenci Hamiltonovského cyklu, kterou lze použít k prokázání, že graf tvoří protiklad Taitovy domněnky
- Barnettina domněnka, stále otevřené upřesnění Taitova domněnky o tom, že každý bipartitní krychlový polyedrický graf je Hamiltonian.[1]
Poznámky
- ^ Barnettina domněnka Otevřená problémová zahrada, vyvoláno 12. 10. 2009.
Reference
- Holton, D. A .; McKay, B. D. (1988), „Nejmenší nehamiltonovské 3 spojené kubické planární grafy mají 38 vrcholů“, Journal of Combinatorial Theory, Series B, 45 (3): 305–319, doi:10.1016/0095-8956(88)90075-5.
- Tait, P. G. (1884), „Listing's Topologie", Filozofický časopis, 5. série, 17: 30–46. Přetištěno Vědecké práce, Sv. II, s. 85–98.
- Tutte, W. T. (1946), „Na Hamiltonových okruzích“ (PDF), Journal of the London Mathematical Society, 21 (2): 98–101, doi:10.1112 / jlms / s1-21.2.98.
Částečně na základě sci.math příspěvek od Billa Taylora, použitý se svolením.