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

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

Визначення

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

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

Алгебра

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

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

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

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

Топологія

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

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

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

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

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

Базис циклів

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

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

Існування

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

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

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

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

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

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

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

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

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

Двоїстість

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

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

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

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

Примітки

1. Gross, Jonathan L.; Yellen, Jay (2005), 4.6 Graphs and Vector Spaces, (вид. 2nd), CRC Press, с. 197—207, ISBN , архів оригіналу за 2 травня 2019, процитовано 3 травня 2022.
2. Diestel, Reinhard (2012), 1.9 Some linear algebra, , Graduate Texts in Mathematics, т. 173, Springer, с. 23—28, архів оригіналу за 2 травня 2019, процитовано 3 травня 2022.
3. Joshi, K. D. (1997), Applied Discrete Structures, New Age International, с. 172, ISBN .
4. Wallis, W. D. (2010), A Beginner's Guide to Graph Theory, Springer, с. 66, ISBN .
5. Тут під розрізом графа ${\displaystyle G=(V,E)}$ мають на увазі множину ребер ${\displaystyle S}$, таку що множину вершин ${\displaystyle V}$ можна розбити на дві неперетинні підмножини ${\displaystyle A}$ і ${\displaystyle B}$, такі що ${\displaystyle S=E\cap (A\times B)}$.
6. Eppstein, David (1996), (PDF), Technical Report 96-14, Department of Information and Computer Science, University of California, Irvine, архів оригіналу (PDF) за 5 жовтня 2020, процитовано 3 травня 2022
7. Serre, Jean-Pierre (2003), Trees, Springer Monographs in Mathematics, Springer, с. 23, ISBN 
8. Biggs, Norman (1993), Algebraic Graph Theory, Cambridge Mathematical Library, Cambridge University Press, с. 154, ISBN 
9. Berger, Franziska; Gritzmann, Peter; de Vries, Sven (2009), Minimum cycle bases and their applications, Algorithmics of Large and Complex Networks, Lecture Notes in Computer Science, т. 5515, с. 34—49, doi:10.1007/978-3-642-02094-0_2, ISBN 
10. (1995), Nowhere-zero flows, Handbook of combinatorics, Vol. 1, 2, Amsterdam: Elsevier, с. 289—299, MR 1373660
11. (2001), Cyclomatic number, The Theory of Graphs, Courier Dover Publications, с. 27—30, ISBN 
12. Veblen, Oswald (1912), An application of modular equations in analysis situs, Annals of Mathematics, Second Series, 14 (1): 86—94, doi:10.2307/1967604, JSTOR 1967604
13. Diestel, (2012), pp. 32, 65.
14. Rizzi, Romeo (2009), Minimum weakly fundamental cycle bases are hard to find, Algorithmica, 53 (3): 402—424, doi:10.1007/s00453-007-9112-8, MR 2482112
15. Diestel, (2012), pp. 105—106.
16. (1937), (PDF), Fundamenta Mathematicae, 28: 22—32, архів оригіналу (PDF) за 20 січня 2022, процитовано 3 травня 2022
17. Hartvigsen, David; Mardon, Russell (1994), The all-pairs min cut problem and the minimum cycle basis problem on planar graphs, SIAM Journal on Discrete Mathematics, 7 (3): 403—418, doi:10.1137/S0895480190177042, MR 1285579
18. (1999), Recent Excluded Minor Theorems for Graphs, (PDF), Cambridge University Press, с. 201—222, архів оригіналу (PDF) за 3 серпня 2016, процитовано 3 травня 2022