Простір циклів
Про́стір ци́клів (або цикловий простір) неорієнтованого графа — лінійний простір над полем , що складається з його ейлерових підграфів. Розмірність цього простору називають контурним рангом графа. З точки зору алгебричної топології цикловий простір є першою групою гомологій графа.
Кістяковим підграфом заданого графа називають його підграф , такий що множина вершин збігається з множиною вершин . Таким чином, будь-який граф з ребрами має кістякових підграфів на наборі вершин графа , включно із самим і порожнім графом. Сімейство всіх кістякових підграфів утворює реберний простір даного графа. Граф називають ейлеровим якщо кожній його вершині інцидентне парне число ребер (іншими словами, степінь будь-якої вершини графа парна). Сімейство всіх ейлерових кістякових підграфів утворює простір циклів даного графа[1][2].
Реберний простір будь-якого графа замкнутий відносно теоретико-множинних операцій, тому він утворює булеву алгебру[3]. Циклові простори також мають алгебричну структуру: об'єднання або перетин ейлерових підграфів може не бути ейлеровим, але їх симетрична різниця буде. Це пов'язано з тим, що симетрична різниця множин з парним набором елементів (окіл вершини в першому і в другому підграфах) також містить парну множину елементів.
Сімейство множин, замкнуте відносно симетричної різниці можна алгебрично описати векторним простором над двоелементним скінченним полем [4]. Це поле складається з двох елементів, і , а додавання і множення відповідають логічним операціям виключне «або» і кон'юнкція (додавання і множення за модулем 2). У просторі циклів векторами будуть ейлерові підграфи, їх додаванню відповідає симетрична різниця, множенню на скаляр — тотожне відображення, а множення на скаляр перетворює будь-який підграф на порожній, який відповідає нульовому вектору простору циклів.
Реберний простір також є векторним простором над з операцією симетричної різниці як додаванням. Простір циклів і простір розрізів[5] є ортогональними доповненнями один одного всередині реберного простору. Це означає, що множина ребер є розрізом якщо і тільки якщо будь-який ейлерів підграф містить парне число ребер з і, навпаки, множина є ейлеровим підграфом якщо і тільки якщо будь-який розріз містить парне число ребер з . Хоча ці простори і є ортогональними доповненнями один одного, у них може бути нетривіальний перетин. У загальному випадку, граф має непорожній ейлерів розріз якщо і тільки якщо число його кістякових лісів парне[6].
Неорієнтований граф можна розглядати як симпліційний комплекс, чиї вершини є нуль-вимірними симплексами, а ребра — одновимірними симплексами[7]. Ланцюговий комплекс такого топологічного простору складається з його реберного і вершинного просторів, пов'язаних граничним оператором, який переводить будь-який кістяковий підграф (елемент реберного простору) в його множину вершин непарного степеня (елемент вершинного простору). Група гомологий складається з елементів реберного простору, які переводяться граничним оператором у нульовий елемент вершинного простору, тобто, з ейлерових підграфів. Відповідно, груповою операцією тут є симетрична різниця ейлерових графів.
Визначення циклового простору можна розширити заміною довільним кільцем, отримана група гомологій буде модулем над даним кільцем[8]. Зокрема, цілочисельним цикловим простором називають групу гомологій . У теоретико-графових термінах такий простір можна визначити заданням орієнтації на графі і визначенням цілочисельного циклу як набору цілих чисел, присвоєних ребрам графа так, що в будь-якій вершині сума чисел, присвоєних ребрам, які входять у неї, дорівнює сумі чисел, присвоєних ребрам, які виходять з неї. Відповідно, цілочисельний цикловий простір складається з усіх цілочисельних циклів, а додаванню векторів у цьому просторі буде відповідати додавання чисел, присвоєних кожному ребру окремо[9].
Елемент або (циклового простору за модулем ) з додатковою умовою, що всі присвоєні числа є ненульовими, називають ніде не нульовими потоками[10].
Розмірність простору циклів графа з вершинами, ребрами та компонентами зв'язності дорівнює [11]. Це число можна топологічно інтерпретувати як перше число Бетті графа[7]. В теорії графів воно також відоме як цикловий ранг і цикломатичне число. З того, що простір циклів є векторним простором над двоелементним полем, випливає, що загальна кількість елементів простору циклів дорівнює .
Базис простору циклів є сімейством з ейлерових підграфів, таких, що будь-який ейлерів підграф можна подати у вигляді симетричної різниці деякого набору базисних циклів.
За теоремою Веблена[12] будь-який ейлерів підграф можна розкласти в суму простих циклів — підграфів, усі ребра якої утворюють одну компоненту зв'язності, всі вершини якої мають степінь . Таким чином, завжди є базис, всі елементи якого є простими циклами. Такий базис називають базисом циклів цього графа. Більше того, завжди можна побудувати такий базис, що всі його елементи будуть породженими циклами (тобто циклами без хорд у початковому графі)[13].
Щоб побудувати базис циклів можна сконструювати кістяковий ліс графа, а потім для кожного ребра , що не належить лісу сформувати цикл , що складається з разом зі шляхом в кістяковому лісі, що сполучає кінці ребра. Множина сформованих таким чином циклів є лінійно незалежною (оскільки кожен цикл містить ребро , яке не належить іншим циклам) і складається з циклів, тому гарантовано є базисом. Побудований таким чином базис називають фундаментальним базисом циклів.
Базис називають слабко фундаментальним, якщо на множині циклів можна встановити лінійний порядок, такий, що кожен цикл містить хоча б одне ребро, яке не міститься в жодному з попередніх циклів. Будь-який фундаментальний базис циклів є слабко фундаментальним (для будь-яких порядків), протилежне хибне. Існують графи, деякі з базисів циклів яких не є слабко фундаментальними[14].
Нехай кожному ребру графа присвоєно дійсне число, зване його вагою, а вага будь-якого підграфа визначається як сума ваг ребер, що входять до нього. Базис найменшої ваги у просторі циклів мусить бути базисом циклів і його можливо побудувати за поліноміальний час[9]. При цьому такий базис може не бути слабко фундаментальним і задача пошуку слабко фундаментального базису найменшої ваги є NP-складною[14].
Критерій планарності Маклейна характеризує планарні графи у термінах із простору циклів та базису циклів. Критерій стверджує, що скінченний неорієнтований граф є планарним якщо і тільки якщо він має базис циклів, у якому кожне ребро графа міститься в не більше, ніж двох циклах. Таким базисом для планарного графа є межі граней у його укладці, оскільки кожне ребро міститься лише у межах двох граней, які воно відокремлює. Відповідно, якщо граф має базис циклів із такою властивістю, то його елементи можна використати як межі граней укладки графа[15][16].
Простір циклів планарного графа є простором розрізів двоїстого до нього графа, і навпаки. Базис найменшої ваги в планарному графі не обов'язково збігається з базисом із меж його граней, описаним вище. Однак, у планарного графа завжди є базис найменшої ваги, в якому жодні два базисні цикли не перетинаються. З двоїстості просторів циклів і розрізів випливає, що такий базис циклів планарного графа відповідає дереву Гоморі — Ху двоїстого графа, яке задає базис найменшої ваги в його просторі розрізів[17].
У планарних графах розфарбування з різними кольорами двоїсті ніде не нульовим потокам над полем залишків за модулем . Різниця між номерами кольорів сусідніх граней у цій двоїстості є значенням потоку, що тече ребром, яке відокремлює ці грані. Зокрема, існування ніде не нульового 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.
- ↑ Тут під розрізом графа мають на увазі множину ребер , таку що множину вершин можна розбити на дві неперетинні підмножини і , такі що .
- ↑ 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
