Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску
Не путать с гамильтоновым графом .
Гипогамильтонов граф, построенный Линдгреном (1967) .

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

История [ править ]

Гипогамильтоновы графы были впервые изучены Сусселье (1963) . Линдгрен (1967) цитирует Gaudin, Herz & Rossi (1964) и Busacker & Saaty (1965) как дополнительные ранние работы по этому вопросу; еще одна ранняя работа - Herz, Duby & Vigué (1967) .

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

Приложения [ править ]

Hypohamiltonian графики возникают в целочисленном программировании решений для задачи коммивояжера : некоторые виды hypohamiltonian графиков определяют грани на коммивояжер многогранника , форма определяются как выпуклая оболочка множества возможных решений задачи коммивояжера, и эти аспекты могут быть используется в плоскостных методах решения задачи. [1] Грёчель (1980) отмечает, что вычислительная сложностьопределения того, является ли граф гипогамильтоновым, хотя и неизвестно, вероятно, будет высоким, что затрудняет поиск граней этих типов, за исключением тех, которые определяются небольшими гипогамильтоновыми графами; к счастью, самые маленькие графы приводят к сильнейшим неравенствам для этого приложения. [2]

Основные понятия , тесно связанные с hypohamiltonicity также были использованы Парк, Lim & Kim (2007) для измерения отказоустойчивости в сетевых топологий для параллельных вычислений .

Свойства [ править ]

Каждый гипогамильтонов граф должен быть 3- вершинно-связным , так как удаление любых двух вершин оставляет гамильтонов путь, который связан. Там существуют п -vertex hypohamiltonian графы , в которых максимальная степень п / 2, и в котором существует около п 2 /4 ребра. [3]

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

Герц, Дуби и Виге (1967) предположили, что каждый гипогамильтонов граф имеет обхват 5 или более, но это было опровергнуто Томассеном (1974b) , который нашел примеры с обхватом 3 и 4. Некоторое время было неизвестно, может ли гипогамильтонов граф быть плоские , но сейчас известно несколько примеров [4], самый маленький из которых имеет 40 вершин. [5] Каждый плоский гипогамильтонов граф имеет хотя бы одну вершину с тремя инцидентными ребрами. [6]

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

Цветовые классы любой 3-раскраски ребер 3-регулярного графа образуют три паросочетания, причем каждое ребро принадлежит ровно одному из паросочетаний. Гипогамильтоновы снарки не имеют разбиения на сопоставления этого типа, но Хэггквист (2007) предполагает, что ребра любого гипогамильтонова снарка могут быть использованы для формирования шести сопоставлений, так что каждое ребро принадлежит ровно двум сопоставлениям. Это частный случай гипотезы Берге – Фулкерсона о том, что любой снарк имеет шесть паросочетаний с этим свойством.

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

Примеры [ править ]

Наименьшим гипогамильтоновым графом является граф Петерсена ( Herz, Duby & Vigué, 1967 ). В более общем смысле обобщенный граф Петерсена GP ( n , 2) является гипогамильтоновым, когда n равно 5 (mod 6); [9] граф Петерсена является примером этой конструкции с n  = 5.

Линдгрен (1967) нашел еще один бесконечный класс гипогамильтоновых графов с числом вершин 4 (mod 6). Конструкция Линдгрена состоит из цикла длины 3 (mod 6) и единственной центральной вершины; центральная вершина соединена с каждой третьей вершиной цикла ребрами, которые он называет спицами, а вершины на расстоянии двух позиций от каждой конечной точки спицы соединены друг с другом. Опять же, наименьшим примером конструкции Линдгрена является граф Петерсена.

Дополнительные бесконечные семейства приведены Бонди (1972) , Дойеном и ван Дистом (1975) и Гуттом (1977) .

Перечисление [ править ]

Вацлав Хваталь в 1973 году доказал, что для всех достаточно больших n существует гипогамильтонов граф с n вершинами. Принимая во внимание последующие открытия, [10] теперь известно, что «достаточно большой» означает, что такие графы существуют для всех n ≥ 18. Известен полный список гипогамильтоновых графов с не более чем 17 вершинами: [11] это 10- вершинный граф Петерсена, 13-вершинный граф и 15-вершинный граф, найденные компьютерным поиском Герца (1968) , и четыре 16-вершинных графа. Существует не менее тринадцати гипогамильтоновых графов с 18 вершинами. Применяя триггерный метод Хватала (1973) к графу Петерсена и цветочному снарку, можно показать, что количество гипогамильтоновых графов, а точнее, количество гипогамильтоновых снарков, растет как экспоненциальная функция от количества вершин. [12]

Обобщения [ править ]

Теоретики графов также изучали графы с возможностью отслеживания, графы , которые не содержат гамильтонова траектория, но такие, что каждое подмножество из n  - 1 вершин может быть соединено путем. [13] Аналогичные определения гипогамильтонности и возможности отслеживания для ориентированных графов рассматривались несколькими авторами. [14]

Эквивалентное определение гипогамильтоновых графов состоит в том, что их самый длинный цикл имеет длину n  - 1 и что пересечение всех самых длинных циклов пусто. Menke, Zamfirescu & Zamfirescu (1998) исследуют графы с тем же свойством, что пересечение самых длинных циклов пусто, но у которых самая длинная длина цикла короче n  - 1. Герц (1968) определяет циклируемость графа как наибольшее число. k такое, что все k вершин принадлежат циклу; гипогамильтоновы графы - это в точности графы, которые имеют циклируемость n  - 1. Точно так же Парк, Лим и Ким (2007) определяют граф как ƒ-гамильтониан неисправности, если удаление не более вершин оставляет гамильтонов подграф. Schauerte & Zamfirescu (2006) изучают графы с циклируемостью n  - 2.

Заметки [ править ]

  1. ^ Grötschel (1977) ; Грёчель (1980) ; Grötschel & Wakabayashi (1981) .
  2. ^ Goemans (1995) .
  3. ^ Thomassen (1981) .
  4. ^ Существование плоских гипогамильтоновых графов было поставлено как открытый вопрос Хваталем (1973) , и Хватал, Кларнер и Кнут (1972) предложили премию в 5 долларов за построение одного. Томассен (1976) использовал теорему Гринберга для нахождения плоских гипогамильтоновых графов с обхватом 3, 4 и 5 и показал, что существует бесконечно много плоских гипогамильтоновых графов.
  5. ^ Jooyandeh et al. (2013) , используя компьютерный поиск и теорему Гринберга. Ранее небольшие плоские гипогамильтоновы графы с 42, 57 и 48 вершинами соответственно были найдены Винером и Арайей ( 2009) , Хацелем (1979) и Замфиреску и Замфиреску (2007) .
  6. ^ Thomassen (1978) .
  7. ^ Штеффен (1998) ; Штеффен (2001) .
  8. ^ Кольер и Шмейхель (1977) .
  9. ^ Робертсон (1969) доказал, что эти графы негамильтоновы, в то время как несложно проверить, что их удаления с одной вершиной являются гамильтоновыми. См. Классификацию негамильтоновых обобщенных графов Петерсена в Alspach (1983) .
  10. ^ Thomassen (1974a) ; Дойен и ван Дист (1975) .
  11. ^ Aldred, Маккей и Wormald (1997) . См. Также (последовательность A141150 в OEIS ).
  12. ^ Скупень (1989) ; Скупень (2007) .
  13. ^ Капур, Кронк и Лик (1968) ; Кронк (1969) ; Грюнбаум (1974) ; Томассен (1974a) .
  14. ↑ Fouquet & Jolivet (1978) ; Grötschel & Wakabayashi (1980) ; Grötschel & Wakabayashi (1984) ; Томассен (1978) .

Ссылки [ править ]

  • Олдред, РА; McKay, BD ; Wormald, NC (1997), "Малые гипогамильтоновы графы" (PDF) , J. Combinatorial Math. Комбинаторные вычисления. , 23 : 143–152.
  • Alspach, BR (1983), "Классификация гамильтониана обобщен Петерсен графы", Журнал комбинаторной теории, серии B , 34 (3): 293-312, DOI : 10,1016 / 0095-8956 (83) 90042-4 , MR  0714452.
  • Бонди, JA (1972), "Вариации Гамильтона тему", Canadian математический вестник , 15 : 57-62, DOI : 10,4153 / CMB-1972-012-3.
  • Бусакер, Р.Г .; Саати, Т.Л. (1965), Конечные графы и сети , Макгроу-Хилл.
  • Chvátal, В. (1973), "флип-флоп в гих-гамильтоновы графах", Canadian математический вестник , 16 : 33-41, DOI : 10,4153 / CMB-1973-008-9 , MR  0371722.
  • Chvátal, V .; Кларнер, Д.А.; Кнут, Д.Е. (1972), Избранные комбинаторные исследовательские проблемы (PDF) , Tech. Отчет STAN-CS-72-292, факультет компьютерных наук, Стэнфордский университет.
  • Collier, JB; Шмейхель, EF (1977), "Новый флип-флоп конструкция для hypohamiltonian графов", Дискретная математика , 18 (3): 265-271, DOI : 10.1016 / 0012-365X (77) 90130-3 , MR  0543828.
  • Doyen, J .; Ван Дист В. (1975), "Новые семейства гипогамильтоновых графов", Дискретная математика , 13 (3): 225–236, DOI : 10.1016 / 0012-365X (75) 90020-5 , MR  0416979.
  • Fouquet, J.-L .; Jolivet, JL (1978), "Гипогамильтоновы ориентированные графы", Cahiers Centre Études Rech. Опера. , 20 (2): 171–181, MR  0498218.
  • Gaudin, T .; Herz, P .; Росси (1964), "Решение проблемы № 29", Rev. Franç. Речь. Операционнель , 8 : 214–218..
  • Goemans, Мишель Х. (1995), "наихудшего случая сравнение действительных неравенств для TSP", математического программирования , 69 (1-3): 335-349, CiteSeerX  10.1.1.52.8008 , DOI : 10.1007 / BF01585563.
  • Grötschel, M. (1977), "Гипогамильтоновы грани симметричного многогранника коммивояжера", Zeitschrift für Angewandte Mathematik und Mechanik , 58 : 469–471.
  • Grötschel, М. (1980), "О монотонности симметричной задаче коммивояжера: hypohamiltonian / hypotraceable графики и фасеты", математики исследования операций , 5 (2): 285-292, DOI : 10.1287 / moor.5.2.285 , JSTOR  3689157.
  • Grötschel, M .; Вакабаяси Ю. (1980), «Гипогамильтоновы орграфы», Методы исследования операций , 36 : 99–119, Zbl  0436.05038.
  • Grötschel, M .; Вакабаяси Ю. (1981), "О структуре монотонного асимметричного многогранника коммивояжера I: гипогамильтоновы грани", Дискретная математика , 24 : 43–59, DOI : 10.1016 / 0012-365X (81) 90021-2.
  • Grötschel, M .; Вакабаяси, Ю. (1984), "Конструкции предполагаемых орграфов", в Коттле, Род-Айленд; Кельмансон, ML; Корте, Б. (ред.), Математическое программирование (Протокол Международного конгресса, Рио-де-Жанейро, 1981) , Северная Голландия.
  • Грюнбаум, Б. (1974), «Вершины, пропущенные самыми длинными путями или схемами», Журнал комбинаторной теории, серия A , 17 : 31–38, DOI : 10.1016 / 0097-3165 (74) 90025-9 , MR  0349474.
  • Гутт, Симона (1977), «Бесконечные семейства гипогамильтоновых графов», Королевская академия Бельгии, Бюллетень классов наук , 5e Série, 63 (5): 432–440, MR  0498243.
  • Хэггквист, Р. (2007), Мохар, Б .; Новаковски, Р.Дж.; Запад, DB (ред.), "Проблема 443. Специального случай Фалкерсон гипотеза", Исследовательские проблемы с 5 - словенской конференцией (Блед, 2003), дискретной математики , 307 (3-5): 650-658, DOI : 10.1016 /j.disc.2006.07.013.
  • Hatzel, W. (1979), "Ein planarer hypohamiltonscher Graph mit 57 Knoten", Math. Анна. , 243 (3): 213-216, DOI : 10.1007 / BF01424541 , МР  0548801.
  • Герц, Дж. К. (1968), «Sur la cyclabilité des graphes», « Компьютеры в математических исследованиях» , Северная Голландия, стр. 97–107, MR  0245461.
  • Herz, JC; Дуби, JJ; Виге, Ф. (1967), "Recherche systématique des graphes hypohamiltoniens", в Rosenstiehl, P. (ed.), Theory of Graphs: International Symposium, Rome 1966 , Paris: Gordon and Breach, pp. 153–159.
  • Джуйандех, Мохаммадреза; Маккей, Брендан Д .; Эстергард, Патрик Р.Дж.; Pettersson, Ville H .; Замфиреску, Кэрол Т. (2013), Плоские гипогамильтоновы графы на 40 вершинах , arXiv : 1302.2698 , Bibcode : 2013arXiv1302.2698J.
  • Капур, Сан-Франциско; Кронк, HV; Лик, DR (1968), "О обходов в графах", Canadian математический вестник , 11 (2): 195-201, DOI : 10,4153 / CMB-1968-022-8 , MR  0229543.
  • Кронк, HV (1969), Клей, В. (ред . ), "Существует ли hypotraceable графа?", Проблемы исследования, American Mathematical Monthly , 76 (7): 809-810, DOI : 10,2307 / 2317879 , JSTOR  2317879.
  • Линдгрен, У. Ф. (1967), «Бесконечный класс гипогамильтоновых графов», American Mathematical Monthly , 74 (9): 1087–1089, DOI : 10.2307 / 2313617 , JSTOR  2313617 , MR  0224501.
  • Máčajová, E .; Шковьера, М. (2007), «Построение гипогамильтоновых снарков с циклической связностью 5 и 6» , Электронный журнал комбинаторики , 14 (1): R14.
  • Menke, B .; Замфиреску, Т.И.; Замфиреску, CM (1998), «Пересечения самых длинных циклов в сеточных графах», 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.
  • Моханти, ИП; Рао, Д. (1981), "Семейство гого-гамильтоновые обобщенные призм", Комбинаторика и теория графов , Lecture Notes в математике, 885 , Springer-Verlag, стр 331-338,. DOI : 10.1007 / BFb0092278 , ISBN 978-3-540-11151-1.
  • Park, J.-H .; Lim, H.-S .; Ким, Х.-К. (2007), «Пан-связность и панцикличность гиперкубоподобных сетей межсоединений с неисправными элементами», Теоретическая информатика , 377 (1–3): 170–180, DOI : 10.1016 / j.tcs.2007.02.029.
  • Робертсон, Г. Н. (1969), Графики минимального нижнего обхвата, валентности и ограничений связности , докторская диссертация, Ватерлоо, Онтарио: Университет Ватерлоо.
  • Шауэрте, Борис; Замфиреску, CT (2006), «Регулярные графы, в которых каждая пара точек пропускается некоторым самым длинным циклом», An. Univ. Craiova Ser. Мат. Сообщить. , 33 : 154-173, ЛВП : 1854 / LU-6901462 , МР  2359901.
  • Скупень, З. (1989), "Экспоненциально много гипогамильтоновых графов", Графы, гиперграфы и матроиды III (Proc. Conf. Kalsk 1988) , Зелена-Гура: Высший инженерный колледж, стр. 123–132. Цитируется по Skupień (2007) .
  • Скупень, З. (2007), «Экспоненциально много гипогамильтоновых снарков», 6-й Чешско-Словацкий международный симпозиум по комбинаторике, теории графов, алгоритмам и приложениям , Электронные заметки по дискретной математике, 28 , стр. 417–424, doi : 10.1016 / j .endm.2007.01.059.
  • Sousselier, R. (1963), Berge, C. (ed.), "Problème № 29: Le cercle des irascibles", Problèmes plaisants et délectables, Rev. Franç. Речь. Операционнель , 7 : 405–406.
  • Штеффно, Е. (1998), "Классификация и характеризация snarks", дискретная математика , 188 (1-3): 183-203, DOI : 10.1016 / S0012-365X (97) 00255-0 , МР  1630478.
  • Штеффен, E. (2001), "О бикритических снарках", Math. Словака , 51 (2): 141–150, MR  1841443.
  • Томассен, Карстен (1974a), «Гипогамильтоновы и гипотетические графы», Дискретная математика , 9 : 91–96, DOI : 10.1016 / 0012-365X (74) 90074-0 , MR  0347682.
  • Томасен, Карстен (1974b), "О hypohamiltonian графов", дискретная математика , 10 (2): 383-390, DOI : 10.1016 / 0012-365X (74) 90128-9 , МР  0357226.
  • Томасно, Карстен (1976), "плоскостной и бесконечное hypohamiltonian и hypotraceable графики", дискретная математика , 14 (4): 377-389, DOI : 10.1016 / 0012-365X (76) 90071-6 , МР  0422086.
  • Томассен, Карстен (1978), "Гипогамильтоновы графы и орграфы", Теория и приложения графов (Proc. Internat. Conf., Western Mich. Univ., Kalamazoo, Mich., 1976) , Lecture Notes in Mathematics, 642 , Berlin: Springer-Verlag, стр. 557–571, MR  0499523.
  • Томассен, Карстен (1981), «Плоские кубические гипогамильтоновы графы и отслеживаемые гипотезы», Журнал комбинаторной теории, серия B , 30 : 36–44, DOI : 10.1016 / 0095-8956 (81) 90089-7 , MR  0609592.
  • Винер, Габор; Арая, Макото (2009), Последний вопрос , arXiv : 0904.3012 , Bibcode : 2009arXiv0904.3012W.
  • Замфиреску, Коннектикут; Замфиреска, Т. (2007), "Плоский hypohamiltonian граф с 48 вершинами", Журнал теории графов , 55 (4): 338-342, DOI : 10.1002 / jgt.20241.

Внешние ссылки [ править ]

  • Вайсштейн, Эрик В. , «Гипогамильтонов граф» , MathWorld