Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску

В теории графов , особенно в теории гиперграфов , линейный граф гиперграфа H , обозначаемый L ( H ), - это граф , множество вершин которого является множеством гиперребер H с двумя смежными вершинами в L ( H ), когда соответствующие им гиперребра имеет непустое пересечение в H . Другими словами, L ( H ) - граф пересечений семейства конечных множеств. Это обобщение линейного графика графа.

Вопросы о линейных графах гиперграфов часто являются обобщением вопросов о линейных графах графов. Например, гиперграф, все ребра которого имеют размер k , называется k- однородным . (2-равномерный гиперграф - это граф). В теории гиперграфов часто естественно требовать, чтобы гиперграфы были k- однородными. Каждый граф является линейным графом некоторого гиперграфа, но, учитывая фиксированный размер ребра k , не каждый граф является линейным графом некоторого k -равномерного гиперграфа. Основная проблема состоит в том, чтобы охарактеризовать те, которые есть для каждого k ≥ 3.

Гиперграф называется линейным, если каждая пара гиперребер пересекается не более чем в одной вершине. Каждый граф является линейным графом не только некоторого гиперграфа, но и некоторого линейного гиперграфа ( Berge 1989 ).

Линейные графики k -однородных гиперграфов, k ≥ 3 [ править ]

Бейнеке (1968) охарактеризовал линейные графы графов списком из 9 запрещенных индуцированных подграфов . (См. Статью о линейных графах .) Никакая характеризация запрещенными индуцированными подграфами не известна для линейных графов k-однородных гиперграфов для любого k ≥ 3, и Ловас (1977) показал, что такой характеризации конечным списком не существует, если k = 3 .

Краус (1943) охарактеризовал линейные графы графов в терминах кликовых покрытий. (См. Линейные графики .) Глобальная характеристика типа Крауса для линейных графов k -однородных гиперграфов для любого k ≥ 3 была дана Берге (1989) .

Линейные графики k -однородных линейных гиперграфов, k ≥ 3 [ править ]

Глобальная характеристика типа Крауца для линейных графов k -однородных линейных гиперграфов для любого k ≥ 3 была дана Naik et al. (1980) . В то же время они нашли конечный список запрещенных индуцированных подграфов для линейных 3-однородных гиперграфов с минимальной степенью вершины не менее 69. Metelsky & Tyshkevich (1997) и Jacobson, Kézdy & Lehel (1997) улучшили эту оценку до 19. At последний Skums, Suzdal & Tyshkevich (2005) уменьшил эту оценку до 16. Metelsky & Tyshkevich (1997) также доказали, что если k > 3, такой конечный список не существует для линейного k.-однородные гиперграфы, независимо от того, какая нижняя граница ставится на степень.

Трудность нахождения характеризации линейных k -однородных гиперграфов связана с тем, что существует бесконечно много запрещенных индуцированных подграфов. В качестве примеров для m > 0 рассмотрим цепочку из m ромбовидных графов , в которой последовательные ромбы имеют общие вершины степени два. Для k ≥ 3 добавьте висячие ребра в каждой вершине степени 2 или 4, чтобы получить одно из семейств минимальных запрещенных подграфов Найка, Рао и Шрикханде и др. ( 1980 , 1982 ), как показано здесь. Это не исключает ни существования полиномиального распознавания, ни возможности запрещенной индуцированной характеризации подграфа, аналогичной характеристике Бейнеке линейных графов графов.

Повторяющийся ромбовидный graph.svg

Есть некоторые интересные характеристики, доступные для линейных графов линейных k- однородных гиперграфов, принадлежащие различным авторам (Naik, Rao & Shrikhande et al.  1980 , 1982 , Jacobson, Kézdy & Lehel 1997 , Metelsky & Tyshkevich 1997 и Zverovich 2004 ) при ограничениях на минимальной степени или минимальной степени кромки G. Минимальная степень кромки не менее k 3 -2 k 2 +1 в Naik et al. (1980) сокращено до 2 k 2 -3 k +1 в Jacobson, Kézdy & Lehel (1997) и Zverovich (2004).охарактеризовать линейные графы k -однородных линейных гиперграфов для любого k ≥ 3.

Сложность распознавания линейных графов линейных k -однородных гиперграфов без каких-либо ограничений на минимальную степень (или минимальную степень ребра) неизвестна. Для k = 3 и минимальной степени не менее 19 распознавание возможно за полиномиальное время ( Jacobson, Kézdy & Lehel 1997 и Metelsky & Tyshkevich 1997 ). Скумс, Суздаль и Тышкевич (2005) снизили минимальную степень до 10.

Есть много интересных открытых проблем и предположений в Naik et al., Jacoboson et al., Metelsky et al. и Зверович.

График дизъюнктности [ править ]

Дизъюнктность график гиперграфа H , обозначается D ( Н ), является графиком, множество вершин которого является множество гиперребер из Н , с двумя соседними вершинами в D ( H ) , когда соответствующие им Гиперребра пересекаются в H . [1] Другими словами, D ( H ) - дополнительный граф к L ( H ). Клика в D ( H ) соответствует независимому множеству в L ( H ), и наоборот.

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

  1. ^ Мешулам, Рой (2001-01-01). «Кликовый комплекс и соответствие гиперграфа». Combinatorica . 21 (1): 89–94. DOI : 10.1007 / s004930170006 . ISSN  1439-6912 . S2CID  207006642 .
  • Beineke, LW (1968), «О производных графах и орграфах», в Sachs, H .; Voss, H .; Вальтер, Х. (ред.), Beitrage zur Graphentheorie , Leipzig: Teubner, pp. 17–23.
  • Берге, К. (1989), Гиперграфы: комбинаторика конечных множеств , Амстердам: Северная Голландия, MR  1013569 CS1 maint: обескураженный параметр ( ссылка ). Перевод с французского.
  • Bermond, JC; Heydemann, MC; Sotteau, D. (1977), "Линейные графики гиперграфах I" (PDF) , дискретная математика , 18 (3): 235-241, DOI : 10.1016 / 0012-365X (77) 90127-3 , MR  0463003.
  • Heydemann, MC; Сотто, Д. (1976), "Линейные графы гиперграфов II", Комбинаторика (Proc. Fifth Hungarian Colloq., Keszthely, 1976) , Colloq. Математика. Soc. J. Bolyai, 18 , стр. 567–582, MR  0519291.
  • Краус, J. (1943), "Демонстрация новой теории Уитни сюр ле réseaux", Матем. Физ. Лапок , 50 : 75–85, MR  0018403. (На венгерском, с французским аннотацией.)
  • Ловас, Л. (1977), «Проблема 9», Beiträge zur Graphentheorie und deren Anwendungen , Vorgetragen auf dem Internationalen Kolloquium в Оберхофе (ГДР), стр. 313 CS1 maint: обескураженный параметр ( ссылка ).
  • Jacobson, MS; Kézdy, Андре Э .; Леэль, Йено (1997), "Распознавание пересечения графиков линейных однородных гиперграфов", графов и комбинаторика , 13 (4): 359-367, DOI : 10.1007 / BF03353014 , МР  1485929 , S2CID  9173731.
  • Метельский, Юрий; Тышкевич, Регина (1997), "Линейные графы линейных 3-однородных гиперграфов", Журнал теории графов , 25 (4): 243–251, DOI : 10.1002 / (SICI) 1097-0118 (199708) 25: 4 < 243 :: AID-JGT1> 3.0.CO; 2-K , MR  1459889.
  • Naik, Ranjan N .; Рао, SB; Шриханде, СС ; Сингхи, Н.М. (1980), "Графы пересечений k -однородных гиперграфов", комбинаторная математика, оптимальные планы и их приложения (Proc. Sympos. Combin. Math. And Optimal Design, Colorado State Univ., Fort Collins, Colo., 1978 ) , Анналы дискретной математики, 6 , стр. 275–279, MR  0593539 CS1 maint: обескураженный параметр ( ссылка ).
  • Naik, Ranjan N .; Рао, SB; Шриханде, СС ; Singhi, NM (1982), "Пересечение графы к -равномерному линейным гиперграфам", Европейский журнал комбинаторика , 3 (2): 159-172, DOI : 10.1016 / s0195-6698 (82) 80029-2 , MR  0670849 CS1 maint: обескураженный параметр ( ссылка ).
  • Скумы, ПВ; Суздаль, СВ; Тышкевич, Р. (2009), "Край пересечение линейного 3-равномерных гиперграфов", дискретная математика , 309 : 3500-3517, DOI : 10.1016 / j.disc.2007.12.082.
  • Зверович, Игорь Е. (2004), "Решение задачи Jacobson, Kézdy и Lehel", графов и комбинаторика , 20 (4): 571-577, DOI : 10.1007 / s00373-004-0572-1 , МР  2108401 , S2CID  33662052.
  • Волошин, Виталий И. (2009), Введение в теорию графов и гиперграфов , Нью-Йорк: Nova Science Publishers, Inc. , MR  2514872