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

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

Визначення

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

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

Алгебра

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

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

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

Топологія

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

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

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

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

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

Базис циклів

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

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

Існування

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

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

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

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

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

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

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

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

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

Двоїстість

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

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

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

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

Примітки

↑ Gross, Jonathan L.; Yellen, Jay (2005), 4.6 Graphs and Vector Spaces, Graph Theory and Its Applications (вид. 2nd), CRC Press, с. 197—207, ISBN 9781584885054, архів оригіналу за 2 травня 2019, процитовано 3 травня 2022.
↑ Diestel, Reinhard (2012), 1.9 Some linear algebra, Graph Theory, Graduate Texts in Mathematics, т. 173, Springer, с. 23—28, архів оригіналу за 2 травня 2019, процитовано 3 травня 2022.
↑ Joshi, K. D. (1997), Applied Discrete Structures, New Age International, с. 172, ISBN 9788122408263.
↑ Wallis, W. D. (2010), A Beginner's Guide to Graph Theory, Springer, с. 66, ISBN 9780817645809.
↑ Тут під розрізом графа $G=(V,E)$ мають на увазі множину ребер $S$ , таку що множину вершин $V$ можна розбити на дві неперетинні підмножини $A$ і $B$ , такі що $S=E\cap (A\times B)$ .
↑ Eppstein, David (1996), On the Parity of Graph Spanning Tree Numbers (PDF), Technical Report 96-14, Department of Information and Computer Science, University of California, Irvine, архів оригіналу (PDF) за 5 жовтня 2020, процитовано 3 травня 2022
↑ ^а ^б Serre, Jean-Pierre (2003), Trees, Springer Monographs in Mathematics, Springer, с. 23, ISBN 9783540442370
↑ Biggs, Norman (1993), Algebraic Graph Theory, Cambridge Mathematical Library, Cambridge University Press, с. 154, ISBN 9780521458979
↑ ^а ^б 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 978-3-642-02093-3
↑ Seymour, P. D. (1995), Nowhere-zero flows, Handbook of combinatorics, Vol. 1, 2, Amsterdam: Elsevier, с. 289—299, MR 1373660
↑ Berge, Claude (2001), Cyclomatic number, The Theory of Graphs, Courier Dover Publications, с. 27—30, ISBN 9780486419756
↑ 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
↑ Diestel, (2012), pp. 32, 65.
↑ ^а ^б 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
↑ Diestel, (2012), pp. 105—106.
↑ Mac Lane, S. (1937), A combinatorial condition for planar graphs (PDF), Fundamenta Mathematicae, 28: 22—32, архів оригіналу (PDF) за 20 січня 2022, процитовано 3 травня 2022
↑ 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
↑ Thomas, Robin (1999), Recent Excluded Minor Theorems for Graphs, Surveys in Combinatorics, 1999 (PDF), Cambridge University Press, с. 201—222, архів оригіналу (PDF) за 3 серпня 2016, процитовано 3 травня 2022

[gy-1] Gross, Jonathan L.; Yellen, Jay (2005), 4.6 Graphs and Vector Spaces, Graph Theory and Its Applications (вид. 2nd), CRC Press, с. 197—207, ISBN 9781584885054, архів оригіналу за 2 травня 2019, процитовано 3 травня 2022.

[diestel-2] Diestel, Reinhard (2012), 1.9 Some linear algebra, Graph Theory, 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 9788122408263.

[4] Wallis, W. D. (2010), A Beginner's Guide to Graph Theory, Springer, с. 66, ISBN 9780817645809.

[5] Тут під розрізом графа $G=(V,E)$ мають на увазі множину ребер $S$ , таку що множину вершин $V$ можна розбити на дві неперетинні підмножини $A$ і $B$ , такі що $S=E\cap (A\times B)$ .

[6] Eppstein, David (1996), On the Parity of Graph Spanning Tree Numbers (PDF), Technical Report 96-14, Department of Information and Computer Science, University of California, Irvine, архів оригіналу (PDF) за 5 жовтня 2020, процитовано 3 травня 2022

[serre-7] а ^б Serre, Jean-Pierre (2003), Trees, Springer Monographs in Mathematics, Springer, с. 23, ISBN 9783540442370

[8] Biggs, Norman (1993), Algebraic Graph Theory, Cambridge Mathematical Library, Cambridge University Press, с. 154, ISBN 9780521458979

[mcba-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 978-3-642-02093-3

[10] Seymour, P. D. (1995), Nowhere-zero flows, Handbook of combinatorics, Vol. 1, 2, Amsterdam: Elsevier, с. 289—299, MR 1373660

[berge-11] Berge, Claude (2001), Cyclomatic number, The Theory of Graphs, Courier Dover Publications, с. 27—30, ISBN 9780486419756

[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.

[rizzi-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

[d106-15] Diestel, (2012), pp. 105—106.

[16] Mac Lane, S. (1937), A combinatorial condition for planar graphs (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] Thomas, Robin (1999), Recent Excluded Minor Theorems for Graphs, Surveys in Combinatorics, 1999 (PDF), Cambridge University Press, с. 201—222, архів оригіналу (PDF) за 3 серпня 2016, процитовано 3 травня 2022

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]