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

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

Эквивалентность этих определений нетрудно увидеть: связный подграф графа (вместе с рёбрами, связывающими его с ) или хорда цикла, которая нарушает порождение цикла, в любом случае должен быть мостом, и должен быть также класс эквивалентности бинарного отношения на рёбрах, в котором два ребра связаны, если они являются концами пути без внутренних вершин в См., например, теорему 2.4 в статье Татта , показывающую, что множество вершин мостов связаны путями, см. статью Сеймур и Вивера для определения мостов с помощью хорд и связных компонент, а также статью Ди Баттиста, Идса, Тамассиа, Толлиса для определения мостов с помощью классов эквивалентности бинарного отношения на рёбрах.

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

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

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

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

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

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

Примечания

Литература

Категория:Объекты теории графов Категория:Планарные графы