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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку

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

Визначення

[ред. | ред. код]

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

[ред. | ред. код]

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

Алгебра

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

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

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

Реберний простір також є векторним простором над з операцією симетричної різниці як додаванням. Простір циклів і простір розрізів[5] є ортогональними доповненнями один одного всередині реберного простору. Це означає, що множина ребер є розрізом якщо і тільки якщо будь-який ейлерів підграф містить парне число ребер з і, навпаки, множина є ейлеровим підграфом якщо і тільки якщо будь-який розріз містить парне число ребер з . Хоча ці простори і є ортогональними доповненнями один одного, у них може бути нетривіальний перетин. У загальному випадку, граф має непорожній ейлерів розріз якщо і тільки якщо число його кістякових лісів парне[6].

Топологія

[ред. | ред. код]

Неорієнтований граф можна розглядати як симпліційний комплекс, чиї вершини є нуль-вимірними симплексами, а ребра — одновимірними симплексами[7]. Ланцюговий комплекс такого топологічного простору складається з його реберного і вершинного просторів, пов'язаних граничним оператором, який переводить будь-який кістяковий підграф (елемент реберного простору) в його множину вершин непарного степеня (елемент вершинного простору). Група гомологий складається з елементів реберного простору, які переводяться граничним оператором у нульовий елемент вершинного простору, тобто, з ейлерових підграфів. Відповідно, груповою операцією тут є симетрична різниця ейлерових графів.

Визначення циклового простору можна розширити заміною довільним кільцем, отримана група гомологій буде модулем над даним кільцем[8]. Зокрема, цілочисельним цикловим простором називають групу гомологій . У теоретико-графових термінах такий простір можна визначити заданням орієнтації на графі і визначенням цілочисельного циклу як набору цілих чисел, присвоєних ребрам графа так, що в будь-якій вершині сума чисел, присвоєних ребрам, які входять у неї, дорівнює сумі чисел, присвоєних ребрам, які виходять з неї. Відповідно, цілочисельний цикловий простір складається з усіх цілочисельних циклів, а додаванню векторів у цьому просторі буде відповідати додавання чисел, присвоєних кожному ребру окремо[9].

Елемент або (циклового простору за модулем ) з додатковою умовою, що всі присвоєні числа є ненульовими, називають ніде не нульовими потоками[10].

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

[ред. | ред. код]

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

Базис циклів

[ред. | ред. код]
Докладніше: Базис циклів

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

Існування

[ред. | ред. код]

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

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

[ред. | ред. код]

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

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

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

[ред. | ред. код]

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

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

[ред. | ред. код]

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

[ред. | ред. код]

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

Двоїстість

[ред. | ред. код]

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

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

[ред. | ред. код]

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

Примітки

[ред. | ред. код]
  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.
  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. Тут під розрізом графа мають на увазі множину ребер , таку що множину вершин можна розбити на дві неперетинні підмножини і , такі що .
  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
  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
  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
  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.
  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. 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