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

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

Периферійний цикл ${\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}$^[3].
• ${\displaystyle C}$ є периферійним циклом, якщо він є породженим циклом із властивістю, за якої підграф ${\displaystyle G\setminus C}$, утворений видаленням ребер і вершин циклу ${\displaystyle C}$, зв'язний.^[4]
• Якщо ${\displaystyle C}$ є будь-яким підграфом графа ${\displaystyle G}$, міст^[5] графа ${\displaystyle C}$ є мінімальним підграфом ${\displaystyle B}$ графа ${\displaystyle G}$, який не має спільних ребер з ${\displaystyle C}$ і має властивість, за якої всі його точки приєднання (вершини, суміжні ребрам, які належать ${\displaystyle B}$ і ${\displaystyle G\setminus B}$ одночасно) належать ${\displaystyle C}$^[6]. Простий цикл ${\displaystyle C}$ є периферійним, якщо він має рівно один міст^[7]

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

Периферійні цикли з'являються в теорії багатогранних графів, тобто, вершинно 3-зв'язних планарних графів. Для будь-якого планарного графа ${\displaystyle G}$ і будь-якого планарного вкладення ${\displaystyle G}$ межі вкладення, породжені циклами, мають бути периферійними циклами. У багатогранному графі всі грані є периферійними циклами і будь-який периферійний цикл є гранню^[9]. Звідси випливає, що (до комбінаторної еквівалентності, вибору зовнішньої грані та орієнтації площини) будь-який багатогранний граф має унікальне планарне вкладення^[10].

У планарних графах простір циклів утворений гранями, але в непланарних графах периферійні цикли відіграють аналогічну роль — для будь-якого вершинно 3-зв'язаного скінченного графа циклічний простір утворюють периферійні цикли^[11]. Результат можна поширити на локально скінченні нескінченні графи^[12]. Зокрема, звідси випливає, що 3-зв'язні графи гарантовано містять периферійні цикли. Існують 2-зв'язні графи, які не містять периферійних циклів (прикладом є повний двочастковий граф ${\displaystyle K_{2,4}}$, в якому будь-який цикл має два мости), але, якщо 2-зв'язний граф має мінімальний степінь 3, то він містить принаймні один периферійний цикл^[13].

Периферійні цикли в 3-зв'язних графах можна обчислити за лінійний час, їх використовують для розробки тестів планарності^[14]. Їх також розширено до загальнішого поняття нерозділювальних вушних розкладів. У деяких алгоритмах для перевірки планарності графів корисно знайти цикл, який не є периферійним, з метою розбиття задачі на менші підзадачі. У двозв'язному графі з контурним рангом, меншим від 3, (такому як цикл або тета-граф), будь-який цикл є периферійним, але будь-який двозв'язний граф з контурним рангом 3 і більше має непериферійний цикл, який можна знайти за лінійний час^[15].

Узагальнюючи хордальні графи, Сеймур і Вівер ^[16] визначили стиснутий граф як граф, у якому будь-який периферійний цикл є трикутником. Вони описали ці графи як суми за кліками хордальних графів і максимальних планарних графів^[17].

Периферійні цикли називали також нерозділювальними циклами^[3], але цей термін двозначний, оскільки він використовується ще для двох інших понять — для простих циклів, видалення яких робить решту графа незв'язною^[18], і для циклів топологічного вкладення графа, таких, що вирізання вздовж циклу не робить незв'язною поверхню, в яку граф укладено^[19].

У матроїдах, нерозділювальний цикл — це цикл матроїда (тобто, мінімальна залежна множина), за якої видалення^[en] циклу залишає менший матроїд, який є зв'язним (тобто, який не можна розбити на пряму суму матроїдів)^[20]. Він аналогічний периферійним циклам, але не тотожний навіть у графових матроїдах^[en] (матроїди, в яких цикли є простими циклами графа). Наприклад, у повному двочастковому графі ${\displaystyle K_{2,3}}$ будь-який цикл є периферійним (він має лише один міст, шлях із двох ребер), але графовий матроїд, утворений цим мостом не зв'язний, так що ніякий цикл графового матроїда графа ${\displaystyle K_{2,3}}$ не є нерозділювальним.

• Tutte W. T. How to draw a graph // Proceedings of the London Mathematical Society. — 1963. — Т. 13. — С. 743–767. — (Third Series). — DOI:10.1112/plms/s3-13.1.743.
• Giuseppe Di Battista, Peter Eades, Roberto Tamassia, Ioannis G. Tollis. Graph Drawing: Algorithms for the Visualization of Graphs. — Prentice Hall, 1998. — С. 74–75. — ISBN 978-0-13-301615-4.
• Tutte W. T. Convex representations of graphs // Proceedings of the London Mathematical Society. — 1960. — Т. 10. — С. 304–320. — (Third Series). — DOI:10.1112/plms/s3-10.1.304.
• Hassler Whitney^[en]. Non-separable and planar graphs // Transactions of the American Mathematical Society. — 1932. — Т. 34, вип. 2. — С. 339–362. — DOI:10.2307/1989545.
• Henning Bruhn. The cycle space of a 3-connected locally finite graph is generated by its finite and infinite peripheral circuits // Journal of Combinatorial Theory. — 2004. — Т. 92, вип. 2. — С. 235–256. — (Series B). — DOI:10.1016/j.jctb.2004.03.005.
• Carsten Thomassen, Bjarne Toft. Non-separating induced cycles in graphs // Journal of Combinatorial Theory. — 1981. — Т. 31, вип. 2. — С. 199–224. — (Series B). — DOI:10.1016/S0095-8956(81)80025-1.
• Jens M. Schmidt. The Mondshein Sequence // Proceedings of the 41st International Colloquium on Automata, Languages and Programming (ICALP'14). — 2014. — С. 967—978. — DOI:10.1007/978-3-662-43948-7_80.
• Seymour P. D., Weaver R. W. A generalization of chordal graphs // Journal of Graph Theory. — 1984. — Т. 8, вип. 2. — С. 241–251. — DOI:10.1002/jgt.3190080206.
• Borse Y. M., Waphare B. N. Vertex disjoint non-separating cycles in graphs // The Journal of the Indian Mathematical Society. — 2008. — Т. 75, вип. 1—4. — С. 75–92 (2009). — (New Series).
• Sergio Cabello, Bojan Mohar. Finding shortest non-separating and non-contractible cycles for topologically embedded graphs // Discrete and Computational Geometry. — 2007. — Т. 37, вип. 2. — С. 213–235. — DOI:10.1007/s00454-006-1292-5.
• Bráulio Maia Junior, Manoel Lemos, Tereza R. B. Melo. Non-separating circuits and cocircuits in matroids // Combinatorics, complexity, and chance. — Oxford : Oxford Univ. Press, 2007. — Т. 34. — С. 162–171. — (Oxford Lecture Ser. Math. Appl.) — DOI:10.1093/acprof:oso/9780198571278.003.0010.