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

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

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

Визначення

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

$C$ є периферійним циклом, якщо він є простим циклом у зв'язному графі з властивістю, за якої для будь-яких двох ребер $e_{1}$ і $e_{2}$ в $G ∖ C$ , існує шлях у $G$ , який починається в $e_{1}$ , закінчується в $e_{2}$ і не має внутрішніх точок, що належать $C$ Шаблон:Sfn.
$C$ є периферійним циклом, якщо він є породженим циклом із властивістю, за якої підграф $G ∖ C$ , утворений видаленням ребер і вершин циклу $C$ , зв'язний.^[1]
Якщо $C$ є будь-яким підграфом графа $G$ , міст^[2] графа $C$ є мінімальним підграфом $B$ графа $G$ , який не має спільних ребер з $C$ і має властивість, за якої всі його точки приєднання (вершини, суміжні ребрам, які належать $B$ і $G ∖ B$ одночасно) належать $C$ Шаблон:Sfn. Простий цикл $C$ є периферійним, якщо він має рівно один міст^[3]

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

Властивості

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

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

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

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

Пов'язані поняття

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

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

Примітки

Шаблон:Примітки

Література

Шаблон:Бібліоінформація

↑ Це визначення використав Брун Шаблон:Harvard citation. Однак, Брун відрізняв випадок, що $G$ має ізольовані вершини, від незв'язності, викликаної видаленням циклу $C$ .
↑ Не плутати з мостом, іншим поняттям з такою ж назвою.
↑ Це визначення периферійних циклів спочатку використав ТаттШаблон:Harvard citation. Сеймур і ВіверШаблон:Harvard citation використали таке саме визначення периферійного циклу, але з іншим визначенням моста, яке нагадує визначення породжених циклів для периферійних циклів.
↑ Див., наприклад, теорему 2.4 у статті Татта Шаблон:Harvard citation, яка показує, що множини вершин мостів пов'язані шляхами, див. статтю Сеймур і Вівера Шаблон:Harvard citation для визначення мостів за допомогою хорд і зв'язних компонент, а також статтю Ді Баттіста, Ідса, Тамассіа, ТоллісаШаблон:Harvard citation для визначення мостів за допомогою класів еквівалентності бінарного відношення на ребрах.
↑ Див. зауваження після теореми 2.8 у статті Татта Шаблон:Harvard citation. Як зауважив Татт, це було вже відомо Вітні Шаблон:Harvard citation
↑ Див., наприклад, Шаблон:Harvard citation
↑ Див., наприклад Шаблон:Harvard citation

[1] Це визначення використав Брун Шаблон:Harvard citation. Однак, Брун відрізняв випадок, що $G$ має ізольовані вершини, від незв'язності, викликаної видаленням циклу $C$ .

[2] Не плутати з мостом, іншим поняттям з такою ж назвою.

[3] Це визначення периферійних циклів спочатку використав ТаттШаблон:Harvard citation. Сеймур і ВіверШаблон:Harvard citation використали таке саме визначення периферійного циклу, але з іншим визначенням моста, яке нагадує визначення породжених циклів для периферійних циклів.

[4] Див., наприклад, теорему 2.4 у статті Татта Шаблон:Harvard citation, яка показує, що множини вершин мостів пов'язані шляхами, див. статтю Сеймур і Вівера Шаблон:Harvard citation для визначення мостів за допомогою хорд і зв'язних компонент, а також статтю Ді Баттіста, Ідса, Тамассіа, ТоллісаШаблон:Harvard citation для визначення мостів за допомогою класів еквівалентності бінарного відношення на ребрах.

[5] Див. зауваження після теореми 2.8 у статті Татта Шаблон:Harvard citation. Як зауважив Татт, це було вже відомо Вітні Шаблон:Harvard citation

[6] Див., наприклад, Шаблон:Harvard citation

[7] Див., наприклад Шаблон:Harvard citation

[1]

[2]

[3]

[4]

[5]

[6]

[7]

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

Зміст

Визначення

Властивості

Пов'язані поняття

Примітки

Література

Навігаційне меню

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

Визначення

Властивості

Пов'язані поняття

Примітки

Література

Навігаційне меню

Пошук