Fleischnerova věta - Fleischners theorem - Wikipedia

2-vrchol spojený graf, jeho čtverec a Hamiltonianův cyklus ve čtverci

v teorie grafů, obor matematiky, Fleischnerova věta dává dostatečnou podmínku, aby graf obsahoval a Hamiltonovský cyklus. Uvádí, že pokud G je 2-vrchol spojený graf, pak čtverec z G je Hamiltonian. je pojmenován po Herbert Fleischner, který svůj důkaz zveřejnil v roce 1974.

Definice a prohlášení

An neorientovaný graf G je Hamiltonian, pokud obsahuje a cyklus který se dotkne každého z jeho vrcholů přesně jednou. Je spojen se 2 vertexy, pokud nemá artikulační vrchol, vrchol, jehož odstranění by ponechalo zbývající graf odpojený. Ne každý graf propojený se 2 vrcholy je hamiltoniánský; protipříklady zahrnují Petersenův graf a kompletní bipartitní graf K._2,3.

Náměstí G je graf G² který má stejný vrchol nastavený jako G, a ve kterém dva vrcholy sousedí, právě když mají vzdálenost maximálně dva palce G. Fleischnerova věta uvádí, že čtverec konečného grafu spojeného se dvěma vrcholy s alespoň třemi vrcholy musí být vždy Hamiltonian. Ekvivalentně, vrcholy každého grafu připojeného ke 2 vrcholům G mohou být uspořádány do a cyklický řád tak, že sousední vrcholy v tomto pořadí jsou ve vzdálenosti nejvýše dvou od sebe G.

Rozšíření

Podle Fleischnerovy věty je možné omezit Hamiltonovský cyklus G² tak, že pro dané vrcholy proti a w z G zahrnuje dva okraje G incident s proti a jeden okraj G incident s w. Navíc pokud proti a w sousedí v G, pak jsou to tři různé okraje G.^[1]

Kromě toho, že má hamiltonovský cyklus, čtverec grafu spojeného se 2 vrcholy G musí být také hamiltonovské spojení (což znamená, že má a Hamiltonova cesta začínající a končící na jakýchkoli dvou určených vrcholech) a 1-hamiltonián (což znamená, že pokud je odstraněn jakýkoli vrchol, zbývající graf má stále Hamiltonovský cyklus).^[2] Musí to být také vrchol pancyklický, což znamená, že pro každý vrchol proti a každé celé číslo k s 3 ≤k ≤ |PROTI(G) |, existuje cyklus délkyk obsahujícíproti.^[3]

Pokud graf G není spojen se dvěma vrcholy, pak jeho čtverec může nebo nemusí mít hamiltonovský cyklus a určení, zda jeden má, je NP-kompletní.^[4]

Nekonečný graf nemůže mít hamiltonovský cyklus, protože každý cyklus je konečný, ale Carsten Thomassen dokázal, že pokud G je nekonečný lokálně konečný graf propojený se dvěma vrcholy s jediným konec pak G² nutně má dvojnásobně nekonečnou Hamiltonovu cestu.^[5] Obecněji, pokud G je lokálně konečný, propojený se dvěma vrcholy a má tedy libovolný počet konců G² má hamiltonovský kruh. V kompaktní topologický prostor vytvořený prohlížením grafu jako a zjednodušený komplex a přidáním dalšího bodu v nekonečnu ke každému z jeho konců je hamiltonovská kružnice definována jako podprostor, který je homeomorfní do euklidovského kruhu a pokrývá každý vrchol.^[6]

Algoritmy

Hamiltonovský cyklus na náměstí an n-vertex 2-spojený graf lze najít v lineárním čase,^[7] zdokonalování oproti prvnímu algoritmickému řešení od Lau^[8] provozní doby Na²)Fleischnerova věta může být použita k poskytnutí a 2-přiblížení do problémové místo cestujícího prodavače problém v metrické prostory.^[9]

Dějiny

Důkaz Fleischnerovy věty oznámil Herbert Fleischner v roce 1971 a publikoval jím v roce 1974, řešení domněnky z roku 1966 Crispin Nash-Williams také nezávisle L. W. Beineke a Michael D. Plummer.^[10] Ve své recenzi Fleischnerovy práce Nash-Williams napsal, že vyřešil „dobře známý problém, který již několik let porazil vynalézavost jiných teoretiků grafů“.^[11]

Fleischnerův původní důkaz byl komplikovaný. Václav Chvátal, v díle, ve kterém vynalezl houževnatost grafu, poznamenal, že čtverec a kgraf spojený s vrcholem je nutně k-tvrdý; on domnělý že 2-tvrdé grafy jsou hamiltoniánské, z čehož by vyplynul další důkaz Fleischnerovy věty.^[12] Protiklady k této domněnce byly později objeveny,^[13] ale možnost, že by konečná vazba na houževnatost mohla znamenat Hamiltonicitu, zůstává v teorii grafů důležitým otevřeným problémem. Jednodušší důkaz jak Fleischnerovy věty, tak jejích rozšíření o Chartrand a kol. (1974), bylo dáno Říha (1991),^[14] a další zjednodušený důkaz věty poskytl Georgakopoulos (2009a).^[15]

Reference

Poznámky

Primární zdroje

• Alstrup, Stephen; Georgakopoulos, Agelos; Rotenberg, Eva; Thomassen, Carsten (2018), „Hamiltonovský cyklus ve čtverci 2-spojeného grafu v lineárním čase“, Sborník z dvacátého devátého výročního sympozia ACM-SIAM o diskrétních algoritmech, str. 1645–1649, doi:10.1137/1.9781611975031.107, ISBN  978-1-61197-503-1
• Bauer, D .; Broersma, H. J .; Veldman, H. J. (2000), „Ne každý 2 tvrdý graf je hamiltoniánský“ Sborník 5. semináře Twente o grafech a kombinatorické optimalizaci (Enschede, 1997), Diskrétní aplikovaná matematika, 99 (1–3): 317–321, doi:10.1016 / S0166-218X (99) 00141-9, PAN  1743840.
• Bondy, J. A. (1971), „Pancyclic graphs“, Sborník z druhé konference v Louisianě o kombinatorice, teorii grafů a výpočtu (Louisiana State Univ., Baton Rouge, La., 1971)„Baton Rouge, Louisiana: Louisianská státní univerzita, s. 167–172, PAN  0325458.
• Chartrand, G.; Hobbs, Arthur M.; Jung, H. A .; Kapoor, S. F .; Nash-Williams, C. St. J. A. (1974), „Čtverec bloku je spojen Hamiltoniánem“, Journal of Combinatorial Theory, Řada B, 16 (3): 290–292, doi:10.1016/0095-8956(74)90075-6, PAN  0345865.
• Chvátal, Václav (1973), „Tvrdé grafy a hamiltonovské obvody“, Diskrétní matematika, 5 (3): 215–228, doi:10.1016 / 0012-365X (73) 90138-6, PAN  0316301.
• Fleischner, Herbert (1974), „Čtverec každého grafu se dvěma spoji je Hamiltonián“, Journal of Combinatorial Theory, Řada B, 16: 29–34, doi:10.1016/0095-8956(74)90091-4, PAN  0332573.
• Fleischner, H. (1976), „Ve čtvercích grafů jsou Hamiltonicita a pancyklicita, Hamiltonovské propojení a pankonektivita rovnocenné pojmy“, Monatshefte für Mathematik, 82 (2): 125–149, doi:10.1007 / BF01305995, PAN  0427135.
• Georgakopoulos, Agelos (2009a), „Krátký důkaz Fleischnerovy věty“, Diskrétní matematika, 309 (23–24): 6632–6634, doi:10.1016 / j.disc.2009.06.024, PAN  2558627.
• Georgakopoulos, Agelos (2009b), „Nekonečné Hamiltonovy cykly ve čtvercích lokálně konečných grafů“, Pokroky v matematice, 220 (3): 670–705, doi:10.1016 / j.aim.2008.09.014, PAN  2483226.
• Hobbs, Arthur M. (1976), „Čtverec bloku je vrchol pancyklický“, Journal of Combinatorial Theory, Řada B, 20 (1): 1–4, doi:10.1016/0095-8956(76)90061-7, PAN  0416980.
• Hochbaum, Dorit S.; Shmoys, David B. (1986), „Jednotný přístup k aproximačním algoritmům pro problémy s úzkým hrdlem“, Deník ACM, New York, NY, USA: ACM, 33 (3): 533–550, doi:10.1145/5925.5933.
• Lau, H. T. (1980), Nalezení Hamiltoniánského cyklu ve čtverci bloku., Ph.D. práce, Montreal: McGill University. Jak uvádí Hochbaum & Shmoys (1986).
• Müttel, Janina; Rautenbach, Dieter (2012), „Krátký důkaz univerzální verze Fleischnerovy věty“, Diskrétní matematika, 313 (19): 1929–1933, doi:10.1016 / j.disc.2012.07.032.
• Parker, R. Garey; Rardin, Ronald L. (1984), „Zaručená heuristika výkonu pro problém obchodního cestujícího s úzkým hrdlem“, Dopisy o operačním výzkumu, 2 (6): 269–272, doi:10.1016/0167-6377(84)90077-4.
• Říha, Stanislav (1991), „Nový důkaz Fleischnerovy věty“, Journal of Combinatorial Theory, Řada B, 52 (1): 117–123, doi:10.1016/0095-8956(91)90098-5, PAN  1109427.
• Thomassen, Carsten (1978), "Hamiltonovské cesty ve čtvercích nekonečných lokálně konečných bloků", v Bollobás, B. (vyd.), Pokroky v teorii grafů (Cambridge Combinatorial Conf., Trinity College, Cambridge, 1977), Annals of Discrete Mathematics, 3, Elsevier, str.269–277, doi:10.1016 / S0167-5060 (08) 70512-0, ISBN  978-0-7204-0843-0, PAN  0499125.
• Podzemní, Polly (1978), „Na grafech s Hamiltonovými čtverci“, Diskrétní matematika, 21 (3): 323, doi:10.1016 / 0012-365X (78) 90164-4, PAN  0522906.

Sekundární zdroje

• Bondy, J. A. (1995), „Základní teorie grafů: cesty a obvody“, Handbook of combineatorics, Vol. 1, 2, Amsterdam: Elsevier, s. 3–110, PAN  1373656.
• Chartrand, Gary; Lesniak, Linda; Zhang, Ping (2010), Grafy a digrafy (5. vydání), CRC Press, str. 139, ISBN  9781439826270.
• Diestel, Reinhard (2012), "10. Hamiltonovské cykly", Teorie grafů (PDF) (opraveno 4. elektronické vydání)