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

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

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

Определение

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

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

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

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

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

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

Семья	Препятствия	Связь	Ссылка
Леса	Петли, пары параллельных ребер и циклы любой длины.	Подграф	Определение
Леса	Петля (для мультиграфов) или треугольник К ₃ (для простых графов)	Граф минор	Определение
Линейные леса	[Петля/треугольник К ₃ (см. выше)] и звездочка К _1,3	Граф минор	Определение
Графики без когтей	Звезда К _1,3	Индуцированный подграф	Определение
Графики сопоставимости		Индуцированный подграф
Графики без треугольников	Треугольник К ₃	Индуцированный подграф	Определение
Планарные графы	К ₅ и К _3,3	Гомеоморфный подграф	Теорема Куратовского
Планарные графы	К ₅ и К _3,3	Граф минор	Теорема Вагнера
Внепланарные графы	К ₄ и К _2,3	Граф минор	Дистель (2000) , ^[1] п. 107
Внешние 1-планарные графы	Шесть запрещенных несовершеннолетних	Граф минор	Ауэр и др. (2013) ^[2]
Графы фиксированного рода	Конечное множество препятствий	Граф минор	Дистель (2000) , ^[1] п. 275
Апекс-графики	Конечное множество препятствий	Граф минор	^[3]
Бессвязно встраиваемые графики	Петерсен Семья	Граф минор	^[4]
Двудольные графы	Нечетные циклы	Подграф	^[5]
Хордальные графы	Циклы длиной 4 и более	Индуцированный подграф	^[6]
Идеальные графики	Циклы нечетной длины 5 и более или их дополнения	Индуцированный подграф	^[7]
Линейный график графиков	9 запрещенных подграфов	Индуцированный подграф	^[8]
Объединения графов кактусовых графов	с четырьмя вершинами, Ромбический граф образованный удалением ребра из полного графа K ₄	Граф минор	^[9]
Лестничные диаграммы	K _2,3 и его двойственный граф	Гомеоморфный подграф	^[10]
Разделение графиков	$C_{4},C_{5},{\bar {C}}_{4}\left(=K_{2}+K_{2}\right)$	Индуцированный подграф	^[11]
2-связные последовательно-параллельные ( ширина дерева ≤ 2, ширина ветвей ≤ 2)	К ₄	Граф минор	Дистель (2000) , ^[1] п. 327
Ширина дерева ≤ 3	К ₅ , октаэдр , пятиугольная призма , граф Вагнера	Граф минор	^[12]
Ширина ветки ≤ 3	К ₅ , октаэдр , куб , граф Вагнера	Граф минор	^[13]
Приводимые к дополнению графы (кографы)	4-вершинный путь P ₄	Индуцированный подграф	^[14]
Тривиально совершенные графы	4-вершинный путь P ₄ и 4-вершинный цикл C ₄	Индуцированный подграф	^[15]
Пороговые графики	4-вершинный путь P ₄ , 4-вершинный цикл C ₄ и дополнение к C ₄	Индуцированный подграф	^[15]
Линейный граф 3-равномерных линейных гиперграфов	Конечный список запрещенных индуцированных подграфов минимальной степени не ниже 19.	Индуцированный подграф	^[16]
Линейный график k -однородных линейных гиперграфов, k > 3	Конечный список запрещенных индуцированных подграфов с минимальной степенью ребра не менее 2 k ² − 3 тыс. + 1	Индуцированный подграф	^[17]^[18]
Графы ΔY-сводимые к одной вершине	Конечный список из не менее 68 миллиардов различных сумм (1,2,3)-клики.	Граф минор	^[19]
Графики спектрального радиуса не более $\lambda$	Конечное множество препятствий существует тогда и только тогда, когда $\lambda <{\sqrt {2+{\sqrt {5}}}}$ и $\lambda \neq \beta _{m}^{1/2}+\beta _{m}^{-1/2}$ для любого $m\geq 2$ , где $\beta _{m}$ является самым большим корнем $x^{m+1}=1+x+\dots +x^{m-1}$ .	Подграф/индуцированный подграф	^[20]
Кластерные графики	граф путей с тремя вершинами	Индуцированный подграф
Общие теоремы
Семья, определяемая индуцированно-наследственным свойством	Возможно, бесконечный набор препятствий	Индуцированный подграф
Семья, определяемая несовершеннолетним наследственным имуществом	Конечное множество препятствий	Граф минор	Теорема Робертсона – Сеймура

См. также

Ссылки

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

[diestel-1] Jump up to: ^а ^б ^с Дистель, Рейнхард (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, doi : 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), «Производные графы орграфов», в Саксе, Х.; Восс, Х.-Дж.; Вальтер, Х.-Дж. (ред.), Вклад в теорию графов , Лейпциг: Тойбнер, стр. 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), «Графы с шириной ветвей не более трех», Journal of Algorithms , 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

[g78-15] Jump up to: ^а ^б Голумбик, Мартин Чарльз (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] Джейкобсон, MS; Кезди, Андре Э.; Лехель, Йено (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 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]