Википедия

Гипогамильтонов граф

В теории графов говорят, что граф G гипогамильтонов, если сам по себе граф не имеет гамильтонова цикла, но любой граф, полученный удалением одной вершины из G, является гамильтоновым.

Гипогамильтонов граф, построенный Линдгреном[1].

История

править

Гипогамильтоновы графы первым изучал Сусельер в 1963[2]. Линдгрен[1] цитирует Гаудина, Герца и Росси (1964)[3], а также Бусакера и Саати (1965)[4] в качестве дополнительного материала по данной тематике. Ещё одна ранняя работа — статья Герца, Дуби и Виге 1967 года[5].

Грётчел[6] просуммировал большинство работ в этой области следующим высказыванием: «Статьи об этих графах ... обычно выявляют новые классы гипогамильтоновых и гиповычерчиваемых графов и показывают, что для некоторых n такие графы действительно существуют или что они обладают странными и неожиданными свойствами.»

Приложения

править

Гипогамильтоновы графы появляются в целочисленных решениях задачи коммивояжёра – гипогамильтоновы графы определённого вида определяют фасеты многогранника коммивояжёра, тела, определённого как выпуклая оболочка множества возможных решений задачи коммивояжёра, и эти фасеты можно использовать для методов отсекающих плоскостей при решении задачи алгоритмом Гомори[7][6][8]. Грётчел заметил[6], что вычислительная сложность определения, является ли граф гипогамильтоновым, хотя и не известна, по-видимому, высока, что делает трудным поиск фасет такого типа, за исключением фасет, определённых гипогамильтоновыми графами малых размеров. К счастью, наиболее маленькие графы приводят к наиболее сильным неравенствам для данной задачи[9].

Понятия, близкие гипогамильтоновости, использовали Парк, Лим и Ким[10] для измерения отказоустойчивости сетевых топологий параллельных вычислений.

Свойства

править

Любой гипогамильтонов граф должен быть вершинно 3-связным, так как удаление любых двух вершин оставляет гамильтонов путь, который связен (в графе с удалённой одной вершиной существует гамильтонов цикл, а удаление второй вершины даёт гамильтонов путь) . Существуют гипогамильтоновы графы с n вершинами, в которых максимальная степень вершины равна n/2 и в которых примерно n2/4 рёбер[11].

 
Гипогамильтонов граф Томассена (1974) с обхватом 3.

Герц, Дуби и Виге высказали гипотезу[5], что любой гипогамильтонов граф имеет обхват 5 или более, но гипотеза была опровергнута Томассеном[12], нашедшим примеры с обхватом 3 и 4. Некоторое время не было известно, могут ли гипогамильтоновы графы быть планарными, но теперь известны некоторые примеры таких графов [13] и наименьший из этих графов имеет 40 вершин [14]. Любой планарный гипогамильтонов граф имеет по меньшей мере одну вершину только с тремя инцидентными рёбрами[15].

Если 3-однородный граф гамильтонов, его рёбра могут быть выкрашены в три цвета — используем поочерёдную раскраску рёбер двумя цветами вдоль гамильтонова цикла (который должен иметь чётную длину по лемме о рукопожатиях), а третьим цветом выкрашиваем все оставшиеся рёбра. Таким образом, все снарки, кубические графы без мостов, требующие четыре цвета для раскраски рёбер, должны быть негамильтоновы, и многие из известных снарков гипогамильтоновы. Любой гипокамильтонов снарк является бикритичным — удаление любых двух вершин оставляет подграф, рёбра которого можно выкрасить в три цвета[16][17]. Трёхцветную раскраску этого подграфа можно легко описать — после удаления вершины оставшаяся часть содержит гамильтонов цикл. После удаления второй вершины цикл становится путём, рёбра которого можно поочерёдно выкрасить двумя цветами. Оставшиеся рёбра образуют паросочетание и все эти рёбра можно выкрасить третьим цветом.

Классы цветов любой 3-цветной раскраски рёбер 3-однородного графа образуют три паросочетания, таких, что каждое ребро принадлежит ровно одному паросочетанию. Гипогамильтоновы снарки не имеют разложения на паросочетания такого типа, но Хеггквист[18] высказал гипотезу, что рёбра любого гипогамильтонова снарка могут быть использованы для образования шести паросочетаний, таких, что каждое ребро принадлежит ровно двум паросочетаниям. Это специальный случай гипотезы Бержа – Фулкерсона, что любой снарк имеет шесть паросочетаний с таким свойством.

Гипогамильтоновы графы не могут быть двудольными — в двудольном графе вершина может быть удaлена с образованием гамильтонова подграфа, только если она принадлежит к большему из двух классов цветов графа. Однако любой двудольный граф встречается в виде порождённого подграфа некоторого гипогамильтонова графа[19].

Примеры

править

Самый маленький гипогамильтонов граф — это граф Петерсена[5]. Более общо, обобщённый граф Петерсена GP(n,2) является гипогамильтоновым, если n равен 5 (mod 6) [20]. Граф Петерсена является представителем этого построения с n = 5.

Линдгрен[1] нашёл другой бесконечный класс гипогамильтоновых графов, в котором число вершин равно 4 (mod 6). Построение Линдгрена состоит из цикла длины 3 (mod 6) и одной центральной вершины. Центральная вершина соединена с каждой третьей вершиной цикла ребром, которое он называет спицей, а вершины на две позиции от конечной вершины спицы соединяются друг с другом. Снова наименьшим представителем построения Линдгрена является граф Петерсена.

Дополнительные бесконечные семейства дали Бонди[21], Дойен и ван Дист[22] и Гутт[23].

Перечисление

править

Вацлав Хватал в 1973 доказал, что для всех достаточно больших n существует гипогамильтонов с n вершинами. Если принять во внимание последовавшие открытия[24][22], «достаточно большое число» теперь известно, так что такие графы существуют для всех n ≥ 18. Полный список гипогамильтоновых графов с не более чем 17 вершинами известен [25] — это граф Петерсена с 10 вершинами, графы с 13 и 15 вершинами, найденные Герцем с помощью компьютерного поиска[26], и четыре графа с 16 вершинами. Существует по меньшей мере тринадцать гипогамильтоновых графов с 18 вершинами. При применении триггерного метода Хватала[27] к графу Петерсена и снарку «цветок», можно показать, что число гипогамильтоновых графов, конкретнее, число гипогамильтоновых снарков, растёт как экспонента от числа вершин[28][29].

Обобщения

править

Теоретики изучают также гиповычерчиваемые графы, графы, не содержащие гамильтонов путь, но в которых любое подмножество n − 1 вершин может быть соединено путём[30][31][32][24]. Аналогичные определения гипогамильтоновости и гиповычерчиваемости были предложены некоторыми авторами для ориентированных графов[33][34][35][15].

Эквивалентное определение гипогамильтоновых графов — что их самые длинные циклы имеют длину n − 1 и что пересечение всех самых длинных циклов пусто. Менке и Замфиреску[36] исследовали графы со свойством, что пересечение самых длинных циклов пусто, но в которых длина таких циклов меньше n − 1. Герц[26] определил циклируемость графа как наибольшее число k, такое, что любые k вершин принадлежат циклу. Гипогамильтоновы графы — это в точности графы, которые имеют циклируемость n − 1. Подобным образом Парк, Лим и Ким[10] определил граф как ƒ-устойчиво негамильтонов, если удаление самое большее ƒ вершин даёт гамильтонов подграф. Шауэрте и Замфиреску[37] изучали графы с циклируемостью n − 2.

Примечания

править
  1. ↑ 1 2 3 Lindgren, 1967.
  2. ↑ Sousselier, 1963.
  3. ↑ Gaudin, Herz, Rossi, 1964.
  4. ↑ Busacker, Saaty, 1965.
  5. ↑ 1 2 3 Herz, Duby, Vigué, 1967.
  6. ↑ 1 2 3 Grötschel, 1980.
  7. ↑ Grötschel, 1977.
  8. ↑ Grötschel, Wakabayashi, 1981.
  9. ↑ Goemans, 1995.
  10. ↑ 1 2 Park, Lim, Kim, 2007.
  11. ↑ Thomassen, 1981.
  12. ↑ Thomassen, 1974b.
  13. ↑ Задача о существовании планарных гипогамильтоновых графов была поставлена как открытый вопрос Вацлавом Хваталом (Chvátal 1973) и группа, в составе Хватала, Кларнера и Кнута, обещала приз в $5 нашедшему такой граф (Chvátal, Klarner, Knuth 1972). Томассен (Thomassen 1976) для поиска планарных гипогамильтоновых графов с обхватом 3, 4 и 5 использовал теорему Гринберга и показал, что существует бесконечно много планарных гипогамильтоновых графов.
  14. ↑ Нашли Джуйанде, МкКей, Ёстергард и Петтерссон (Jooyandeh, McKay, и др. 2013), для чего использовали компьютерный поиск и теорему Гринберга. До этого малые планарные гипогамильтоновы графы с 42, 57 и 48 вершинами были найдены Винером и Арайа (Wiener, Araya 2009), Хатцелем (Hatzel 1979) и Замфиреску (Zamfirescu, Zamfirescu 2007).
  15. ↑ 1 2 Thomassen, 1978.
  16. ↑ Steffen, 1998.
  17. ↑ Steffen, 2001.
  18. ↑ Häggkvist, 2007.
  19. ↑ Collier, Schmeichel, 1977.
  20. ↑ Робертсон (Robertson 1969) доказал, что эти графы негамильтоновы, хотя можно легко проверить, что удаление одной вершины даёт гамильтонов граф. См. статью Алспаха (Alspach 1983) по классификации негамильтоновых обобщённых графов Петерсена.
  21. ↑ Bondy, 1972.
  22. ↑ 1 2 Doyen, van Diest, 1975.
  23. ↑ Gutt, 1977.
  24. ↑ 1 2 Thomassen, 1974a.
  25. ↑ Aldred, McKay, Wormald, 1997. См. также последовательность A141150 в OEIS.
  26. ↑ 1 2 Herz, 1968.
  27. ↑ Chvátal, 1973.
  28. ↑ Skupień, 1989.
  29. ↑ Skupień, 2007.
  30. ↑ Kapoor, Kronk, Lick, 1968.
  31. ↑ Kronk, 1969.
  32. ↑ Grünbaum, 1974.
  33. ↑ Fouquet, Jolivet, 1978.
  34. ↑ Grötschel, Wakabayashi, 1980.
  35. ↑ Grötschel, Wakabayashi, 1984.
  36. ↑ Menke, Zamfirescu, Zamfirescu, 1998.
  37. ↑ Schauerte, Zamfirescu, 2006.

Литература

править
  • R. A. Aldred, B. D. McKay, N. C. Wormald. Small hypohamiltonian graphs // J. Combinatorial Math. Combinatorial Comput.. — 1997. — Т. 23. — С. 143–152.
  • B. R. Alspach. The classification of Hamiltonian generalized Petersen graphs // Journal of Combinatorial Theory, Series B. — 1983. — Т. 34, вып. 3. — С. 293–312. — doi:10.1016/0095-8956(83)90042-4.
  • J. A. Bondy. Variations of the Hamiltonian theme // Canadian Mathematical Bulletin. — 1972. — Т. 15. — С. 57–62. — doi:10.4153/CMB-1972-012-3.
  • R. G. Busacker, T. L. Saaty. Finite Graphs and Networks. — McGraw-Hill, 1965.
  • V. Chvátal. Flip-flops in hypo-Hamiltonian graphs // Canadian Mathematical Bulletin. — 1973. — Т. 16. — С. 33–41. — doi:10.4153/CMB-1973-008-9.
  • V. Chvátal, D. A. Klarner, D. E. Knuth. Selected Combinatorial Research Problems. — Computer Science Department, Stanford University, 1972. — (Tech. Report STAN-CS-72-292). (недоступная ссылка)
  • J. B. Collier, E. F. Schmeichel. New flip-flop constructions for hypohamiltonian graphs // Discrete Mathematics. — 1977. — Т. 18, вып. 3. — С. 265–271. — doi:10.1016/0012-365X(77)90130-3.
  • J. Doyen, V. van Diest. New families of hypohamiltonian graphs // Discrete Mathematics. — 1975. — Т. 13, вып. 3. — С. 225–236. — doi:10.1016/0012-365X(75)90020-5.
  • J.-L. Fouquet, J. L. Jolivet. Hypohamiltonian oriented graphs // Cahiers Centre Études Rech. Opér.. — 1978. — Т. 20, вып. 2. — С. 171–181.
  • T. Gaudin, P. Herz, Rossi. Solution du problème No. 29 // Rev. Franç. Rech. Opérationnelle. — 1964. — Т. 8. — С. 214–218.
  • Michel X. Goemans. Worst-case comparison of valid inequalities for the TSP // Mathematical Programming. — 1995. — Т. 69, вып. 1–3. — С. 335–349. — doi:10.1007/BF01585563.
  • M. Grötschel. Hypohamiltonian facets of the symmetric travelling salesman polytope // Zeitschrift für Angewandte Mathematik und Mechanik. — 1977. — Т. 58. — С. 469–471.
  • M. Grötschel. On the monotone symmetric traveling salesman problem: hypohamiltonian/hypotraceable graphs and facets // Mathematics of Operations Research. — 1980. — Т. 5, вып. 2. — С. 285–292. — doi:10.1287/moor.5.2.285. — JSTOR 3689157.
  • M. Grötschel, Y. Wakabayashi. Hypohamiltonian digraphs // Mathematics of Operations Research. — 1980. — Т. 36. — С. 99–119.
  • M. Grötschel, Y. Wakabayashi. On the structure of the monotone asymmetric travelling salesman polytope I: hypohamiltonian facets // Discrete Mathematics. — 1981. — Т. 24. — С. 43–59. — doi:10.1016/0012-365X(81)90021-2.
  • M. Grötschel, Y. Wakabayashi. Mathematical Programming (Proc. International Congress, Rio de Janeiro, 1981) / R. W. Cottle, M. L. Kelmanson, B. Korte. — North-Holland, 1984.
  • B. Grünbaum. Vertices missed by longest paths or circuits // Journal of Combinatorial Theory, Series A. — 1974. — Т. 17. — С. 31–38. — doi:10.1016/0097-3165(74)90025-9.
  • S. Gutt. Infinite families of hypohamiltonian graphs // Académie Royale de Belgique, Bulletin de la Classe des Sciences, Koninklijke Belgische Academie, Mededelingen van de Klasse der Wetenschappen, 5e Série. — 1977. — Т. 63, вып. 5. — С. 432–440.
  • R. Häggkvist. Research problems from the 5th Slovenian Conference (Bled, 2003) / B. Mohar, R. J. Nowakowski, D. B. West. — 2007. — Т. 307 (3–5). — С. 650–658. — (Discrete Mathematics). — doi:10.1016/j.disc.2006.07.013.
  • W. Hatzel. Ein planarer hypohamiltonscher Graph mit 57 Knoten // Math. Ann.. — 1979. — Т. 243, вып. 3. — С. 213–216. — doi:10.1007/BF01424541.
  • J. C. Herz. Computers in Mathematical Research. — North-Holland, 1968. — С. 97–107.
  • J. C. Herz, J. J. Duby, F. Vigué. Theory of Graphs: International Symposium, Rome 1966 / P. Rosenstiehl. — Paris: Gordon and Breach, 1967. — С. 153–159.
  • Mohammadreza Jooyandeh, Brendan D. McKay, Patric R. J. Östergård, Ville H. Pettersson, Carol T. Zamfirescu. Planar Hypohamiltonian Graphs on 40 Vertices. — 2013. — arXiv:1302.2698.
  • S. F. Kapoor, H. V. Kronk, D. R. Lick. On detours in graphs // Canadian Mathematical Bulletin. — 1968. — Т. 11. — С. 195–201. — doi:10.4153/CMB-1968-022-8.
  • H. V. Kronk. Does there exist a hypotraceable graph? // American Mathematical Monthly / V. Klee. — Mathematical Association of America, 1969. — Т. 76, вып. 7. — С. 809–810. — doi:10.2307/2317879. — JSTOR 2317879.
  • W. F. Lindgren. An infinite class of hypohamiltonian graphs // American Mathematical Monthly. — Mathematical Association of America, 1967. — Т. 74, вып. 9. — С. 1087–1089. — doi:10.2307/2313617. — JSTOR 2313617.
  • E. Máčajová, M. Škoviera. Constructing hypohamiltonian snarks with cyclic connectivity 5 and 6 // Electronic Journal of Combinatorics. — 2007. — Т. 14, вып. 1. — С. R14.
  • B. Menke, T. I. Zamfirescu, C. M. Zamfirescu. Intersections of longest cycles in grid graphs // Journal of Graph Theory. — 1998. — Т. 25, вып. 1. — С. 37–52. — doi:10.1002/(SICI)1097-0118(199705)25:1<37::AID-JGT2>3.0.CO;2-J.
  • S. P. Mohanty, D. Rao. Combinatorics and Graph Theory. — Springer-Verlag, 1981. — Т. 885. — С. 331–338. — (Lecture Notes in Mathematics). — doi:10.1007/BFb0092278.
  • J.-H. Park, H.-S. Lim, H.-C. Kim. Panconnectivity and pancyclicity of hypercube-like interconnection networks with faulty elements // Theoretical Computer Science. — 2007. — Т. 377, вып. 1–3. — С. 170–180. — doi:10.1016/j.tcs.2007.02.029.
  • G. N. Robertson. Graphs minimal under girth, valency and connectivity constraints. — Waterloo, Ontario: University of Waterloo, 1969. — (Ph. D. thesis).
  • Boris Schauerte, C. T. Zamfirescu. Regular graphs in which every pair of points is missed by some longest cycle // An. Univ. Craiova Ser. Mat. Inform.. — 2006. — Т. 33. — С. 154–173.
  • Z. Skupień. Graphs, Hypergraphs and Matroids III (Proc. Conf. Kalsk 1988). — Zielona Góra: Higher College of Engineering, 1989. — С. 123–132.. As cited by Skupień (2007)
  • Z. Skupień. 6th Czech-Slovak International Symposium on Combinatorics, Graph Theory, Algorithms and Applications. — 2007. — Т. 28. — С. 417–424. — (Electronic Notes in Discrete Mathematics). — doi:10.1016/j.endm.2007.01.059.
  • R. Sousselier. Problème no. 29: Le cercle des irascibles // Rev. Franç. Rech. Opérationnelle / C. Berge. — 1963. — Т. 7. — С. 405–406.
  • E. Steffen. Classification and characterizations of snarks // Discrete Mathematics. — 1998. — Т. 188, вып. 1–3. — С. 183–203. — doi:10.1016/S0012-365X(97)00255-0.
  • E. Steffen. On bicritical snarks // Math. Slovaca. — 2001. — Т. 51, вып. 2. — С. 141–150.
  • Carsten Thomassen. Hypohamiltonian and hypotraceable graphs // Discrete Mathematics. — 1974a. — Т. 9. — С. 91–96. — doi:10.1016/0012-365X(74)90074-0.
  • Carsten Thomassen. {{{заглавие}}} // Discrete Mathematics. — 1974b. — Т. 10, вып. 2. — С. 383–390. — doi:10.1016/0012-365X(74)90128-9.
  • Carsten Thomassen. Planar and infinite hypohamiltonian and hypotraceable graphs // Discrete Mathematics. — 1976. — Т. 14, вып. 4. — С. 377–389. — doi:10.1016/0012-365X(76)90071-6.
  • Carsten Thomassen. Theory and applications of graphs (Proc. Internat. Conf., Western Mich. Univ., Kalamazoo, Mich., 1976). — Berlin: Springer-Verlag, 1978. — Т. 642. — С. 557–571. — (Lecture Notes in Mathematics).
  • Carsten Thomassen. Planar cubic hypo-Hamiltonian and hypotraceable graphs // Journal of Combinatorial Theory, Series B. — 1981. — Т. 30. — С. 36–44. — doi:10.1016/0095-8956(81)90089-7.
  • Gábor Wiener, Makoto Araya. The ultimate question. — 2009. — arXiv:0904.3012.
  • C. T. Zamfirescu, T. I. Zamfirescu. A planar hypohamiltonian graph with 48 vertices // Journal of Graph Theory. — 2007. — Т. 55, вып. 4. — С. 338–342. — doi:10.1002/jgt.20241.

Ссылки

править
Источник — https://ru.wiki.x.io/w/index.php?title=Гипогамильтонов_граф&oldid=133770066