В теории графов, разделе математики, многие важные семейства графов могут быть описаны конечным набором отдельных графов, которые не принадлежат к семейству, и дополнительно исключить все графы из семейства, которые содержат любой из этих запрещенных графов как (индуцированные) подграф или второстепенный. Прототипным примером этого явления является теорема Куратовского , которая утверждает, что граф является плоским (может быть нарисован без пересечений на плоскости) тогда и только тогда, когда он не содержит ни одного из двух запрещенных графов, полного графа K 5 и полного двудольного графа. граф K 3,3 . Для теоремы Куратовского понятие включения - это понятие гомеоморфизма графов., в котором подразделение одного графа появляется как подграф другого. Таким образом, каждый граф либо имеет планарный рисунок (в этом случае он принадлежит к семейству плоских графов), либо имеет подразделение одного из этих двух графов в качестве подграфа (в этом случае он не принадлежит к планарным графам).
Определение [ править ]
В более общем смысле, характеристика запрещенного графа - это метод определения семейства структур графа или гиперграфа путем определения подструктур, существование которых запрещено в любом графе в семействе. Разные семьи различаются по характеру того, что запрещено . В общем, структура G является членом семейства тогда и только тогда , когда запрещенная субструктура не содержится в G . Запрещено подструктура может быть один из:
- подграфы , меньшие графы, полученные из подмножеств вершин и ребер большего графа,
- индуцированные подграфы , меньшие графы, полученные путем выбора подмножества вершин и использования всех ребер с обеими конечными точками в этом подмножестве,
- гомеоморфные подграфы (также называемые топологическими минорами ), меньшие графы, полученные из подграфов путем сворачивания путей из вершин степени два в отдельные ребра, или
- миноры графов , меньшие графы, полученные из подграфов произвольным сжатием ребер .
Множество структур, которым запрещено принадлежать к данному семейству графов, также можно назвать множеством препятствий для этого семейства.
Запрещенные характеристики графов могут использоваться в алгоритмах для проверки принадлежности графа к данному семейству. Во многих случаях можно проверить за полиномиальное время , содержит ли данный граф какие-либо элементы набора препятствий и, следовательно, принадлежит ли он семейству, определенному этим множеством препятствий.
Чтобы семейство имело характеристику запрещенного графа с определенным типом подструктуры, семейство должно быть замкнуто под подструктурами. То есть каждая подструктура (данного типа) графа в семействе должна быть другим графом в семействе. Точно так же, если граф не является частью семейства, все более крупные графы, содержащие его в качестве подструктуры, также должны быть исключены из семейства. Когда это так, всегда существует набор препятствий (набор графов, которые не входят в семейство, но все меньшие подструктуры которых принадлежат этому семейству). Однако для некоторых представлений о том, что такое подструктура, этот набор препятствий может быть бесконечным. Теорема Робертсона – Сеймура доказывает, что для частного случая миноров графа, замкнутое относительно миноров семейство всегда имеет конечное множество препятствий.
Список запрещенных характеристик для графов и гиперграфов [ править ]
| Семья | Препятствия | Связь | Справка |
|---|---|---|---|
| Леса | петли, пары параллельных ребер и циклы любой длины | подграф | Определение |
| петля (для мультиграфов) или треугольник K 3 (для простых графов) | граф минор | Определение | |
| Графы без когтей | звезда К 1,3 | индуцированный подграф | Определение |
| Графики сопоставимости | индуцированный подграф | ||
| Графы без треугольников | треугольник К 3 | индуцированный подграф | Определение |
| Планарные графики | К 5 и К 3,3 | гомеоморфный подграф | Теорема Куратовского |
| К 5 и К 3,3 | граф минор | Теорема Вагнера | |
| Внешнепланарные графы | К 4 и К 2,3 | граф минор | Дистель (2000) , [1] стр. 107 |
| Внешние 1-плоские графы | шесть запрещенных несовершеннолетних | граф минор | Auer et al. (2013) [2] |
| Графики фиксированного рода | конечное множество препятствий | граф минор | Дистель (2000) , [1] стр. 275 |
| Графики вершины | конечное множество препятствий | граф минор | [3] |
| Бесконечные встраиваемые графики | Семья Петерсен | граф минор | [4] |
| Двудольные графы | нечетные циклы | подграф | [5] |
| Хордовые графы | циклы длиной 4 и более | индуцированный подграф | [6] |
| Совершенные графики | циклы нечетной длины 5 и более или их дополнения | индуцированный подграф | [7] |
| Линейный график графиков | девять запрещенных подграфов (перечислены здесь ) | индуцированный подграф | [8] |
| График объединение из кактуса графиков | ромбовидный граф с четырьмя вершинами, образованный удалением ребра из полного графа K 4 | граф минор | [9] |
| Лестничные графики | K 2,3 и его двойственный граф | гомеоморфный подграф | [10] |
| Разделить графики | индуцированный подграф | [11] | |
| 2-подключенные последовательно-параллельные ( ширина дерева ≤ 2, ширина ответвления ≤ 2) | К 4 | граф минор | Дистель (2000) , [1] стр. 327 |
| Ширина дерева ≤ 3 | K 5 , октаэдр , пятиугольная призма , граф Вагнера | граф минор | [12] |
| Ширина ответвления ≤ 3 | K 5 , октаэдр , куб , граф Вагнера | граф минор | [13] |
| Дополняемо-приводимые графы (кографы) | 4-вершинный путь P 4 | индуцированный подграф | [14] |
| Тривиально совершенные графы | 4-вершинный путь P 4 и 4-вершинный цикл C 4 | индуцированный подграф | [15] |
| Графики пороговых значений | 4-вершинный путь P 4 , 4-вершинный цикл C 4 и дополнение к C 4 | индуцированный подграф | [15] |
| Линейный график 3-однородных линейных гиперграфов | конечный список запрещенных индуцированных подграфов минимальной степени не менее 19 | индуцированный подграф | [16] |
| Линейный график k -однородных линейных гиперграфов, k > 3 | конечный список запрещенных индуцированных подграфов с минимальной степенью ребра не менее 2 k 2 - 3 k + 1 | индуцированный подграф | [17] [18] |
| Графы ΔY-сводимые к одной вершине | конечный список не менее 68 миллиардов различных (1,2,3) -кликовых сумм | граф минор | [19] |
| Общие теоремы | |||
| Семья, определяемая индуцированно-наследственным свойством | множество препятствий, возможно, не конечное | индуцированный подграф | |
| Семья, определяемая несовершеннолетним наследственным имуществом | конечное множество препятствий | граф минор | Теорема Робертсона – Сеймура. |
См. Также [ править ]
- Гипотеза Эрдеша – Хайнала
- Проблема запрещенного подграфа
- Матроид минор
- Проблема заранкевича
Ссылки [ править ]
- ^ a b c Дистель, Рейнхард (2000), Теория графов , Тексты для выпускников по математике, 173 , Springer-Verlag, ISBN 0-387-98976-5.
- ^ Ауэр, Кристофер; Бахмайер, Кристиан; Бранденбург, Франц Дж .; Глайсснер, Андреас; Ханауэр, Катрин; Нойвирт, Даниэль; Рейслхубер, Йозеф (2013), «Распознавание внешних 1-плоских графов за линейное время», в Wismath, Стивен; Wolff, Александр (ред.), 21 - й Международный симпозиум, GD 2013, Бордо, Франция, 23-25 сентября, 2013, пересмотренная Избранные труды , Lecture Notes в области компьютерных наук, 8242 , стр 107-118,. DOI : 10.1007 / 978- 3-319-03841-4_10.
- ^ Гупта, А .; Impagliazzo, R. (1991), "Вычисление плоских переплетений" , Proc. 32-й симпозиум IEEE по основам информатики (FOCS '91) , Компьютерное общество IEEE, стр. 802–811, DOI : 10.1109 / SFCS.1991.185452.
- ^ Робертсон, Нил ; Сеймур, PD ; Томас, Робин (1993), "Бесконечные вложения графов в 3-пространство", Бюллетень Американского математического общества , 28 (1): 84–89, arXiv : math / 9301216 , doi : 10.1090 / S0273-0979-1993- 00335-5 , Руководство по ремонту 1164063 .
- ^ Béla Bollobás (1998) "Современная теория графов", Springer, ISBN 0-387-98488-7 стр. 9
- ^ Кашивабара, Тошинобу (1981), «Алгоритмы для некоторых графов пересечений», Сайто, Нобуджи; Нишизеки, Такао (ред.), Теория графов и алгоритмы, 17-й симпозиум Исследовательского института электрических коммуникаций, Университет Тохоку, Сендай, Япония, 24-25 октября 1980 г., Протоколы , Лекционные заметки по компьютерным наукам, 108 , Springer-Verlag, . С. 171-181, DOI : 10.1007 / 3-540-10704-5 \ _15.
- ↑ Чудновский, Мария ; Робертсон, Нил ; Сеймур, Пол ; Томас, Робин (2006), «Сильная теорема о совершенном графе» (PDF) , Annals of Mathematics , 164 (1): 51–229, arXiv : math / 0212070v1 , doi : 10.4007 / annals.2006.164.51 .
- ^ Beineke, LW (1968), "Производные графы орграфов", в Sachs, H .; Voss, H.-J .; Уолтер, Х.-Дж. (ред.), Beiträge zur Graphentheorie , Лейпциг: Teubner, стр. 17–33.
- ↑ Эль-Маллах, Эхаб; Colbourn, Чарльз Дж (1988), "Сложность некоторых проблем края делеционных", IEEE Transactions на схем и систем , 35 (3): 354-362, DOI : 10,1109 / 31,1748.
- ^ Takamizawa, K .; Нишизэки, Такао ; Сайто, Нобуджи (1981), "Комбинаторные задачи на последовательно-параллельных графах", Дискретная прикладная математика , 3 (1): 75–76, DOI : 10.1016 / 0166-218X (81) 90031-7.
- ^ Фёльдес, Стефан; Хаммер, Питер Лэдислав (1977a), «Сплит-графы», Труды Восьмой Юго-Восточной конференции по комбинаторике, теории графов и вычислениям (Университет штата Луизиана, Батон-Руж, штат Луизиана, 1977) , Congressus Numerantium, XIX , Виннипег: Utilitas Math ., стр. 311–315, MR 0505860
- ^ Bodlaender, Hans L. (1998), "Частичный k- арборетум графов с ограниченной шириной дерева", Теоретическая информатика , 209 (1-2): 1-45, DOI : 10.1016 / S0304-3975 (97) 00228- 4 CS1 maint: обескураженный параметр ( ссылка ).
- ^ Bodlaender, Ганс Л. ; Thilikos, Димитриос М. (1999), "Графы с branchwidth не более трех", журнал алгоритмов , 32 (2): 167-194, DOI : 10,1006 / jagm.1999.1011.
- ^ Seinsche, D. (1974), "Об одном свойстве класса n- раскрашиваемых графов", Журнал комбинаторной теории, серия B , 16 (2): 191–193, DOI : 10.1016 / 0095-8956 (74) 90063-X , Руководство по ремонту 0337679
- ^ a b Голумбик, Мартин Чарльз (1978), «Тривиально совершенные графы», Дискретная математика , 24 (1): 105–107, DOI : 10.1016 / 0012-365X (78) 90178-4 CS1 maint: обескураженный параметр ( ссылка )..
- ^ Метельский, Юрий; Тышкевич, Регина (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
- ^ Якобсон, MS; Kézdy, Андре Э .; Леэль, Йено (1997), "Распознавание пересечения графиков линейных однородных гиперграфов", графы и комбинаторика , 13 : 359-367, DOI : 10.1007 / BF03353014 , МР 1485929
- ^ Naik, Ranjan N .; Рао, SB; Шриханде, СС ; Singhi, NM (1982), "Пересечение графы к -равномерным гиперграфам", Европейский журнал комбинаторика , 3 : 159-172, DOI : 10.1016 / s0195-6698 (82) 80029-2 , MR 0670849 CS1 maint: обескураженный параметр ( ссылка )
- ^ Ю, Yanming (2006), «Больше Запретный Несовершеннолетние для Уай-Дельта-Уай сводимости», Электронный журнал комбинаторике , 13 Веб-сайт
