Характеризация запрещёнными графами

Характеризация запрещёнными графами — это метод описания семейства графов или гиперграфов путём указания подструктур, которым запрещено появляться внутри любого графа в семействе.

Запрещённые графыПравить

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

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

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

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

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

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

Список характеризаций запрещёнными графами (для графов и гиперграфов)Править

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

Семейство	Запрещённые графы	Зависимость	Связь
Леса	петли, пары параллельных рёбер и циклы любой длины	подграф	Определение
петля (для мультиграфов) или треугольник K₃ (для простых графов)	минор графа	Определение
Графы без клешней	звезда K_1,3	порождённый подграф	Определение
Графы сравнимости		порождённый подграф
Графы без треугольников	треугольник K₃	порождённый подграф	Определение
Планарные графы	K₅ и K_3,3	гомеоморфный подграф	теорема Понтрягина — Куратовского
K₅ и K_3,3	минор графа	теорема Вагнера
Внешнепланарные графы	K₄ и K_2,3	минор графа	Дистель, 4. Планарные графы, с. 115, упр. 23^[1]
Внешние 1-планарные графы	пять запрещённых миноров	минор графа	Ауэр, Бахмайер и др.^[2]
Графы с фиксировнным родом	конечное препятствующее множество (уже для тороидальных графов размером не меньше 250815)	минор графа	Дистель, 12. Миноры, деревья и полный предпорядок, с. 387, упр. 53^[1]
Верхушечный граф	конечное препятствующее множество	минор графа	^[3]
Графы, допускающие вложение без зацеплений	Петерсеново семейство графов	минор графа	^[4]
Двудольные графы	нечётные циклы	подграф	^[5]
Хордальные графы	циклы длины 4 или более	порождённый подграф	^[6]
Совершенные графы	нечетные циклы длины 5 и более и их дополнения	порождённый подграф	^[7]
Рёберные графы для графов	девять запрещённых подграфов (перечислены здесь)	порождённый подграф	^[8]
Объединения графов-кактусов	алмаз, образованный удалением ребра из полного графа K₄	минор графа	^[9]
Лестницы	K_2,3 и его двойственный граф	гомеоморфный подграф	^[10]
Циркулярные графы дуг Хелли		порождённый подграф	^[11]
Расщепляемые графы	$\text{[math]}$ $\text{[math]}$ $C_{4},C_{5},{\bar {C_{4}}}(=K_{2}+K_{2})$	порождённый подграф	^[12]
Параллельно-последовательные графы (древесная ширина $\text{[math]}$ $\text{[math]}$ $\leqslant 2$ , ширина ветвей $\text{[math]}$ $\text{[math]}$ $\leqslant 2$ )	K₄	минор графа	Дистель, 7. Экстремальная теория графов, с. 203, упр. 31^[1]
Древесная ширина $\text{[math]}$ $\text{[math]}$ $\leqslant 3$	K₅, октаэдр, пятиугольная призма, граф Вагнера	минор графа	^[13]
Древесная ширина $\text{[math]}$ $\text{[math]}$ $<3$	K₄	минор графа	Дистель, 12. Миноры, деревья и полный предпорядок, с. 370, пр. 12.6.2^[1]
Ширина ветвей $\text{[math]}$ $\text{[math]}$ $\leqslant 3$	K₅, октаэдр, куб, граф Вагнера	минор графа	^[14]
Дополнительно сводимые графы (кографы)	Граф P₄	порождённый подграф	^[15]
Тривиально совершенные графы	Граф P₄ и цикл C₄	порождённый подграф	^[16]
Пороговые графы	Граф P₄, цикл C₄ и дополнение C₄	порождённый подграф	^[16]
Рёберные графы 3-однородных линейных гиперграфов	конечный список запрещённых порождённых подграфов с минимальной степенью, не меньшей 19	порождённый подграф	^[17]
Рёберные графы k-однородные линейные гиперграфы, k > 3	конечный список запрещённых порождённых подграфов с минимальной степенью рёбер по меньшей мере 2k² − 3k + 1	порождённый подграф	^[18]^[19]

Основные теоремы

семейство, определённое порождённым наследственным свойством	(не обязательно конечное) препятствующее множество	порождённый подграф
семейство, определённое минорным наследственным свойством	конечное препятствующее множество	минор графа	Теорема Робертсона – Сеймура

См. такжеПравить

ПримечанияПравить

↑ ¹ ² ³ ⁴ Reinhard Diestel. Graph Theory. Архивная копия от 9 апреля 2011 на Wayback Machine GTM 173, 5th edition 2016/17. Springer-Verlag, Heidelberg. Graduate Texts in Mathematics, Volume 173. ISBN 978-3-662-53621-6
↑ Christopher Auer, Christian Bachmaier, Franz J. Brandenburg, Andreas Gleißner, Kathrin Hanauer, Daniel Neuwirth, Josef Reislhuber. 21st International Symposium, GD 2013, Bordeaux, France, September 23-25, 2013, Revised Selected Papers / Stephen Wismath, Alexander Wolff,. — 2013. — Т. 8242. — С. 107–118. — (Lecture Notes in Computer Science). — doi:10.1007/978-3-319-03841-4_10..
↑ A. Gupta, R. Impagliazzo. Proc. 32nd IEEE Symposium on Foundations of Computer Science (FOCS '91). — IEEE Computer Society, 1991. — С. 802–811. — doi:10.1109/SFCS.1991.185452..
↑ Neil Robertson, P. D. Seymour, Robin Thomas. Linkless embeddings of graphs in 3-space // Bulletin of the American Mathematical Society. — 1993. — Т. 28, вып. 1. — С. 84–89. — doi:10.1090/S0273-0979-1993-00335-5. — arXiv:math/9301216..
↑ Béla Bollobás^[en]. Modern Graph Theory. — Springer, 1998. — ISBN 0-387-98488-7.
↑ Toshinobu Kashiwabara. Graph Theory and Algorithms, 17th Symposium of Research Institute of Electric Communication, Tohoku University, Sendai, Japan, October 24-25, 1980, Proceedings / Nobuji Saito, Takao Nishizeki. — Springer-Verlag, 1981. — Т. 108. — С. 171–181. — (Lecture Notes in Computer Science). — doi:10.1007/3-540-10704-5\_15..
↑ Maria Chudnovsky, Neil Robertson, Paul Seymour, Robin Thomas. The strong perfect graph theorem // Annals of Mathematics. — 2006. — Т. 164, вып. 1. — С. 51–229. — doi:10.4007/annals.2006.164.51. — arXiv:math/0212070v1..
↑ L. W. Beineke. Beiträge zur Graphentheorie / H. Sachs, H.-J. Voss, H.-J. Walter. — Leipzig: Teubner, 1968. — С. 17–33..
↑ Ehab El-Mallah, Charles Colbourn. The complexity of some edge deletion problems // IEEE Transactions on Circuits and Systems. — 1988. — Т. 35, вып. 3. — С. 354–362. — doi:10.1109/31.1748..
↑ K. Takamizawa, Takao Nishizeki, Nobuji Saito. Combinatorial problems on series-parallel graphs // Discrete Applied Mathematics. — 1981. — Т. 3, вып. 1. — С. 75–76. — doi:10.1016/0166-218X(81)90031-7..
↑ Benson L. Joeris, Min Chih Lin, Ross M. McConnell, Jeremy P. Spinrad, Jayme L. Szwarcfiter. Linear-Time Recognition of Helly Circular-Arc Models and Graphs // Algorithmica. — 2009. — Т. 59, вып. 2. — С. 215–239. — doi:10.1007/s00453-009-9304-5.
↑ Stéphane Földes, Peter L. Peter Hammer. Proceedings of the Eighth Southeastern Conference on Combinatorics, Graph Theory and Computing (Louisiana State Univ., Baton Rouge, La., 1977). — Winnipeg: Utilitas Math., 1977a. — Т. XIX. — С. 311–315. — (Congressus Numerantium).
↑ Hans L. Bodlaender. A partial k-arboretum of graphs with bounded treewidth // Theoretical Computer Science. — 1998. — Т. 209, вып. 1–2. — С. 1–45. — doi:10.1016/S0304-3975(97)00228-4..
↑ Hans L. Bodlaender, Dimitrios M. Thilikos. Graphs with branchwidth at most three // Journal of Algorithms. — 1999. — Т. 32, вып. 2. — С. 167–194. — doi:10.1006/jagm.1999.1011..
↑ D. Seinsche. On a property of the class of n-colorable graphs // Journal of Combinatorial Theory, Series B. — 1974. — Т. 16, вып. 2. — С. 191–193. — doi:10.1016/0095-8956(74)90063-X.
↑ ¹ ² Martin Charles Golumbic. Trivially perfect graphs // Discrete Mathematics. — 1978. — Т. 24, вып. 1. — С. 105–107. — doi:10.1016/0012-365X(78)90178-4.
↑ Yury Metelsky, Regina Tyshkevich. On line graphs of linear 3-uniform hypergraphs // Journal of Graph Theory. — 1997. — Vol. 25. — Вып. 4. — С. 243–251. — doi:10.1002/(SICI)1097-0118(199708)25:4<243::AID-JGT1>3.0.CO;2-K.
↑ M. S. Jacobson, Andre E. Kézdy, Jeno Lehel. Recognizing intersection graphs of linear uniform hypergraphs // Graphs and Combinatorics. — 1997. — Т. 13. — С. 359–367. — doi:10.1007/BF03353014.
↑ Ranjan N. Naik, S. B. Rao, S. S. Shrikhande, N. M. Singhi. Intersection graphs of k-uniform hypergraphs // European J. Combinatorics. — 1982. — Т. 3. — С. 159–172. — doi:10.1016/s0195-6698(82)80029-2.

[diestel-1] ¹ ² ³ ⁴ Reinhard Diestel. Graph Theory. Архивная копия от 9 апреля 2011 на Wayback Machine GTM 173, 5th edition 2016/17. Springer-Verlag, Heidelberg. Graduate Texts in Mathematics, Volume 173. ISBN 978-3-662-53621-6

[2] Christopher Auer, Christian Bachmaier, Franz J. Brandenburg, Andreas Gleißner, Kathrin Hanauer, Daniel Neuwirth, Josef Reislhuber. 21st International Symposium, GD 2013, Bordeaux, France, September 23-25, 2013, Revised Selected Papers / Stephen Wismath, Alexander Wolff,. — 2013. — Т. 8242. — С. 107–118. — (Lecture Notes in Computer Science). — doi:10.1007/978-3-319-03841-4_10..

[3] A. Gupta, R. Impagliazzo. Proc. 32nd IEEE Symposium on Foundations of Computer Science (FOCS '91). — IEEE Computer Society, 1991. — С. 802–811. — doi:10.1109/SFCS.1991.185452..

[4] Neil Robertson, P. D. Seymour, Robin Thomas. Linkless embeddings of graphs in 3-space // Bulletin of the American Mathematical Society. — 1993. — Т. 28, вып. 1. — С. 84–89. — doi:10.1090/S0273-0979-1993-00335-5. — arXiv:math/9301216..

[5] Béla Bollobás^[en]. Modern Graph Theory. — Springer, 1998. — ISBN 0-387-98488-7.

[6] Toshinobu Kashiwabara. Graph Theory and Algorithms, 17th Symposium of Research Institute of Electric Communication, Tohoku University, Sendai, Japan, October 24-25, 1980, Proceedings / Nobuji Saito, Takao Nishizeki. — Springer-Verlag, 1981. — Т. 108. — С. 171–181. — (Lecture Notes in Computer Science). — doi:10.1007/3-540-10704-5\_15..

[7] Maria Chudnovsky, Neil Robertson, Paul Seymour, Robin Thomas. The strong perfect graph theorem // Annals of Mathematics. — 2006. — Т. 164, вып. 1. — С. 51–229. — doi:10.4007/annals.2006.164.51. — arXiv:math/0212070v1..

[8] L. W. Beineke. Beiträge zur Graphentheorie / H. Sachs, H.-J. Voss, H.-J. Walter. — Leipzig: Teubner, 1968. — С. 17–33..

[9] Ehab El-Mallah, Charles Colbourn. The complexity of some edge deletion problems // IEEE Transactions on Circuits and Systems. — 1988. — Т. 35, вып. 3. — С. 354–362. — doi:10.1109/31.1748..

[10] K. Takamizawa, Takao Nishizeki, Nobuji Saito. Combinatorial problems on series-parallel graphs // Discrete Applied Mathematics. — 1981. — Т. 3, вып. 1. — С. 75–76. — doi:10.1016/0166-218X(81)90031-7..

[11] Benson L. Joeris, Min Chih Lin, Ross M. McConnell, Jeremy P. Spinrad, Jayme L. Szwarcfiter. Linear-Time Recognition of Helly Circular-Arc Models and Graphs // Algorithmica. — 2009. — Т. 59, вып. 2. — С. 215–239. — doi:10.1007/s00453-009-9304-5.

[12] Stéphane Földes, Peter L. Peter Hammer. Proceedings of the Eighth Southeastern Conference on Combinatorics, Graph Theory and Computing (Louisiana State Univ., Baton Rouge, La., 1977). — Winnipeg: Utilitas Math., 1977a. — Т. XIX. — С. 311–315. — (Congressus Numerantium).

[13] Hans L. Bodlaender. A partial k-arboretum of graphs with bounded treewidth // Theoretical Computer Science. — 1998. — Т. 209, вып. 1–2. — С. 1–45. — doi:10.1016/S0304-3975(97)00228-4..

[14] Hans L. Bodlaender, Dimitrios M. Thilikos. Graphs with branchwidth at most three // Journal of Algorithms. — 1999. — Т. 32, вып. 2. — С. 167–194. — doi:10.1006/jagm.1999.1011..

[15] D. Seinsche. On a property of the class of n-colorable graphs // Journal of Combinatorial Theory, Series B. — 1974. — Т. 16, вып. 2. — С. 191–193. — doi:10.1016/0095-8956(74)90063-X.

[g78-16] ¹ ² Martin Charles Golumbic. Trivially perfect graphs // Discrete Mathematics. — 1978. — Т. 24, вып. 1. — С. 105–107. — doi:10.1016/0012-365X(78)90178-4.

[17] Yury Metelsky, Regina Tyshkevich. On line graphs of linear 3-uniform hypergraphs // Journal of Graph Theory. — 1997. — Vol. 25. — Вып. 4. — С. 243–251. — doi:10.1002/(SICI)1097-0118(199708)25:4<243::AID-JGT1>3.0.CO;2-K.

[18] M. S. Jacobson, Andre E. Kézdy, Jeno Lehel. Recognizing intersection graphs of linear uniform hypergraphs // Graphs and Combinatorics. — 1997. — Т. 13. — С. 359–367. — doi:10.1007/BF03353014.

[19] Ranjan N. Naik, S. B. Rao, S. S. Shrikhande, N. M. Singhi. Intersection graphs of k-uniform hypergraphs // European J. Combinatorics. — 1982. — Т. 3. — С. 159–172. — doi:10.1016/s0195-6698(82)80029-2.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]