Простір циклів

Про́стір ци́клів (або цикловий простір) неорієнтованого графа — лінійний простір над полем ${\displaystyle \mathbb {F} _{2}}$, що складається з його ейлерових підграфів. Розмірність цього простору називають контурним рангом графа. З точки зору алгебричної топології цикловий простір є першою групою гомологій графа.

Визначення

Теорія графів

Кістяковим підграфом заданого графа ${\displaystyle G}$ називають його підграф ${\displaystyle S}$, такий що множина вершин ${\displaystyle S}$ збігається з множиною вершин ${\displaystyle G}$. Таким чином, будь-який граф з ${\displaystyle m}$ ребрами має ${\displaystyle 2^{m}}$ кістякових підграфів на наборі вершин графа ${\displaystyle G}$, включно із самим ${\displaystyle G}$ і порожнім графом. Сімейство всіх кістякових підграфів ${\displaystyle G}$ утворює реберний простір даного графа. Граф називають ейлеровим якщо кожній його вершині інцидентне парне число ребер (іншими словами, степінь будь-якої вершини графа парна). Сімейство всіх ейлерових кістякових підграфів утворює простір циклів даного графа^[1][2].

Алгебра

Симетрична різниця двох ейлерових підграфів (червоного і зеленого) також є ейлеровим підграфом (синій).

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

Сімейство множин, замкнуте відносно симетричної різниці можна алгебрично описати векторним простором над двоелементним скінченним полем ${\displaystyle \mathbb {F} _{2}}$^[4]. Це поле складається з двох елементів, ${\displaystyle 0}$ і ${\displaystyle 1}$, а додавання і множення відповідають логічним операціям виключне «або» і кон'юнкція (додавання і множення за модулем 2). У просторі циклів векторами будуть ейлерові підграфи, їх додаванню відповідає симетрична різниця, множенню на скаляр ${\displaystyle 1}$ — тотожне відображення, а множення на скаляр ${\displaystyle 0}$ перетворює будь-який підграф на порожній, який відповідає нульовому вектору простору циклів.

Реберний простір також є векторним простором над ${\displaystyle \mathbb {F} _{2}}$ з операцією симетричної різниці як додаванням. Простір циклів і простір розрізів^[5] є ортогональними доповненнями один одного всередині реберного простору. Це означає, що множина ребер ${\displaystyle S}$ є розрізом якщо і тільки якщо будь-який ейлерів підграф містить парне число ребер з ${\displaystyle S}$ і, навпаки, множина ${\displaystyle S}$ є ейлеровим підграфом якщо і тільки якщо будь-який розріз містить парне число ребер з ${\displaystyle S}$. Хоча ці простори і є ортогональними доповненнями один одного, у них може бути нетривіальний перетин. У загальному випадку, граф ${\displaystyle G}$ має непорожній ейлерів розріз якщо і тільки якщо число його кістякових лісів парне^[6].

Топологія

Неорієнтований граф можна розглядати як симпліційний комплекс, чиї вершини є нуль-вимірними симплексами, а ребра — одновимірними симплексами^[7]. Ланцюговий комплекс такого топологічного простору складається з його реберного і вершинного просторів, пов'язаних граничним оператором, який переводить будь-який кістяковий підграф (елемент реберного простору) в його множину вершин непарного степеня (елемент вершинного простору). Група гомологий ${\displaystyle H_{1}(G,\mathbb {F} _{2})}$ складається з елементів реберного простору, які переводяться граничним оператором у нульовий елемент вершинного простору, тобто, з ейлерових підграфів. Відповідно, груповою операцією тут є симетрична різниця ейлерових графів.

Визначення циклового простору можна розширити заміною ${\displaystyle \mathbb {F} _{2}}$ довільним кільцем, отримана група гомологій буде модулем над даним кільцем^[8]. Зокрема, цілочисельним цикловим простором називають групу гомологій ${\displaystyle H_{1}(G,\mathbb {Z} )}$. У теоретико-графових термінах такий простір можна визначити заданням орієнтації на графі і визначенням цілочисельного циклу як набору цілих чисел, присвоєних ребрам графа так, що в будь-якій вершині сума чисел, присвоєних ребрам, які входять у неї, дорівнює сумі чисел, присвоєних ребрам, які виходять з неї. Відповідно, цілочисельний цикловий простір складається з усіх цілочисельних циклів, а додаванню векторів у цьому просторі буде відповідати додавання чисел, присвоєних кожному ребру окремо^[9].

Елемент ${\displaystyle H_{1}(G,\mathbb {Z} )}$ або ${\displaystyle H_{1}(G,\mathbb {Z} _{k})}$ (циклового простору за модулем ${\displaystyle k}$) з додатковою умовою, що всі присвоєні числа є ненульовими, називають ніде не нульовими потоками^[10].

Цикловий ранг

Розмірність простору циклів графа з ${\displaystyle n}$ вершинами, ${\displaystyle m}$ ребрами та ${\displaystyle c}$ компонентами зв'язності дорівнює ${\displaystyle m-n+c}$^[11]. Це число можна топологічно інтерпретувати як перше число Бетті графа^[7]. В теорії графів воно також відоме як цикловий ранг і цикломатичне число. З того, що простір циклів є векторним простором над двоелементним полем, випливає, що загальна кількість елементів простору циклів дорівнює ${\displaystyle 2^{m-n+c}}$.

Базис циклів

Докладніше: Базис циклів

Базис простору циклів є сімейством з ${\displaystyle m-n+c}$ ейлерових підграфів, таких, що будь-який ейлерів підграф можна подати у вигляді симетричної різниці деякого набору базисних циклів.

Існування

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

Фундаментальні та слабко фундаментальні базиси

Щоб побудувати базис циклів можна сконструювати кістяковий ліс графа, а потім для кожного ребра ${\displaystyle e}$, що не належить лісу сформувати цикл ${\displaystyle C_{e}}$, що складається з ${\displaystyle e}$ разом зі шляхом в кістяковому лісі, що сполучає кінці ребра. Множина сформованих таким чином циклів є лінійно незалежною (оскільки кожен цикл містить ребро ${\displaystyle e}$, яке не належить іншим циклам) і складається з ${\displaystyle m-n+c}$ циклів, тому гарантовано є базисом. Побудований таким чином базис називають фундаментальним базисом циклів.

Базис називають слабко фундаментальним, якщо на множині циклів можна встановити лінійний порядок, такий, що кожен цикл містить хоча б одне ребро, яке не міститься в жодному з попередніх циклів. Будь-який фундаментальний базис циклів є слабко фундаментальним (для будь-яких порядків), протилежне хибне. Існують графи, деякі з базисів циклів яких не є слабко фундаментальними^[14].

Базис найменшої ваги

Нехай кожному ребру графа присвоєно дійсне число, зване його вагою, а вага будь-якого підграфа визначається як сума ваг ребер, що входять до нього. Базис найменшої ваги у просторі циклів мусить бути базисом циклів і його можливо побудувати за поліноміальний час^[9]. При цьому такий базис може не бути слабко фундаментальним і задача пошуку слабко фундаментального базису найменшої ваги є NP-складною^[14].

Планарні графи

Критерій планарності Маклейна

Критерій планарності Маклейна характеризує планарні графи у термінах із простору циклів та базису циклів. Критерій стверджує, що скінченний неорієнтований граф є планарним якщо і тільки якщо він має базис циклів, у якому кожне ребро графа міститься в не більше, ніж двох циклах. Таким базисом для планарного графа є межі граней у його укладці, оскільки кожне ребро міститься лише у межах двох граней, які воно відокремлює. Відповідно, якщо граф має базис циклів із такою властивістю, то його елементи можна використати як межі граней укладки графа^[15][16].

Двоїстість

Простір циклів планарного графа є простором розрізів двоїстого до нього графа, і навпаки. Базис найменшої ваги в планарному графі не обов'язково збігається з базисом із меж його граней, описаним вище. Однак, у планарного графа завжди є базис найменшої ваги, в якому жодні два базисні цикли не перетинаються. З двоїстості просторів циклів і розрізів випливає, що такий базис циклів планарного графа відповідає дереву Гоморі — Ху двоїстого графа, яке задає базис найменшої ваги в його просторі розрізів^[17].

Ніде не нульові потоки

Докладніше: Ніде не нульовий потік

У планарних графах розфарбування з ${\displaystyle k}$ різними кольорами двоїсті ніде не нульовим потокам над полем ${\displaystyle \mathbb {Z} _{k}}$ залишків за модулем ${\displaystyle k}$ . Різниця між номерами кольорів сусідніх граней у цій двоїстості є значенням потоку, що тече ребром, яке відокремлює ці грані. Зокрема, існування ніде не нульового 4-потоку в будь-якому планарному графі еквівалентне теоремі про чотири фарби. Теорема про снарки узагальнює цей результат на непланарні графи^[18].