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

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

Периферийный цикл в неориентированном графе — цикл, который не отделяет любую часть графа от любой другой. Периферийные циклы (или, как они сначала назывались, периферийные многоугольники, поскольку Татт назвал циклы «многоугольниками»), первым изучал Татт, Уильям ТомасШаблон:Sfn. Периферийные циклы играют важную роль в описании планарных графов и в образовании циклических пространств непланарных графовШаблон:Sfn.

Определения

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

• $C$ является периферийным циклом, если он является простым циклом в связном графе со свойством, при котором для любых двух рёбер $e_1$ и $e_2$ в $G\setminus C$, существует путь в $G$, который начинается в $e_1$, кончается в $e_2$ и не имеет внутренних точек, принадлежащих $C$Шаблон:Sfn.
• $C$ является периферийным циклом, если он является порождённым циклом со свойством, при котором подграф $G\setminus C$, образованный удалением рёбер и вершин цикла $C$ связен.
• Если $C$ является любым подграфом графа $G$, мост графа $C$ является минимальным подграфом $B$ графа $G$, не имеющим общих рёбер с $C$ и имеющим свойство, при котором все его точки присоединения (вершины, смежные рёбрам, принадлежащим $B$ и $G\setminus B$ одновременно) принадлежит $C$Шаблон:Sfn. Простой цикл $C$ является периферийным, если он имеет в точности один мост

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

Свойства

Периферийные циклы появляются в теории полиэдральных графов, то есть, вершинно 3-связных планарных графов. Для любого планарного графа $G$ и любого планарного вложения $G$ грани вложения, порождённые циклами, должны быть периферийными циклами. В полиэдральном графе все грани являются периферийными циклами и любой периферийный цикл является граньюШаблон:Sfn. Отсюда следует, что (до комбинаторной эквивалентности, выбора внешней грани и ориентации плоскости) любой полиэдральный граф имеет уникальное планарное вложение.

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

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

Обобщая хордальные графы, Сеймур и Вивер Шаблон:Sfn определили сжатый граф как граф, в котором любой периферийный цикл является треугольником. Они описали эти графы как суммы по кликам хордальных графов и максимальных планарных графовШаблон:Sfn.

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

Периферийные циклы назывались также неразделяющими цикламиШаблон:Sfn, но этот термин двусмысленный, поскольку он используется еще для двух других понятий — для простых циклов, удаление которых делает оставшийся граф несвязным, и для циклов топологического вложения графа, таких, что вырезание вдоль цикла не делает несвязной поверхность, в которую граф вложен.

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

Литература

• Шаблон:Статья
• Шаблон:Книга
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Книга
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Книга