Базис циклів

Симетрична різниця двох циклів у ейлеровому підграфі

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

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

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

Визначення

Кістякове дерево заданого графа $G$ має той самий набір вершин, що й сам $G$ але, можливо, менше ребер. Кажуть, що граф $G$, або один з його підграфів, є ейлеровим, якщо кожна його вершина має парний степінь (тобто число інцидентних вершин ребер). Будь-який простий цикл у графі є ейлеровим підграфом, але можуть існувати й інші ейлерові підграфи. Простір циклів графа — це набір його ейлерових підграфів. Вони утворюють векторний простір над скінченним полем із двох елементів. Додавання векторів відповідає симетричній різниці двох або більше підграфів, яка утворює інший підграф, що складається з ребер, які входять непарне число разів у аргументи операції симетричної різниці.

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

Спеціальні базиси циклів

Вивчалися деякі спеціальні типи базисів циклів, серед них фундаментальні базиси циклів, слабкі фундаментальні базиси циклів, розріджені (або 2-) базиси циклів і цілі базиси циклів.

Породжені цикли

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

Фундаментальні цикли

Якщо $T$ — кістякове дерево або кістяковий ліс даного графа $G$ і $e$ — ребро, що не належить $T$, то фундаментальний цикл $C_{e}$, визначений ребром $e$ — це простий цикл, що складається з $e$ разом зі шляхом у $T$, що з'єднує кінцеві вершини $e$. Існує рівно $m-n+c$ фундаментальних циклів, рівно по одному для кожного ребра, що не належить $T$. Кожен з них лінійно незалежний від решти, оскільки містить ребро $e$, що не належить жодному іншому фундаментальному циклу. Таким чином, фундаментальні цикли утворюють базис простору циклів. Базис циклів, побудований таким способом, називають фундаментальним базисом циклів або строго фундаментальним базисом циклів.

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

Слабко фундаментальні цикли

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

Цикли граней

Якщо зв'язний скінченний планарний граф вкладено в площину, кожна грань вкладення оточена циклом ребер. Одна грань буде необмеженою (вона містить точки, довільно далекі від вершин графа), інші грані будуть обмеженими. Згідно з формулою Ейлера, існує рівно $m-n+1$ обмежених граней.

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

Для графів, правильно вкладених на інші поверхні в такий спосіб, що всі грані топологічно є дисками, у загальному випадку необов'язково існує базис циклів, що складається лише з циклів граней. Цикли граней цих вкладень дають потрібну підмножину всіх ейлерових підграфів. Група гомологій $H_{2}(S,\mathbb {Z} _{2})$ заданої поверхні $S$ описує ейлерові підграфи, які не можна подати у вигляді меж набору граней. Критерій планарності Маклейна використовує цю ідею для опису планарних графів у термінах базисів циклів — скінченний неорієнтований граф є планарним тоді й лише тоді, коли він має розріджений базис циклів (або 2-базис), базис, у якому кожне ребро графа належить максимум двом циклам базису. У планарному графі базис циклів, утворений множиною обмежених граней, обов'язково розріджений, і навпаки — розріджений базис циклів будь-якого графа обов'язково утворює множину обмежених граней планарного вкладення графа.

Цілі базиси

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

Найменша вага

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

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

Алгоритми поліноміального часу

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

Гортон (Horton, 1987) запропонував перший алгоритм поліноміального часу для пошуку базису з найменшою вагою в графах, у яких всі ваги більші за нуль. Його алгоритм використовує той же підхід «отримати і перевірити», але число циклів, що переглядаються, обмежується невеликою множиною розміру $O(mn)$ — ці цикли називають циклами Гортона. Цикл Гортона — це фундаментальний цикл дерева найкоротших шляхів графа. Існує n різних дерев найкоротших шляхів (по одному для кожної кореневої вершини) і кожне дерево має не більше від m фундаментальних циклів, що дає загальну кількість циклів Гортона. Як показав Гортон, будь-який цикл у базисі циклів найменшої ваги є циклом Гортона.

Якщо використати алгоритм Дейкстри для пошуку кожного найкоротшого дерева шляхів, а потім для кроків перевірки базового жадібного алгоритму використати виключення Гауса, отримаємо алгоритм поліноміального часу для базису циклів найменшої ваги.

Подальші дослідження дали покращені алгоритми для цієї задачі, що зменшують часову складність найгіршого випадку для знаходження базису циклів найменшої ваги до $O(m^{2}n/\log n)$, де $m$ — число ребер графа, а $n$ — число вершин .

NP-складність

Пошук фундаментального базису найменшої можливої ваги тісно пов'язаний із задачею пошуку кістякового дерева, яке мінімізує середні попарні відстані — обидві задачі NP-складні. Пошук найменшого за вагою слабкого фундаментального базису також NP-складний і апроксимація MAXSNP-складна. Якщо дозволено від'ємні ваги і цикли з від'ємною вагою, то пошук базису циклів найменшої ваги (без обмежень) також NP-складний, оскільки його можна використати для пошуку гамільтонового циклу — якщо граф гамільтонів, і задати всім ребрам вагу −1, базис циклів найменшої ваги міститиме принаймні один гамільтонів цикл.

У планарних графах

Базис циклів з найменшою вагою для планарного графа не обов'язково збігається з базисом, утвореним межами граней — він може містити цикли, що не відповідають граням, а також деякі грані можуть бути відсутніми як цикли в базисі з найменшою вагою. Однак існує базис циклів найменшої ваги, в якому ніякі два цикли не перетинають один одного — для будь-яких двох циклів у цьому базисі або цикли охоплюють неперетинні підмножини граней, або один з двох циклів охоплює інший. Ця множина циклів відповідає в двоїстому графі даного планарного графа множині розрізів, які утворюють дерево Гоморі — Ху двоїстого графа, найменший за вагою базис простору розрізів. На основі цієї двоїстості, явне подання базису циклів найменшої ваги для планарного графа можна побудувати за час $O(n\log ^{4}n)$.

Застосування

Базиси циклів використовують для розв'язування задач періодичного планування, як-от задача планування систем громадського транспорту. У цій задачі цикли базису відповідають змінним цілочисельного програмування, яке використовують для розв'язання задачі.

У теоріях структурної жорсткості та кінематики базиси циклів використовують для побудови системи ненадмірної системи рівнянь, яку можна розв'язати з метою перевірки жорсткості структури. У цій задачі базис циклів найменшої або близької до найменшої ваги приводить до простіших систем рівнянь.

У розподілених обчисленнях базиси циклів використовують для аналізу кількості кроків, необхідних для стабілізування алгоритму.

У біоінформатиці базиси циклів використовують для визначення з даних генотипу інформації про гаплотип. Базис циклів також використовують для аналізу третинної структури РНК.

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

Література

• Reinhard Diestel. 1.9 Some linear algebra // [1] — Springer, 2012. — Т. 173. — С. 23–28. — (Graduate Texts in Mathematics) Архівовано з джерела 2 травня 2019
• David M. Chickering, Dan Geiger, David Heckerman. On finding a cycle basis with a shortest maximal cycle // Information Processing Letters. — 1995. — Т. 54, вип. 1. — С. 55–58. — DOI:10.1016/0020-0190(94)00231-M.
• J. D. Horton. A polynomial-time algorithm to find the shortest cycle basis of a graph // SIAM Journal on Computing. — 1987. — Т. 16, вип. 2. — С. 358–366. — DOI:10.1137/0216026.
• S. Mac Lane. A combinatorial condition for planar graphs // Fundamenta Mathematicae. — 1937. — Т. 28. — С. 22–32. Архівовано з джерела 20 січня 2022. Процитовано 3 травня 2022.
• Oswald Veblen. An application of modular equations in analysis situs // Annals of Mathematics. — 1912. — Т. 14, вип. 1. — С. 86–94. — (Second Series).
• Franziska Berger, Peter Gritzmann, Sven de Vries. Minimum cycle bases for network graphs // Algorithmica. — 2004. — Т. 40, вип. 1. — С. 51–62. — DOI:10.1007/s00453-004-1098-x.
• Kurt Mehlhorn, Dimitrios Michail. Implementing minimum cycle basis algorithms // ACM Journal of Experimental Algorithmics. — 2006. — Т. 11. — DOI:10.1145/1187436.1216582.
• Telikepalli Kavitha, Kurt Mehlhorn, Dimitrios Michail, Katarzyna E. Paluch. An ${\tilde {O}}(m^{2}n)$ algorithm for minimum cycle basis of graphs // Algorithmica. — 2008. — Т. 52, вип. 3. — С. 333–349. — DOI:10.1007/s00453-007-9064-z.
• Telikepalli Kavitha, Christian Liebchen, Kurt Mehlhorn, Dimitrios Michail, Romeo Rizzi, Torsten Ueckerdt, Katharina A. Zweig. Cycle bases in graphs: Characterization, algorithms, complexity, and applications // Computer Science Review. — 2009. — Т. 3, вип. 4. — С. 199–243. — DOI:10.1016/j.cosrev.2009.08.001.
• W. T. Tutte. How to draw a graph // Proceedings of the London Mathematical Society. — 1963. — Т. 13. — С. 743–767. — (Third Series). — DOI:10.1112/plms/s3-13.1.743.
• D. W. Cribb, R. D. Ringeisen, D. R. Shier. Proceedings of the Twelfth Southeastern Conference on Combinatorics, Graph Theory and Computing, Vol. I (Baton Rouge, La., 1981). — 1981. — Т. 32. — С. 221–229. — (Congressus Numerantium)
• David Hartvigsen, Eitan Zemel. Is every cycle basis fundamental? // Journal of Graph Theory. — 1989. — Т. 13, вип. 1. — С. 117–137. — DOI:10.1002/jgt.3190130115.
• David Hartvigsen, Russell Mardon. The all-pairs min cut problem and the minimum cycle basis problem on planar graphs // SIAM Journal on Discrete Mathematics. — 1994. — Т. 7, вип. 3. — С. 403–418. — DOI:10.1137/S0895480190177042.
• Edoardo Amaldi, Claudio Iuliano, Romeo Rizzi. Integer Programming and Combinatorial Optimization: 14th International Conference, IPCO 2010, Lausanne, Switzerland, June 9-11, 2010, Proceedings. — Springer, 2010. — Т. 6080. — С. 397–410. — (Lecture Notes in Computer Science) — DOI:10.1007/978-3-642-13036-6_30.
• Giulia Galbiati, Edoardo Amaldi. Approximation and Online Algorithms: First International Workshop, WAOA 2003, Budapest, Hungary, September 16-18, 2003, Revised Papers. — Berlin : Springer, 2004. — Т. 2909. — С. 151–164. — (Lecture Notes in Computer Science) — DOI:10.1007/978-3-540-24592-6_12.
• Narsingh Deo, G. M. Prabhu, M. S. Krishnamoorthy. Algorithms for generating fundamental cycles in a graph // ACM Transactions on Mathematical Software. — 1982. — Т. 8, вип. 1. — С. 26–42. — DOI:10.1145/355984.355988.
• Glencora Borradaile, Piotr Sankowski, Christian Wulff-Nilsen. Proc. 51st Annual IEEE Symposium on Foundations of Computer Science (FOCS 2010). — IEEE Computer Soc., Los Alamitos, CA, 2010. — С. 601–610. — DOI:10.1109/FOCS.2010.63.
• Christian Liebchen, Romeo Rizzi. Classes of cycle bases // Discrete Applied Mathematics. — 2007. — Т. 155, вип. 3. — С. 337–355. — DOI:10.1016/j.dam.2006.06.007.
• Christian Liebchen. Periodic timetable optimization in public transport // Operations Research Proceedings. — 2007. — Т. 2006. — С. 29–36. — DOI:10.1007/978-3-540-69995-8_5.
• A. C. Cassell, J. C. De Henderson, A. Kaveh. Cycle bases for the flexibility analysis of structures // International Journal for Numerical Methods in Engineering. — 1974. — Т. 8, вип. 3. — С. 521–528. — DOI:10.1002/nme.1620080308.
• Christian Boulinier, Franck Petit, Vincent Villain. Proceedings of the Twenty-third Annual ACM Symposium on Principles of Distributed Computing (PODC '04). — New York, NY, USA : ACM, 2004. — С. 150–159. — DOI:10.1145/1011767.1011790.
• Derek Aguiar, Sorin Istrail. HapCompass: A Fast Cycle Basis Algorithm for Accurate Haplotype Assembly of Sequence Data // Journal of Computational Biology. — 2012. — Т. 19, вип. 6. — С. 577–590. — DOI:10.1089/cmb.2012.0084.
• Sébastien Lemieux, François Major. Automated extraction and classification of RNA tertiary structure cyclic motifs // Nucleic Acids Research. — 2006. — Т. 34, вип. 8. — С. 2340–2346. — DOI:10.1093/nar/gkl120.
• Sébastien Lemieux, François Major. Automated extraction and classification of RNA tertiary structure cyclic motifs // Nucleic Acids Research. — 2006. — Т. 34, вип. 8. — С. 2340–2346. — DOI:10.1093/nar/gkl120.
• Craig Gotsman, Kanela Kaligosi, Kurt Mehlhorn, Dimitrios Michail, Evangelia Pyrga. Cycle bases of graphs and sampled manifolds // Computer Aided Geometric Design. — 2007. — Т. 24, вип. 8—9. — С. 464–480. — DOI:10.1016/j.cagd.2006.07.001.
• Jonathan L. Gross, Jay Yellen. 4.6 Graphs and Vector Spaces // [2] — 2nd. — CRC Press, 2005. — С. 197–207. — ISBN 9781584885054. Архівовано з джерела 2 травня 2019
• Romeo Rizzi. Minimum weakly fundamental cycle bases are hard to find // Algorithmica. — 2009. — Т. 53, вип. 3. — С. 402–424. — DOI:10.1007/s00453-007-9112-8.