Простір циклів: відмінності між версіями

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку
Наступне редагування →
Вилучено вміст Додано вміст
ВізуальнийВікірозмітка
Створено шляхом перекладу сторінки «Пространство циклов»
(Немає відмінностей)

Версія за 06:58, 3 травня 2022

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

Визначення

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

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

Алгебра

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

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

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

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

Топологія

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

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

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

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

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

Базис циклів

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

Існування

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

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

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

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

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

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

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

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

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

Двоїстість

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

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

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

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

Примітки

  1. ↑ Joshi, K. D. (1997), Applied Discrete Structures, New Age International, с. 172, ISBN 9788122408263.
  2. ↑ Wallis, W. D. (2010), A Beginner's Guide to Graph Theory, Springer, с. 66, ISBN 9780817645809.
  3. ↑ Тут під розрізом графа мають на увазі множину ребер , таку що множину вершин можна розбити на дві неперетинні підмножини і , такі що .
  4. ↑ 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 Архівна копія на сайті Wayback Machine.
  5. ↑ а б Serre, Jean-Pierre (2003), Trees, Springer Monographs in Mathematics, Springer, с. 23, ISBN 9783540442370
  6. ↑ Biggs, Norman (1993), Algebraic Graph Theory, Cambridge Mathematical Library, Cambridge University Press, с. 154, ISBN 9780521458979
  7. ↑ а б 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
  8. ↑ Seymour, P. D. (1995), Nowhere-zero flows, Handbook of combinatorics, Vol. 1, 2, Amsterdam: Elsevier, с. 289—299, MR 1373660
  9. ↑ Berge, Claude (2001), Cyclomatic number, The Theory of Graphs, Courier Dover Publications, с. 27—30, ISBN 9780486419756
  10. ↑ 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
  11. ↑ Помилка скрипту: Функції «harvard_core» не існує., pp. 32, 65.
  12. ↑ а б 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
  13. ↑ Помилка скрипту: Функції «harvard_core» не існує., pp. 105—106.
  14. ↑ 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
  15. ↑ Thomas, Robin (1999), Recent Excluded Minor Theorems for Graphs, Surveys in Combinatorics, 1999 (PDF), Cambridge University Press, с. 201—222 Архівна копія на сайті Wayback Machine.
Отримано з https://uk.wikipedia.org/w/index.php?title=Простір_циклів&oldid=35568836