Периферийный цикл - Peripheral cycle - Wikipedia

На этом графе красный треугольник, образованный вершинами 1, 2 и 5, представляет собой периферийный цикл: четыре оставшихся ребра образуют один мост. Однако пятиугольник 1–2–3–4–5 не является периферийным, так как два оставшихся ребра образуют два отдельных мостика.

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

Определения

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

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

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

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

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

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

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

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

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

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

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

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

1. Тутте, В. Т. (1963), «Как нарисовать график», Труды Лондонского математического общества, Третья серия, 13: 743–767, Дои:10.1112 / плмс / с3-13.1.743, МИСТЕР  0158387.
2. Ди Баттиста, Джузеппе; Идс, Питер; Тамассия, Роберто; Толлис, Иоаннис Г. (1998), Рисование графиков: алгоритмы визуализации графиков, Prentice Hall, стр. 74–75, ISBN  978-0-13-301615-4.
3. По сути, это определение, используемое Брун (2004). Однако Брун выделяет случай, когда ${\displaystyle G}$ имеет изолированные вершины от разрывов, вызванных удалением ${\displaystyle C}$.
4. Не путать с мост (теория графов), другое понятие.
5. Тутте, В. Т. (1960), «Выпуклые представления графов», Труды Лондонского математического общества, Третья серия, 10: 304–320, Дои:10.1112 / плмс / с3-10.1.304, МИСТЕР  0114774.
6. Это определение периферийных циклов, первоначально использовавшееся Тутт (1963). Сеймур и Уивер (1984) используйте то же определение периферийного цикла, но с другим определением моста, которое больше напоминает определение индуцированного цикла для периферийных циклов.
7. См. Например Теорема 2.4 из Тутт (1960), показывающее, что множества вершин мостов линейно связны, см. Сеймур и Уивер (1984) для определения мостов, использующих хорды и компоненты связности, а также см. Di Battista et al. (1998) для определения мостов с использованием классов эквивалентности бинарного отношения на ребрах.
8. Тутт (1963), Теоремы 2.7 и 2.8.
9. См. Примечания после теоремы 2.8 в Тутт (1963). Как замечает Тутте, об этом уже знали Уитни, Хасслер (1932), «Неразделимые и плоские графы», Труды Американского математического общества, 34 (2): 339–362, Дои:10.2307/1989545, МИСТЕР  1501641.
10. Тутт (1963), Теорема 2.5.
11. Брун, Хеннинг (2004), «Цикловое пространство 3-связного локально конечного графа порождается его конечными и бесконечными периферийными схемами», Журнал комбинаторной теории, Серия B, 92 (2): 235–256, Дои:10.1016 / j.jctb.2004.03.005, МИСТЕР  2099143.
12. Томассен, Карстен; Тофт, Бьярн (1981), "Неразрывные индуцированные циклы в графах", Журнал комбинаторной теории, Серия B, 31 (2): 199–224, Дои:10.1016 / S0095-8956 (81) 80025-1, МИСТЕР  0630983.
13. Шмидт, Йенс М. (2014), «Последовательность Mondshein», Конспект лекций по информатике: 967–978, Дои:10.1007/978-3-662-43948-7_80.
14. Di Battista et al. (1998), Лемма 3.4, с. 75–76.
15. Сеймур, П. Д.; Уивер, Р. В. (1984), "Обобщение хордовых графов", Журнал теории графов, 8 (2): 241–251, Дои:10.1002 / jgt.3190080206, МИСТЕР  0742878.
16. Например. видеть Borse, Y.M .; Waphare, Б. Н. (2008), "Непересекающиеся неразделяющие циклы вершин в графах", Журнал Индийского математического общества, Новая серия, 75 (1–4): 75–92 (2009), МИСТЕР  2662989.
17. Например. видеть Кабельо, Серджио; Мохар, Боян (2007), «Поиск кратчайших неразрывных и несжимаемых циклов для топологически вложенных графов», Дискретная и вычислительная геометрия, 37 (2): 213–235, Дои:10.1007 / s00454-006-1292-5, МИСТЕР  2295054.
18. Майя, Браулио, младший; Лемос, Маноэль; Мело, Тереза ​​Р. Б. (2007), "Неразрывные схемы и кокосхемы в матроидах", Комбинаторика, сложность и случайность, Oxford Lecture Ser. Математика. Appl., 34, Оксфорд: Oxford Univ. Press, стр. 162–171, Дои:10.1093 / acprof: oso / 9780198571278.003.0010, МИСТЕР  2314567.