Характеристика запрещенного графа - Forbidden graph characterization

«Запрещенные несовершеннолетние» перенаправляются сюда. Запрещенные несовершеннолетние также могут обращаться к возрастные ограничения.

В теория графов, раздел математики, многие важные семейства графов можно описать конечным набором отдельных графов, которые не принадлежат к семейству, и дополнительно исключить все графы из семейства, которые содержат любой из этих запрещенных графов как (индуцированный) подграф или второстепенный. Типичным примером этого явления является Теорема Куратовского, который утверждает, что граф планарный (может быть нарисован без пересечений на плоскости) тогда и только тогда, когда он не содержит ни одного из двух запрещенных графов, полный график K5 и полный двудольный граф K3,3. Для теоремы Куратовского понятие включения - это понятие гомеоморфизм графа, в котором подразделение одного графа появляется как подграф другого. Таким образом, каждый граф либо имеет планарный рисунок (в этом случае он принадлежит к семейству плоских графов), либо он имеет подразделение одного из этих двух графов в качестве подграфа (в этом случае он не принадлежит к планарным графам).

Определение

В более общем плане характеристика запрещенного графа это метод указание семья график, или же гиперграф, структуры, указав подструктуры, существование которых запрещено в любом графе семейства. Различные семьи различаются по характеру того, что запрещенный. В общем, структура грамм является членом семьи если и только если запрещенная подструктура нет содержалась в грамм. В запрещенная подструктура может быть одним из:

  • подграфы, меньшие графы, полученные из подмножеств вершин и ребер большего графа,
  • индуцированные подграфы, меньшие графы, полученные путем выбора подмножества вершин и использования всех ребер с обеими конечными точками в этом подмножестве,
  • гомеоморфный подграфы (также называемые топологические миноры ), меньшие графы, полученные из подграфов путем сворачивания путей с вершинами степени два в одиночные ребра, или
  • граф миноры, меньшие графы, полученные из подграфов произвольным краевые сокращения.

Множество структур, которым запрещено принадлежать к данному семейству графов, также можно назвать набор препятствий для этой семьи.

Запрещенные характеристики графов могут использоваться в алгоритмы для проверки принадлежности графа к данному семейству. Во многих случаях можно провести тестирование в полиномиальное время содержит ли данный граф какие-либо элементы множества препятствий и, следовательно, принадлежит ли он семейству, определенному этим множеством препятствий.

Для того, чтобы семейство имело характеристику запрещенного графа с определенным типом подструктуры, семейство должно быть замкнуто относительно подструктур, то есть каждая подструктура (данного типа) графа в семействе должна быть другим графом в семья. Точно так же, если граф не является частью семейства, все более крупные графы, содержащие его в качестве подструктуры, также должны быть исключены из семейства. Если это так, всегда существует набор препятствий (набор графов, которые не входят в семейство, но все меньшие подструктуры которых принадлежат этому семейству). Однако для некоторых представлений о том, что такое подструктура, этот набор препятствий может быть бесконечным. В Теорема Робертсона – Сеймура доказывает, что для частного случая граф миноры, замкнутое относительно миноров семейство всегда имеет конечное множество препятствий.

Список запрещенных характеризаций для графов и гиперграфов

Этот список неполный; вы можете помочь добавление недостающих предметов с надежные источники.
СемьяПрепятствияСвязьСсылка
Лесапетли, пары параллельных краев и циклы любой длиныподграфОпределение
петля (для мультиграфов) или треугольник K3 (для простых графиков)граф минорОпределение
Графы без когтейзвезда K1,3индуцированный подграфОпределение
Графики сопоставимостииндуцированный подграф
Графы без треугольниковтреугольник K3индуцированный подграфОпределение
Планарные графикиK5 и K3,3гомеоморфный подграфТеорема Куратовского
K5 и K3,3граф минорТеорема Вагнера
Внешнепланарные графыK4 и K2,3граф минорДистель (2000),[1] п. 107
Внешние 1-плоские графышесть запрещенных несовершеннолетнихграф минорAuer et al. (2013)[2]
Графики фиксированных родконечное множество препятствийграф минорДистель (2000),[1] п. 275
Графики вершиныконечное множество препятствийграф минор[3]
Бесконечные встраиваемые графикиВ Семья Петерсенграф минор[4]
Двудольные графынечетные циклыподграф[5]
Хордовые графыциклы длиной 4 и болееиндуцированный подграф[6]
Совершенные графикициклов нечетной длины 5 и более или их дополняетиндуцированный подграф[7]
Линейный график графиковдевять запрещенных подграфов (перечислены Вот )индуцированный подграф[8]
Графические союзы из кактус графикичетырехвершинник ромбовидный график формируется путем удаления края из полный график K4граф минор[9]
Лестничные графикиK2,3 и это двойственный графгомеоморфный подграф[10]
Разделить графикииндуцированный подграф[11]
2-связный последовательно-параллельный (ширина дерева ≤ 2, ширина ветки ≤ 2)K4граф минорДистель (2000),[1] п. 327
Ширина дерева ≤ 3K5, октаэдр, пятиугольная призма, График Вагнераграф минор[12]
Ширина ветки ≤ 3K5, октаэдр, куб, График Вагнераграф минор[13]
Дополняемо-приводимые графы (кографы)4-вершинный путь п4индуцированный подграф[14]
Тривиально совершенные графы4-вершинный путь п4 и 4-вершинный цикл C4индуцированный подграф[15]
Графики пороговых значений4-вершинный путь п4, 4-вершинный цикл C4, и дополнение C4индуцированный подграф[15]
Линейный график 3-однородных линейных гиперграфовконечный список запрещенных индуцированных подграфов минимальной степени не менее 19индуцированный подграф[16]
Линейный график k-однородные линейные гиперграфы, k > 3конечный список запрещенных индуцированных подграфов с минимальной степенью ребра не менее 2k2 − 3k + 1индуцированный подграф[17][18]
Графики ΔY-приводимая в одну вершинуконечный список не менее 68 миллиардов различных (1,2,3) -кликовых суммграф минор[19]
Общие теоремы
Семья, определенная индуцированно-наследственное свойствомножество препятствий, возможно, не конечноеиндуцированный подграф
Семья, определяемая несовершеннолетняя наследственная собственностьконечное множество препятствийграф минорТеорема Робертсона – Сеймура

Смотрите также

Рекомендации

  1. ^ а б c Дистель, Рейнхард (2000), Теория графов, Тексты для выпускников по математике, 173, Springer-Verlag, ISBN  0-387-98976-5.
  2. ^ Ауэр, Кристофер; Бахмайер, Кристиан; Бранденбург, Франц Дж .; Глайсснер, Андреас; Ханауэр, Катрин; Нойвирт, Даниэль; Рейсльхубер, Йозеф (2013), «Распознавание внешних 1-плоских графов за линейное время», в Wismath, Stephen; Вольф, Александр (ред.), 21-й Международный симпозиум, GD 2013, Бордо, Франция, 23-25 ​​сентября 2013 г., Отредактированные избранные доклады, Конспект лекций по информатике, 8242, стр. 107–118, Дои:10.1007/978-3-319-03841-4_10.
  3. ^ Gupta, A .; Импальяццо, Р. (1991), «Вычислительные планарные сплетения», Proc. 32-й симпозиум IEEE по основам компьютерных наук (FOCS '91), IEEE Computer Society, стр. 802–811, Дои:10.1109 / SFCS.1991.185452.
  4. ^ Робертсон, Нил; Сеймур, П.Д.; Томас, Робин (1993), "Бесконечные вложения графов в 3-пространство", Бюллетень Американского математического общества, 28 (1): 84–89, arXiv:математика / 9301216, Дои:10.1090 / S0273-0979-1993-00335-5, МИСТЕР  1164063.
  5. ^ Béla Bollobás (1998) "Современная теория графов", Springer, ISBN  0-387-98488-7 п. 9
  6. ^ Кашивабара, Тошинобу (1981), «Алгоритмы для некоторых графов пересечений», Сайто, Нобуджи; Нисизэки, Такао (ред.), Теория графов и алгоритмы, 17-й симпозиум Исследовательского института электросвязи, Университет Тохоку, Сендай, Япония, 24-25 октября 1980 г., Труды, Конспект лекций по информатике, 108, Springer-Verlag, стр. 171–181, Дои:10.1007/3-540-10704-5\_15.
  7. ^ Чудновский, Мария; Робертсон, Нил; Сеймур, Пол; Томас, Робин (2006), «Сильная теорема о совершенном графе» (PDF), Анналы математики, 164 (1): 51–229, arXiv:математика / 0212070v1, Дои:10.4007 / анналы.2006.164.51.
  8. ^ Beineke, L. W. (1968), "Производные графы орграфов", в Sachs, H .; Voss, H.-J .; Уолтер, Х.-Дж. (ред.), Beiträge zur Graphentheorie, Лейпциг: Teubner, стр. 17–33..
  9. ^ Эль-Маллах, Эхаб; Колборн, Чарльз Дж. (1988), "Сложность некоторых задач удаления ребер", Транзакции IEEE в схемах и системах, 35 (3): 354–362, Дои:10.1109/31.1748.
  10. ^ Takamizawa, K .; Нисизэки, Такао; Сайто, Нобуджи (1981), "Комбинаторные задачи на последовательно-параллельных графах", Дискретная прикладная математика, 3 (1): 75–76, Дои:10.1016 / 0166-218X (81) 90031-7.
  11. ^ Фёльдес, Стефан; Хаммер, Питер Лэдислав (1977a), «Расщепленные графы», Труды восьмой Юго-Восточной конференции по комбинаторике, теории графов и вычислениям (Университет штата Луизиана, Батон-Руж, штат Луизиана, 1977 г.), Congressus Numerantium, XIX, Виннипег: Utilitas Math., Стр. 311–315, МИСТЕР  0505860
  12. ^ Бодландер, Ханс Л. (1998), "Частичный k-арборетум графов с ограниченной шириной дерева », Теоретическая информатика, 209 (1–2): 1–45, Дои:10.1016 / S0304-3975 (97) 00228-4.
  13. ^ Бодландер, Ханс Л.; Тиликос, Димитриос М. (1999), "Графы с шириной ветвления не более трех", Журнал алгоритмов, 32 (2): 167–194, Дои:10.1006 / jagm.1999.1011.
  14. ^ Seinsche, D. (1974), "Об одном свойстве класса п-раскрашиваемые графики », Журнал комбинаторной теории, серия B, 16 (2): 191–193, Дои:10.1016 / 0095-8956 (74) 90063-Х, МИСТЕР  0337679
  15. ^ а б Голумбик, Мартин Чарльз (1978), "Тривиально совершенные графы", Дискретная математика, 24 (1): 105–107, Дои:10.1016 / 0012-365X (78) 90178-4..
  16. ^ Метельский, Юрий; Тышкевич Регина (1997), "О линейных графах линейных 3-однородных гиперграфов", Журнал теории графов, 25 (4): 243–251, Дои:10.1002 / (SICI) 1097-0118 (199708) 25: 4 <243 :: AID-JGT1> 3.0.CO; 2-K, МИСТЕР  1459889
  17. ^ Jacobson, M. S .; Kézdy, Андре Э .; Лехел, Джено (1997), "Распознавание графов пересечений линейных однородных гиперграфов", Графы и комбинаторика, 13: 359–367, Дои:10.1007 / BF03353014, МИСТЕР  1485929
  18. ^ Naik, Ranjan N .; Rao, S. B .; Шриханде, С.С.; Сингхи, Н. М. (1982), "Графы пересечений k-однородные гиперграфы », Европейский журнал комбинаторики, 3: 159–172, Дои:10.1016 / s0195-6698 (82) 80029-2, МИСТЕР  0670849
  19. ^ Ю, Янмин (2006), "Больше запрещенных второстепенных для сводимости Уай-Дельта-Уай", Электронный журнал комбинаторики, 13 Интернет сайт