Запрещенная характеристика графа

Описание семейства графов путем исключения определенных (под)графов.

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

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

Определение

В более общем смысле, характеристика запрещенного графа — это метод определения семейства структур графа или гиперграфа путем указания подструктур, которым запрещено существовать в любом графе семейства. В разных семьях разный характер запрещенного . В общем случае структура G является членом семейства тогда и только тогда, когда запрещенная подструктура не содержится в G. Запрещенная подструктура может быть одной из: ${\displaystyle {\mathcal {F}}}$

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

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

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

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

Список запрещенных характеристик графов и гиперграфов

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

• Гипотеза Эрдеша – Хайнала
• Проблема с запрещенным подграфом
• Матроид минор
• Задача Заранкевича

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

1. Дистель, Рейнхард (2000), Теория графов , Тексты для выпускников по математике, том. 173, Шпрингер-Верлаг, ISBN 0-387-98976-5.
2. Ауэр, Кристофер; Бахмайер, Кристиан; Бранденбург, Франц Дж.; Гляйснер, Андреас; Ханауэр, Катрин; Нойвирт, Дэниел; Рейслубер, Йозеф (2013), «Распознавание внешних 1-планарных графов в линейном времени», в Висмат, Стивен; Вольф, Александр (ред.), 21-й Международный симпозиум, GD 2013, Бордо, Франция, 23–25 сентября 2013 г., Пересмотренные избранные статьи , Конспекты лекций по информатике, том. 8242, стр. 107–118, номер документа : 10.1007/978-3-319-03841-4_10..
3. Гупта, А.; Импальяццо, Р. (1991), "Вычисление плоских переплетений", Proc. 32-й симпозиум IEEE по основам компьютерных наук (FOCS '91) , IEEE Computer Society, стр. 802–811, doi : 10.1109/SFCS.1991.185452, S2CID  209133.
4. Робертсон, Нил ; Сеймур, Полиция ; Томас, Робин (1993), «Бесзвенные вложения графов в трехмерное пространство», Бюллетень Американского математического общества , 28 (1): 84–89, arXiv : math/9301216 , doi : 10.1090/S0273-0979-1993- 00335-5, МР  1164063, S2CID  1110662.
5. Бела Боллобас (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) , Annals of Mathematics , 164 (1): 51–229, arXiv : math/0212070v1 , doi : 10.4007/annals.2006.164.51, S2CID  119151552.
8. Бейнеке, Л.В. (1968), «Производные графы орграфов», Сакс, Х.; Восс, Х.-Дж.; Вальтер, Х.-Дж. (ред.), Beiträge zur Graphentheorie , Лейпциг: Тойбнер, стр. 17–33..
9. Эль-Маллах, Эхаб; Колборн, Чарльз Дж. (1988), «Сложность некоторых проблем с удалением ребер», IEEE Transactions on Circuits and Systems , 35 (3): 354–362, doi : 10.1109/31.1748.
10. Такамизава, К.; Нисидзеки, Такао ; Сайто, Нобудзи (1981), «Комбинаторные задачи на последовательно-параллельных графах», Discrete Applied Mathematics , 3 (1): 75–76, doi : 10.1016/0166-218X(81)90031-7.
11. Фёльдес, Стефан; Хаммер, Питер Ладислав (1977a), «Разделенные графы», Труды Восьмой Юго-восточной конференции по комбинаторике, теории графов и вычислениям (Университет штата Луизиана, Батон-Руж, Луизиана, 1977) , Congressus Numerantium, vol. XIX, Виннипег: Utilitas Math., стр. 311–315, MR  0505860.
12. Бодлендер, Ханс Л. (1998), «Частичный k -дендрарий графов с ограниченной шириной дерева», Theoretical Computer Science , 209 (1–2): 1–45, doi : 10.1016/S0304-3975(97)00228- 4, HDL : 1874/18312.
13. Бодлендер, Ганс Л .; Тиликос, Димитриос М. (1999), «Графы с шириной ветвей не более трех», Журнал алгоритмов , 32 (2): 167–194, doi : 10.1006/jagm.1999.1011, hdl : 1874/2734.
14. Зейнше, Д. (1974), «Об одном свойстве класса n -раскрашиваемых графов», Журнал комбинаторной теории , серия B, 16 (2): 191–193, doi : 10.1016/0095-8956(74) 90063-Х , МР  0337679
15. Голумбик, Мартин Чарльз (1978), «Тривиально совершенные графики», Discrete Mathematics , 24 (1): 105–107, doi : 10.1016/0012-365X(78)90178-4.
16. Метельский, Юрий; Тышкевич, Регина (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
17. Джейкобсон, М.С.; Кезди, Андре Э.; Лехель, Йено (1997), «Распознавание графов пересечений линейных однородных гиперграфов», Graphs and Combinatorics , 13 (4): 359–367, doi : 10.1007/BF03353014, MR  1485929, S2CID  9173731
18. Наик, Ранджан Н.; Рао, СБ; Шрикханде, SS ; Сингхи, Н.М. (1982), «Графы пересечений k -однородных гиперграфов», Европейский журнал комбинаторики , 3 : 159–172, doi : 10.1016/s0195-6698(82)80029-2 , MR  0670849
19. Ю, Янмин (2006), «Более запрещенные миноры для сводимости звезда-дельта-звезда», Электронный журнал комбинаторики , 13 , doi : 10.37236/1033Веб-сайт
20. Цзян, Цзилинь; Полянский, Александр (01.03.2020). «Запрещенные подграфы для графиков ограниченного спектрального радиуса с приложениями к равноугольным линиям». Израильский математический журнал . 236 (1): 393–421. arXiv : 1708.02317 . дои : 10.1007/s11856-020-1983-2. ISSN  1565-8511.