Базис циклів

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

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

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

Визначення

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

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

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

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

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

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

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

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

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

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

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

Цикли граней

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

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

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

Цілі базиси

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Примітки

Шаблон:Примітки

Література

↑ Шаблон:Harvnb, с. 32, 65.
↑ Шаблон:Harvnb. Див., зокрема, теорему 2.5.
↑ ^3,0 ^3,1 Шаблон:Harvnb, с. 105—106.

[1] Шаблон:Harvnb, с. 32, 65.

[2] Шаблон:Harvnb. Див., зокрема, теорему 2.5.

[d106-3] 3,0 ^3,1 Шаблон:Harvnb, с. 105—106.

[1]

[2]

[3]