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

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

Визначення

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

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

Алгебра

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

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

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

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

Топологія

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

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

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

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

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

Базис циклів

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

Існування

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

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

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

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

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

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

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

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

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

Двоїстість

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

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

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