Периферийный цикл

В теории графов ( периферийный цикл или периферийная схема ) в неориентированном графе интуитивно представляет собой цикл , который не отделяет какую-либо часть графа от любой другой части. Периферийные циклы (или, как их первоначально называли, периферийные многоугольники , поскольку Татт называл циклы «многоугольниками») были впервые изучены Тутте (1963) и играют важную роль в описании плоских графов и в создании пространств циклов непланарных графов. . ^[1]

Определения

Периферический цикл $C$ в графике $G$ может быть определен формально одним из нескольких эквивалентных способов:

$C$ является периферийным, если это простой цикл в связном графе, обладающий свойством, что для каждых двух ребер $e_{1}$ и $e_{2}$ в $G\setminus C$ , существует путь в $G$ это начинается с $e_{1}$ , заканчивается $e_{2}$ , и не имеет внутренних вершин, принадлежащих $C$ . ^[2]
Если $C$ это любой подграф $G$ , мост ^[3] из $C$ это минимальный подграф $B$ из $G$ который не пересекается по ребру с $C$ и у него есть то свойство, что все его точки присоединения (вершины, примыкающие к ребрам в обоих $B$ и $G\setminus B$ ) принадлежат $C$ . ^[4] Простой цикл $C$ является периферийным, если у него ровно один мост. ^[5]
В связном графе, не являющемся тэта-графом , периферийные циклы не могут иметь хорды, поскольку любая хорда была бы мостом, отделенным от остальной части графа. В этом случае, $C$ является периферийным, если это индуцированный цикл , обладающий тем свойством, что подграф $G\setminus C$ образованный удалением ребер и вершин $C$ подключен. ^[6]

Эквивалентность этих определений нетрудно увидеть: связный подграф $G\setminus C$ (вместе с краями, соединяющими его с $C$ ), или хорда цикла, из-за которой он не индуцируется, в любом случае должна быть мостом, а также должна быть классом эквивалентности бинарного отношения на ребрах, в котором два ребра связаны, если они являются концами путь без внутренних вершин $C$ . ^[7]

Характеристики

Периферийные циклы появляются в теории многогранных графов , то есть 3-вершинно-связных плоских графов . Для каждого планарного графа $G$ , и каждое плоское вложение $G$ грани вложения, являющиеся индуцированными циклами, должны быть периферийными циклами. В многогранном графе все грани являются периферийными циклами, и каждый периферийный цикл является гранью. ^[8] Из этого факта следует, что (с точностью до комбинаторной эквивалентности, выбора внешней грани и ориентации плоскости) каждый многогранный граф имеет единственное планарное вложение. ^[9]

В плоских графах пространство циклов порождается гранями, но в неплоских графах периферийные циклы играют аналогичную роль: для каждого конечного графа, связанного с 3 вершинами, пространство циклов порождается периферийными циклами. ^[10] Результат также можно распространить на локально конечные, но бесконечные графы. ^[11] В частности, отсюда следует, что 3-связные графы гарантированно содержат периферийные циклы. Существуют двусвязные графы, не содержащие периферийных циклов (пример — полный двудольный граф $K_{2,4}$ , для которого каждый цикл имеет два моста), но если 2-связный граф имеет минимальную степень три, то он содержит хотя бы один периферийный цикл. ^[12]

Периферийные циклы в 3-связных графах можно вычислять за линейное время и использовать для разработки тестов планарности. ^[13]Они также были расширены до более общего понятия неразделяющихся разложений ушей. В некоторых алгоритмах проверки планарности графов полезно найти непериферийный цикл, чтобы разбить задачу на более мелкие подзадачи. В двусвязном графе с рангом цепи меньше трех (например, в графе циклов или тета-графе ) каждый цикл является периферийным, но каждый двусвязный граф с рангом цепи три или более имеет непериферийный цикл, который можно найти за линейное время. ^[14]

Обобщая хордальные графы , Сеймур и Уивер (1984) определяют ущемленный граф как граф, в котором каждый периферийный цикл является треугольником. Они характеризуют эти графы как клики-суммы хордальных графов и максимальных планарных графов . ^[15]

Связанные понятия

Периферийные циклы также называют неразделяющими циклами. ^[2] но этот термин неоднозначен, поскольку он также использовался для двух связанных, но разных понятий: простых циклов, удаление которых отключило бы оставшийся граф, ^[16] и циклы топологически вложенного графа, такие, что разрезание по циклу не отсоединяет поверхность, на которую вложен граф. ^[17]

В матроидах неразделяющая схема — это схема матроида (т. е. минимального зависимого множества), такая, что при удалении схемы остается связный матроид меньшего размера (т. е. который не может быть записан как прямая сумма матроидов). . ^[18] Они аналогичны периферийным циклам, но не одинаковы даже в графических матроидах (матроидах, схемы которых представляют собой простые циклы графа). Например, в полном двудольном графе $K_{2,3}$ , каждый цикл является периферийным (имеет только один мост, двуреберный путь), но графический матроид, образованный этим мостом, не связен, поэтому ни одна схема графического матроида $K_{2,3}$ является неразрывным.

Ссылки

^ Тутте, WT (1963), «Как нарисовать график», Труды Лондонского математического общества , третья серия, 13 : 743–767, doi : 10.1112/plms/s3-13.1.743 , MR 0158387 .
↑ Перейти обратно: Перейти обратно: ^а ^б Ди Баттиста, Джузеппе; Идс, Питер ; Тамассия, Роберто ; Толлис, Иоаннис Г. (1998), Рисование графиков: алгоритмы визуализации графиков , Prentice Hall , стр. 74–75, ISBN 978-0-13-301615-4 .
^ Не путать с мостом (теорией графов) , другой концепцией.
^ Тутте, WT (1960), «Выпуклые представления графов», Труды Лондонского математического общества , третья серия, 10 : 304–320, doi : 10.1112/plms/s3-10.1.304 , MR 0114774 .
^ Это определение периферических циклов, первоначально использованное Тутте (1963) . Сеймур и Уивер (1984) используют то же определение периферического цикла, но с другим определением моста, которое больше напоминает определение индуцированного цикла для периферических циклов.
^ По сути, это определение, использованное Брюном (2004) . Однако Брюн различает случай, когда $G$ изолировал вершины от разъединений, вызванных удалением $C$ .
^ См., например, теорему 2.4 Тутте (1960) , показывающую, что множества вершин мостов связаны путями, см. Seymour & Weaver (1984) для определения мостов с использованием хорд и связных компонентов, а также см. Di Battista et al. (1998) для определения мостов с использованием классов эквивалентности бинарного отношения на ребрах.
^ Тутте (1963) , Теоремы 2.7 и 2.8.
^ См. замечания к теореме 2.8 в Tutte (1963) . Как отмечает Тутте, это уже было известно Уитни, Хасслер (1932), «Неразделимые и плоские графы», Труды Американского математического общества , 34 (2): 339–362, doi : 10.2307/1989545 , JSTOR 1989545 , MR 1501641 .
^ Все (1963) , Теорема 2.5.
^ Брюн, Хеннинг (2004), «Пространство циклов 3-связного локально конечного графа порождается его конечными и бесконечными периферийными цепями», Журнал комбинаторной теории , серия B, 92 (2): 235–256, doi : 10.1016 /j.jctb.2004.03.005 , МР 2099143 .
^ Томассен, Карстен ; Тофт, Бьерн (1981), «Неразделяющие индуцированные циклы в графах», Журнал комбинаторной теории , серия B, 31 (2): 199–224, doi : 10.1016/S0095-8956(81)80025-1 , MR 0630983 .
^ Шмидт, Йенс М. (2014), «Последовательность Мондшейна», Материалы 41-го Международного коллоквиума по автоматам, языкам и программированию (ICALP'14) , Конспекты лекций по информатике, том. 8572, стр. 967–978, номер домена : 10.1007/978-3-662-43948-7_80 , ISBN. 978-3-662-43947-0 .
^ Ди Баттиста и др. (1998) , Лемма 3.4, с. 75–76.
^ Сеймур, Полиция ; Уивер, Р.В. (1984), «Обобщение хордальных графов», Журнал теории графов , 8 (2): 241–251, doi : 10.1002/jgt.3190080206 , MR 0742878 .
^ Например, см. Борс, Ю.М.; Вапаре, Б.Н. (2008), «Вершинные непересекающиеся неразделяющие циклы в графах», Журнал Индийского математического общества , Новая серия, 75 (1–4): 75–92 (2009), MR 2662989 .
^ Например, см. Кабельо, Серджио; Мохар, Боян (2007), «Нахождение кратчайших неразделяющихся и несжимаемых циклов для топологически вложенных графов», Discrete and Computational Geometry , 37 (2): 213–235, doi : 10.1007/s00454-006-1292-5 , МР 2295054 .
^ Майя, Браулио, Младший; Лемос, Маноэль; Мело, Тереза Р.Б. (2007), «Неразделяющие схемы и косхемы в матроидах», Комбинаторика, сложность и случайность , Оксфордские лекции, сер. Математика. Приложение, вып. 34, Оксфорд: Оксфордский университет. Press, стр. 162–171, doi : 10.1093/acprof:oso/9780198571278.003.0010 , ISBN. 978-0-19-857127-8 , МР 2314567 {{citation}}: CS1 maint: несколько имен: список авторов ( ссылка ) .

[1] Тутте, WT (1963), «Как нарисовать график», Труды Лондонского математического общества , третья серия, 13 : 743–767, doi : 10.1112/plms/s3-13.1.743 , MR 0158387 .

[dett-2] Перейти обратно: Перейти обратно: ^а ^б Ди Баттиста, Джузеппе; Идс, Питер ; Тамассия, Роберто ; Толлис, Иоаннис Г. (1998), Рисование графиков: алгоритмы визуализации графиков , Prentice Hall , стр. 74–75, ISBN 978-0-13-301615-4 .

[3] Не путать с мостом (теорией графов) , другой концепцией.

[4] Тутте, WT (1960), «Выпуклые представления графов», Труды Лондонского математического общества , третья серия, 10 : 304–320, doi : 10.1112/plms/s3-10.1.304 , MR 0114774 .

[5] Это определение периферических циклов, первоначально использованное Тутте (1963) . Сеймур и Уивер (1984) используют то же определение периферического цикла, но с другим определением моста, которое больше напоминает определение индуцированного цикла для периферических циклов.

[6] По сути, это определение, использованное Брюном (2004) . Однако Брюн различает случай, когда $G$ изолировал вершины от разъединений, вызванных удалением $C$ .

[7] См., например, теорему 2.4 Тутте (1960) , показывающую, что множества вершин мостов связаны путями, см. Seymour & Weaver (1984) для определения мостов с использованием хорд и связных компонентов, а также см. Di Battista et al. (1998) для определения мостов с использованием классов эквивалентности бинарного отношения на ребрах.

[8] Тутте (1963) , Теоремы 2.7 и 2.8.

[9] См. замечания к теореме 2.8 в Tutte (1963) . Как отмечает Тутте, это уже было известно Уитни, Хасслер (1932), «Неразделимые и плоские графы», Труды Американского математического общества , 34 (2): 339–362, doi : 10.2307/1989545 , JSTOR 1989545 , MR 1501641 .

[10] Все (1963) , Теорема 2.5.

[11] Брюн, Хеннинг (2004), «Пространство циклов 3-связного локально конечного графа порождается его конечными и бесконечными периферийными цепями», Журнал комбинаторной теории , серия B, 92 (2): 235–256, doi : 10.1016 /j.jctb.2004.03.005 , МР 2099143 .

[12] Томассен, Карстен ; Тофт, Бьерн (1981), «Неразделяющие индуцированные циклы в графах», Журнал комбинаторной теории , серия B, 31 (2): 199–224, doi : 10.1016/S0095-8956(81)80025-1 , MR 0630983 .

[13] Шмидт, Йенс М. (2014), «Последовательность Мондшейна», Материалы 41-го Международного коллоквиума по автоматам, языкам и программированию (ICALP'14) , Конспекты лекций по информатике, том. 8572, стр. 967–978, номер домена : 10.1007/978-3-662-43948-7_80 , ISBN. 978-3-662-43947-0 .

[14] Ди Баттиста и др. (1998) , Лемма 3.4, с. 75–76.

[15] Сеймур, Полиция ; Уивер, Р.В. (1984), «Обобщение хордальных графов», Журнал теории графов , 8 (2): 241–251, doi : 10.1002/jgt.3190080206 , MR 0742878 .

[16] Например, см. Борс, Ю.М.; Вапаре, Б.Н. (2008), «Вершинные непересекающиеся неразделяющие циклы в графах», Журнал Индийского математического общества , Новая серия, 75 (1–4): 75–92 (2009), MR 2662989 .

[17] Например, см. Кабельо, Серджио; Мохар, Боян (2007), «Нахождение кратчайших неразделяющихся и несжимаемых циклов для топологически вложенных графов», Discrete and Computational Geometry , 37 (2): 213–235, doi : 10.1007/s00454-006-1292-5 , МР 2295054 .

[18] Майя, Браулио, Младший; Лемос, Маноэль; Мело, Тереза Р.Б. (2007), «Неразделяющие схемы и косхемы в матроидах», Комбинаторика, сложность и случайность , Оксфордские лекции, сер. Математика. Приложение, вып. 34, Оксфорд: Оксфордский университет. Press, стр. 162–171, doi : 10.1093/acprof:oso/9780198571278.003.0010 , ISBN. 978-0-19-857127-8 , МР 2314567 {{citation}}: CS1 maint: несколько имен: список авторов ( ссылка ) .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]