Hypohamiltoniánský graf - Hypohamiltonian graph - Wikipedia

Nesmí být zaměňována s Hamiltonovský graf.
Hypohamiltoniánský graf sestrojený Lindgren (1967).

V matematické oblasti teorie grafů, graf G se říká, že je hypohamiltonián -li G sám o sobě nemá Hamiltonovský cyklus ale každý graf vytvořený odstraněním jediného vrcholu z G je Hamiltonian.

Dějiny

Hypohamiltonovské grafy byly nejprve studovány Sousselier (1963). Lindgren (1967) cituje Gaudin, Herz & Rossi (1964) a Busacker & Saaty (1965) jako další rané příspěvky na toto téma; další rané dílo je u Herz, Duby a Vigué (1967).

Grötschel (1980) shrnuje velkou část výzkumu v této oblasti následující větou: „Články zabývající se těmito grafy ... obvykle vykazují nové třídy hypohamiltonovských nebo hypotrakovatelných grafů, které ukazují, že pro určité objednávky n takové grafy skutečně existují nebo že mají podivné a neočekávané vlastnosti. “

Aplikace

Hypohamiltonovské grafy vznikají v celočíselné programování řešení problém obchodního cestujícího: definují určité druhy hypohamiltonovských grafů fazety z cestující prodavač polytop, tvar definovaný jako konvexní obal sady možných řešení problému obchodního cestujícího a tyto aspekty mohou být použity v metody řezné roviny za vyřešení problému.[1] Grötschel (1980) podotýká, že výpočetní složitost stanovení, zda je graf hypohamiltoniánský, i když neznámý, je pravděpodobně vysoký, takže je obtížné najít aspekty těchto typů s výjimkou těch definovaných malými hypohamiltonovskými grafy; naštěstí nejmenší grafy vedou k nejsilnějším nerovnostem pro tuto aplikaci.[2]

Pojmy úzce související s hypohamiltonicitou byly také použity Park, Lim & Kim (2007) měřit odolnost proti chybám z topologie sítě pro paralelní výpočty.

Vlastnosti

Každý hypohamiltonovský graf musí být 3připojen k vrcholu, protože odstranění jakýchkoli dvou vrcholů opouští hamiltonovskou cestu, která je spojena. Existují n-vertexové hypohamiltonovské grafy, ve kterých je maximální stupeň n/ 2 a ve kterých je přibližně n2/ 4 hrany.[3]

Thomassenův (1974b) obvodový 3 hypohamiltoniánský graf.

Herz, Duby a Vigué (1967) domníval se, že každý hypohamiltonovský graf má obvod 5 nebo více, ale toto bylo vyvráceno uživatelem Thomassen (1974b), kteří našli příklady s obvodem 3 a 4. Nějakou dobu nebylo známo, zda může být hypohamiltonovský graf rovinný, ale nyní je známo několik příkladů,[4] nejmenší z nich má 40 vrcholů.[5] Každý rovinný hypohamiltoniánský graf má alespoň jeden vrchol s pouhými třemi hranami.[6]

Pokud 3-pravidelný graf je Hamiltonian, jeho okraje mohou být barevné se třemi barvami: použijte alternativní barvy pro okraje Hamiltonovského cyklu (který musí mít rovnoměrnou délku podle handmaking lemma ) a třetí barva pro všechny zbývající hrany. Proto všichni snarks, kubické grafy bez můstku, které vyžadují čtyři barvy okrajů, musí být jiné než hamiltonovské a mnoho známých snarků je hypohamiltoniánských. Každý hypohamiltoniánský snark je bikritický: odstranění jakýchkoli dvou vrcholů ponechá podgraf, jehož okraje lze obarvit pouze třemi barvami.[7] Lze jednoduše popsat tříbarevnost tohoto podgrafu: po odstranění jednoho vrcholu obsahují zbývající vrcholy hamiltonovský cyklus. Po odstranění druhého vrcholu se z tohoto cyklu stane cesta, jejíž okraje mohou být obarveny střídáním dvou barev. Zbývající hrany tvoří a vhodný a mohou být obarveny třetí barvou.

Barevné třídy libovolného 3-zbarvení okrajů 3-pravidelného grafu tvoří tři shody, takže každá hrana patří přesně jedné ze shody. Hypohamiltonianští žraloci nemají oddíl na shody tohoto typu, ale Häggkvist (2007) domněnky, že hrany jakéhokoli hypohamiltonovského snarku lze použít k vytvoření šesti shody, takže každá hrana patří přesně dvěma shody. Toto je speciální případ domněnky Berge – Fulkerson, že jakýkoli snark má s touto vlastností šest shod.

Hypohamiltonovské grafy nemohou být bipartitní: v bipartitním grafu lze vrchol odstranit pouze za účelem vytvoření Hamiltonovského podgrafu, pokud patří do větší ze dvou barevných tříd grafu. Nicméně, každý bipartitní graf vyskytuje se jako indukovaný podgraf nějakého hypohamiltonovského grafu.[8]

Příklady

Nejmenší hypohamiltonovský graf je Petersenův graf (Herz, Duby a Vigué 1967 ). Obecněji, zobecněný Petersenův graf GP (n, 2) je hypohamiltonián, když n je 5 (mod 6);[9] Petersenův graf je instancí této konstrukce s n = 5.

Lindgren (1967) našel další nekonečnou třídu hypohamiltonovských grafů, ve kterých je počet vrcholů 4 (mod 6). Lindgrenova konstrukce se skládá z cyklu délky 3 (mod 6) a jednoho centrálního vrcholu; centrální vrchol je spojen s každým třetím vrcholem cyklu hranami, které nazývá paprsky, a vrcholy dvě polohy od každého koncového bodu paprsků jsou vzájemně spojeny. Nejmenší instancí Lindgrenovy konstrukce je opět Petersenův graf.

Další nekonečné rodiny jsou dány Bondy (1972), Doyen & van Diest (1975), a Gutt (1977).

Výčet

Václav Chvátal v roce 1973 dokázal, že pro všechny dostatečně velké n existuje hypohamiltonovský graf s n vrcholy. S přihlédnutím k následným objevům,[10] „Dostatečně velké“ je nyní známo, že znamená, že takové grafy existují pro všechny n ≥ 18. Je znám kompletní seznam hypohamiltonovských grafů s maximálně 17 vrcholy:[11] jsou to 10-vertexový Petersenův graf, 13-vertexový graf a 15-vertexový graf nalezený počítačovým vyhledáváním Herz (1968) a čtyři 16-vrcholné grafy. Existuje nejméně třináct hypohamiltonovských grafů s 18 vrcholy. Použitím metody klopného obvodu z Chvátal (1973) na Petersenův graf a květina snark, je možné ukázat, že počet hypohamiltonovských grafů a konkrétněji počet hypohamiltonovských snarků roste jako exponenciální funkce počtu vrcholů.[12]

Zobecnění

Teoretici grafů také studovali hypotracovatelné grafy, grafy, které neobsahují hamiltonovskou cestu, ale takové, že každá podmnožina n - 1 vrcholy mohou být spojeny cestou.[13] Analogické definice hypohamiltonicity a hypotraeability pro řízené grafy byly zvažovány několika autory.[14]

Ekvivalentní definice hypohamiltonovských grafů je ta, že jejich nejdelší cyklus má délku n - 1 a že průnik všech nejdelších cyklů je prázdný. Menke, Zamfirescu a Zamfirescu (1998) zkoumat grafy se stejnou vlastností, že průsečík nejdelších cyklů je prázdný, ale ve kterých je nejdelší délka cyklu kratší než n − 1. Herz (1968) definuje cyklovatelnost grafu jako největší číslo k takové, že každý k vrcholy patří do cyklu; hypohamiltonovské grafy jsou přesně grafy, které mají cyklovatelnost n - 1. Podobně, Park, Lim & Kim (2007) definovat graf jako be-chyba hamiltoniánů pokud odstranění maximálně ƒ vrcholů zanechá hamiltonovský podgraf. Schauerte & Zamfirescu (2006) prostudujte grafy s cyklovatelností n − 2.

Poznámky

  1. ^ Grötschel (1977); Grötschel (1980); Grötschel & Wakabayashi (1981).
  2. ^ Goemans (1995).
  3. ^ Thomassen (1981).
  4. ^ Existenci rovinných hypohamiltoniánských grafů položil jako otevřenou otázku Chvátal (1973), a Chvátal, Klarner & Knuth (1972) nabídl cenu 5 $ za konstrukci jednoho. Thomassen (1976) použitý Grinbergova věta najít rovinné hypohamiltonovské grafy obvodu 3, 4 a 5 a ukázat, že existuje nekonečně mnoho planárních hypohamiltonovských grafů.
  5. ^ Jooyandeh a kol. (2013) pomocí počítačového vyhledávání a Grinbergovy věty. Dříve malé planární hypohamiltonovské grafy s 42, 57, respektive 48 vrcholy, byly nalezeny pomocí Wiener & Araya (2009), Hatzel (1979) a Zamfirescu a Zamfirescu (2007).
  6. ^ Thomassen (1978).
  7. ^ Steffen (1998); Steffen (2001).
  8. ^ Collier & Schmeichel (1977).
  9. ^ Robertson (1969) prokázal, že tyto grafy nejsou hamiltonovské, zatímco je snadné ověřit, že jejich vymazání jedním vrcholem jsou hamiltonovské. Vidět Alspach (1983) pro klasifikaci ne-hamiltonovských zobecněných Petersenových grafů.
  10. ^ Thomassen (1974a); Doyen & van Diest (1975).
  11. ^ Aldred, McKay & Wormald (1997). Viz také (sekvence A141150 v OEIS ).
  12. ^ Skupień (1989); Skupień (2007).
  13. ^ Kapoor, Kronk & Lick (1968); Kronk (1969); Grünbaum (1974); Thomassen (1974a).
  14. ^ Fouquet & Jolivet (1978); Grötschel & Wakabayashi (1980); Grötschel & Wakabayashi (1984); Thomassen (1978).

Reference

  • Aldred, R. A .; McKay, B. D.; Wormald, N. C. (1997), „Malé hypohamiltonovské grafy“ (PDF), J. Combinatorial Math. Kombinatorický výpočet., 23: 143–152.
  • Alspach, B. R. (1983), „Klasifikace Hamiltonovských zobecněných Petersenových grafů“, Journal of Combinatorial Theory, Series B, 34 (3): 293–312, doi:10.1016/0095-8956(83)90042-4, PAN  0714452.
  • Bondy, J. A. (1972), „Variace hamiltonovského tématu“, Kanadský matematický bulletin, 15: 57–62, doi:10.4153 / CMB-1972-012-3.
  • Busacker, R. G .; Saaty, T. L. (1965), Konečné grafy a sítě, McGraw-Hill.
  • Chvátal, V. (1973), „Flip-flops in hypo-Hamiltonian graphs“, Kanadský matematický bulletin, 16: 33–41, doi:10.4153 / CMB-1973-008-9, PAN  0371722.
  • Chvátal, V.; Klarner, D. A .; Knuth, D. E. (1972), Vybrané problémy kombinatorického výzkumu (PDF), Tech. Zpráva STAN-CS-72-292, Computer Science Department, Stanford University.
  • Collier, J. B .; Schmeichel, E. F. (1977), „Nové konstrukce klopného obvodu pro hypohamiltonovské grafy“, Diskrétní matematika, 18 (3): 265–271, doi:10.1016 / 0012-365X (77) 90130-3, PAN  0543828.
  • Doyen, J .; van Diest, V. (1975), „Nové rodiny hypohamiltonovských grafů“, Diskrétní matematika, 13 (3): 225–236, doi:10.1016 / 0012-365X (75) 90020-5, PAN  0416979.
  • Fouquet, J.-L .; Jolivet, J. L. (1978), „Hypohamiltonovské orientované grafy“, Cahiers Center Études Rech. Opér., 20 (2): 171–181, PAN  0498218.
  • Gaudin, T .; Herz, P .; Rossi (1964), „Solution du problème č. 29“, Rev. Franç. Rech. Opérationnelle, 8: 214–218.
  • Goemans, Michel X. (1995), „Nejhorší srovnání platných nerovností pro TSP“, Matematické programování, 69 (1–3): 335–349, CiteSeerX  10.1.1.52.8008, doi:10.1007 / BF01585563.
  • Grötschel, M. (1977), „Hypohamiltonovské aspekty symetrického polytopu obchodního cestujícího“, Zeitschrift für Angewandte Mathematik und Mechanik, 58: 469–471.
  • Grötschel, M. (1980), „K problému monotónního symetrického obchodního cestujícího: hypohamiltonovské / hypotrakovatelné grafy a aspekty“, Matematika operačního výzkumu, 5 (2): 285–292, doi:10,1287 / bř. 5.2.285, JSTOR  3689157.
  • Grötschel, M.; Wakabayashi, Y. (1980), „Hypohamiltonovské digrafy“, Metody operačního výzkumu, 36: 99–119, Zbl  0436.05038.
  • Grötschel, M.; Wakabayashi, Y. (1981), „O struktuře monotónního asymetrického obchodního cestujícího polytopa I: hypohamiltonovské aspekty“, Diskrétní matematika, 24: 43–59, doi:10.1016 / 0012-365X (81) 90021-2.
  • Grötschel, M.; Wakabayashi, Y. (1984), "Constructions of hypotraceable digraphs", in Cottle, R. W .; Kelmanson, M. L .; Korte, B. (eds.), Matematické programování (Proc. International Congress, Rio de Janeiro, 1981), Severní Holandsko.
  • Grünbaum, B. (1974), „Vrcholy zmeškané nejdelšími cestami nebo okruhy“, Journal of Combinatorial Theory, Series A, 17: 31–38, doi:10.1016/0097-3165(74)90025-9, PAN  0349474.
  • Gutt, Simone (1977), „Nekonečné rodiny hypohamiltonovských grafů“, Académie Royale de Belgique, Bulletin de la Classe des Sciences, 5e Série, 63 (5): 432–440, PAN  0498243.
  • Häggkvist, R. (2007), Mohar, B.; Nowakowski, R. J .; West, D. B. (eds.), „Problem 443. Special case of the Fulkerson Conjecture“, Problémy výzkumu z 5. slovinské konference (Bled, 2003), Diskrétní matematika, 307 (3–5): 650–658, doi:10.1016 / j.disc.2006.07.013.
  • Hatzel, W. (1979), „Ein planarer hypohamiltonscher Graph mit 57 Knoten“, Matematika. Ann., 243 (3): 213–216, doi:10.1007 / BF01424541, PAN  0548801.
  • Herz, J. C. (1968), „Sur la cyclabilité des graphes“, Počítače v matematickém výzkumu, Severní Holandsko, str. 97–107, PAN  0245461.
  • Herz, J. C .; Duby, J. J .; Vigué, F. (1967), „Recherche systématique des graphes hypohamiltoniens“, v Rosenstiehl, P. (vyd.), Theory of Graphs: International Symposium, Rome 1966„Paris: Gordon and Breach, s. 153–159.
  • Jooyandeh, Mohammadreza; McKay, Brendan D.; Östergård, Patric R. J .; Pettersson, Ville H .; Zamfirescu, Carol T. (2013), Rovinné hypohamiltonovské grafy na 40 vrcholech, arXiv:1302.2698, Bibcode:2013arXiv1302.2698J.
  • Kapoor, S. F .; Kronk, H. V .; Lick, D. R. (1968), „O objížďkách v grafech“, Kanadský matematický bulletin, 11 (2): 195–201, doi:10.4153 / CMB-1968-022-8, PAN  0229543.
  • Kronk, H. V. (1969), Klee, V. (ed.), „Existuje hypotracovatelný graf?“, Problémy s výzkumem, Americký matematický měsíčník, 76 (7): 809–810, doi:10.2307/2317879, JSTOR  2317879.
  • Lindgren, W. F. (1967), „Nekonečná třída hypohamiltonovských grafů“, Americký matematický měsíčník, 74 (9): 1087–1089, doi:10.2307/2313617, JSTOR  2313617, PAN  0224501.
  • Máčajová, E .; Škoviera, M. (2007), „Konstrukce hypohamiltoniánských snarků s cyklickou konektivitou 5 a 6“, Electronic Journal of Combinatorics, 14 (1): R14.
  • Menke, B .; Zamfirescu, T. I .; Zamfirescu, C. M. (1998), „Průniky nejdelších cyklů v mřížkových grafech“, Journal of Graph Theory, 25 (1): 37–52, doi:10.1002 / (SICI) 1097-0118 (199705) 25: 1 <37 :: AID-JGT2> 3.0.CO; 2-J.
  • Mohanty, S. P .; Rao, D. (1981), "Rodina hypo-hamiltonovských zobecněných hranolů", Kombinatorika a teorie grafůPřednášky z matematiky, 885, Springer-Verlag, str. 331–338, doi:10.1007 / BFb0092278, ISBN  978-3-540-11151-1.
  • Park, J.-H .; Lim, H.-S .; Kim, H.-C. (2007), „Panconnectivity and pancyclicity of hypercube-like propojovacích sítí s vadnými prvky“, Teoretická informatika, 377 (1–3): 170–180, doi:10.1016 / j.tcs.2007.02.029.
  • Robertson, G. N. (1969), Grafy minimální omezení obvodu, valence a konektivity„Diplomová práce, Waterloo, Ontario: University of Waterloo.
  • Schauerte, Boris; Zamfirescu, C. T. (2006), „Pravidelné grafy, ve kterých každý pár bodů unikne nějakému nejdelšímu cyklu“, An. Univ. Craiova Ser. Rohož. Informovat., 33: 154–173, PAN  2359901.
  • Skupień, Z. (1989), „Exponenciálně mnoho hypohamiltonovských grafů“, Grafy, hypergrafy a matroidy III (Proc. Conf. Kalsk 1988)„Zielona Góra: Higher College of Engineering, s. 123–132. Jak uvádí Skupień (2007).
  • Skupień, Z. (2007), „Exponentially many hypohamiltonian snarks“, 6. česko-slovenské mezinárodní symposium o kombinatorice, teorii grafů, algoritmech a aplikacích, Elektronické poznámky v diskrétní matematice, 28, str. 417–424, doi:10.1016 / j.endm.2007.01.059.
  • Sousselier, R. (1963), Berge, C. (ed.), „Problème no. 29: Le cercle des irascibles“, Problèmes plaisants et délectables, Rev. Franç. Rech. Opérationnelle, 7: 405–406.
  • Steffen, E. (1998), "Klasifikace a charakterizace snarků", Diskrétní matematika, 188 (1–3): 183–203, doi:10.1016 / S0012-365X (97) 00255-0, PAN  1630478.
  • Steffen, E. (2001), „O bikritických snarkech“, Matematika. Slovaca, 51 (2): 141–150, PAN  1841443.
  • Thomassen, Carsten (1974a), „Hypohamiltonovské a hypotrakovatelné grafy“, Diskrétní matematika, 9: 91–96, doi:10.1016 / 0012-365X (74) 90074-0, PAN  0347682.
  • Thomassen, Carsten (1974b), „On hypohamiltonian graphs“, Diskrétní matematika, 10 (2): 383–390, doi:10.1016 / 0012-365X (74) 90128-9, PAN  0357226.
  • Thomassen, Carsten (1976), „Planární a nekonečné hypohamiltonovské a hypotrakovatelné grafy“, Diskrétní matematika, 14 (4): 377–389, doi:10.1016 / 0012-365X (76) 90071-6, PAN  0422086.
  • Thomassen, Carsten (1978), „Hypohamiltonovské grafy a digrafy“, Teorie a aplikace grafů (Proc. Internat. Conf., Western Mich. Univ., Kalamazoo, Mich., 1976)Přednášky z matematiky, 642, Berlín: Springer-Verlag, str. 557–571, PAN  0499523.
  • Thomassen, Carsten (1981), „Planar cubic hypo-Hamiltonian and hypotraceable graphs“, Journal of Combinatorial Theory, Series B, 30: 36–44, doi:10.1016/0095-8956(81)90089-7, PAN  0609592.
  • Wiener, Gábor; Araya, Makoto (2009), Konečná otázka, arXiv:0904.3012, Bibcode:2009arXiv0904,3012W.
  • Zamfirescu, C. T .; Zamfirescu, T. I. (2007), "Planární hypohamiltoniánský graf se 48 vrcholy", Journal of Graph Theory, 55 (4): 338–342, doi:10.1002 / jgt.20241.

externí odkazy