Основа цикла

В теории графов , разделе математики, базис циклов неориентированного графа — это набор простых циклов , который образует базис пространства циклов графа. То есть это минимальный набор циклов, который позволяет четной степени выразить каждый подграф как симметричную разность базисных циклов.

Базис фундаментального цикла может быть сформирован из любого остовного дерева или остовного леса данного графа путем выбора циклов, образованных комбинацией пути в дереве и одного ребра вне дерева. Альтернативно, если ребра графа имеют положительные веса, базис цикла с минимальным весом может быть построен за полиномиальное время .

В плоских графах множество ограниченных циклов вложения графа образует базис цикла. Базис цикла минимального веса плоского графа соответствует дереву Гомори – Ху двойственного графа .

Определения

данного Охватывающий подграф графа G имеет тот же набор вершин, что и сам G , но, возможно, меньше ребер. Граф G или один из его подграфов называется эйлеровым , если каждая из его вершин имеет четную степень (количество инцидентных ему ребер). Каждый простой цикл в графе является эйлеровым подграфом, но могут быть и другие. Пространство циклов графа — это совокупность его эйлеровых подграфов. Он образует векторное пространство над двухэлементным конечным полем . Операция сложения векторов — это симметричная разность двух или более подграфов, которая образует другой подграф, состоящий из ребер, которые появляются нечетное количество раз в аргументах операции симметричной разности. ^{[ 1 ]}

Базис цикла — это базис этого векторного пространства, в котором каждый базисный вектор представляет собой простой цикл. Он состоит из набора циклов, которые можно комбинировать, используя симметричные разности, для формирования любого эйлерова подграфа, и это минимально с учетом этого свойства. Каждый цикловый базис данного графа имеет одинаковое количество циклов, равное размерности его пространства циклов. Это число называется схемным рангом графа и равно $m-n+c$ где $m$ количество ребер в графе, $n$ - количество вершин, а $c$ — число связных компонентов . ^{[ 2 ]}

Специальные велобазы

Было изучено несколько специальных типов базисов циклов, включая фундаментальные базисы циклов, слабо фундаментальные базисы циклов, разреженные (или 2-) базисы циклов и целочисленные базисы циклов. ^{[ 3 ]}

Индуцированные циклы

Каждый граф имеет циклический базис, в котором каждый цикл является индуцированным циклом . В 3-вершинно-связном графе всегда существует базис, состоящий из периферийных циклов , циклов, удаление которых не отделяет оставшийся граф. ^{[ 4 ]}^{[ 5 ]} В любом графе, кроме графа, образованного добавлением одного ребра к циклу, периферийный цикл должен быть индуцированным циклом.

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

Если $T$ является остовным деревом или остовным лесом данного графа $G$ , и $e$ представляет собой ребро, не принадлежащее $T$ , то фундаментальный цикл $C_{e}$ определяется $e$ – простой цикл, состоящий из $e$ вместе с дорогой в $T$ соединяя конечные точки $e$ . Есть точно $m-n+c$ фундаментальные циклы, по одному на каждое ребро, не принадлежащее $T$ . Каждый из них линейно независим от остальных циклов, поскольку включает в себя ребро $e$ этого нет ни в одном другом фундаментальном цикле. Таким образом, фундаментальные циклы составляют основу пространства циклов. ^{[ 1 ]}^{[ 2 ]} Построенный таким образом базис цикла называется фундаментальным базисом цикла или сильно фундаментальным базисом цикла . ^{[ 3 ]}

Также возможно охарактеризовать фундаментальные базисы циклов без указания дерева, для которого они являются фундаментальными. Существует дерево, для которого данный базис цикла является фундаментальным тогда и только тогда, когда каждый цикл содержит ребро, не входящее ни в один другой базисный цикл, т. е. каждый цикл независим от других. Отсюда следует, что совокупность циклов представляет собой фундаментальную циклическую основу $G$ тогда и только тогда, когда он обладает свойством независимости и имеет правильное количество циклов, чтобы быть базисом $G$ . ^{[ 6 ]}

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

Базис цикла называется слабофундаментальным , если его циклы можно расположить в линейном порядке так, что каждый цикл включает хотя бы одно ребро, не входящее ни в один более ранний цикл. Фундаментальный базис цикла автоматически является слабо фундаментальным (при любом порядке ребер). ^{[ 3 ]}^{[ 7 ]} Если каждый цикловый базис графа является слабо фундаментальным, то же самое верно для каждого минора графа. На основании этого свойства класс графов (и мультиграфов ), для которых каждый базис цикла является слабо фундаментальным, можно охарактеризовать пятью запрещенными минорами : графом квадратной пирамиды , мультиграфом, образованным удвоением всех ребер четырехвершинного цикла, два мультиграфа, образованные удвоением двух ребер тетраэдра , и мультиграф, образованный удвоением ребер треугольника. ^{[ 8 ]}

Лицевые циклы

Если связный конечный планарный граф вложен в плоскость, каждая грань вложения ограничена циклом ребер. Одна грань обязательно неограничена (в нее входят точки, сколь угодно удаленные от вершин графа), а остальные грани ограничены. По формуле Эйлера для плоских графов существует ровно $m-n+1$ ограниченные лица. Симметричная разность любого набора гранных циклов является границей соответствующего набора граней, а разные наборы ограниченных граней имеют разные границы, поэтому невозможно представить один и тот же набор как симметричную разность гранных циклов более чем в одном способ; это означает, что множество гранных циклов линейно независимо. Как линейно независимый набор достаточного количества циклов, он обязательно образует базис цикла. ^{[ 9 ]} Это всегда слабо фундаментальный базис цикла, и он фундаментален тогда и только тогда, когда вложение графа является внешнепланарным .

Для графов, правильно вложенных в другие поверхности, так что все грани вложения являются топологическими дисками, в общем случае неверно, что существует базис циклов, использующий только циклы граней. Циклы граней этих вложений порождают собственное подмножество всех эйлеровых подграфов. Группа гомологии $H_{2}(S,\mathbb {Z} _{2})$ заданной поверхности $S$ характеризует эйлеровы подграфы, которые нельзя представить как границу множества граней. Критерий планарности Мак Лейна использует эту идею для характеристики плоских графов с точки зрения базисов циклов: конечный неориентированный граф является планарным тогда и только тогда, когда он имеет разреженный цикловый базис или 2-базис . ^{[ 3 ]} базис, в котором каждое ребро графа участвует не более чем в двух базисных циклах. В плоском графе базис циклов, образованный набором ограниченных граней, обязательно разрежен, и наоборот, разреженный базис циклов любого графа обязательно образует набор ограниченных граней плоского вложения его графа. ^{[ 9 ]}^{[ 10 ]}

Интегральные основы

Пространство циклов графа можно интерпретировать с помощью теории гомологии как группу гомологий. $H_{1}(G,\mathbb {Z} _{2})$ симплициального комплекса с точкой для каждой вершины графа и отрезком для каждого ребра графа. Эту конструкцию можно обобщить на группу гомологий $H_{1}(G,R)$ над произвольным кольцом $R$ . Важным частным случаем является кольцо целых чисел , для которого группа гомологий $H_{1}(G,\mathbb {Z} )$ — свободная абелева группа , подгруппа свободной абелевой группы, порожденная ребрами графа. Менее абстрактно, эту группу можно построить, присвоив произвольную ориентацию ребрам данного графа; тогда элементы $H_{1}(G,\mathbb {Z} )$ представляют собой маркировку ребер графа целыми числами со свойством, что в каждой вершине сумма меток входящих ребер равна сумме меток исходящих ребер. Групповая операция – это сложение этих векторов меток. Целочисленный базис цикла — это набор простых циклов, порождающий эту группу. ^{[ 3 ]}

Минимальный вес

Если ребрам графа присвоены вещественные веса, вес подграфа можно вычислить как сумму весов его ребер. Базис минимального веса пространства циклов обязательно является базисом цикла: по теореме Веблена , ^{[ 11 ]} каждый эйлеров подграф, который сам по себе не является простым циклом, можно разложить на несколько простых циклов, которые обязательно имеют меньший вес.

По стандартным свойствам базисов в векторных пространствах и матроидах базис цикла минимального веса не только минимизирует сумму весов своих циклов, но и любую другую монотонную комбинацию весов циклов. Например, именно базис цикла минимизирует вес самого длинного цикла. ^{[ 12 ]}

Алгоритмы с полиномиальным временем

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

Хортон (1987) предложил первый алгоритм с полиномиальным временем для поиска базиса минимального веса в графах, для которых вес каждого ребра положителен. Его алгоритм использует подход «генерация и тестирование», но ограничивает генерируемые циклы небольшим набором циклов. $O(mn)$ циклы, называемые циклами Хортона . Цикл Хортона — это фундаментальный цикл дерева кратчайших путей данного графа. Существует не более n различных деревьев кратчайших путей (по одному на каждую начальную вершину), и каждое из них имеет менее m фундаментальных циклов, что дает ограничение на общее количество циклов Хортона. Как показал Хортон, каждый цикл в базисе цикла минимального веса является циклом Хортона. ^{[ 13 ]} Использование алгоритма Дейкстры для поиска каждого дерева кратчайших путей, а затем использование метода исключения Гаусса для выполнения этапов тестирования жадного базисного алгоритма приводит к алгоритму полиномиального времени для базиса цикла минимального веса. Последующие исследователи разработали улучшенные алгоритмы решения этой проблемы. ^{[ 14 ]}^{[ 15 ]}^{[ 16 ]}^{[ 17 ]} уменьшение временной сложности в наихудшем случае для нахождения базиса минимального весового цикла в графе с $m$ края и $n$ вершины в $O(m^{2}n/\log n)$ . ^{[ 18 ]}

NP-твердость

Поиск фундаментального базиса с минимально возможным весом тесно связан с проблемой поиска остовного дерева, минимизирующего среднее значение попарных расстояний; оба NP-сложные . ^{[ 19 ]} Нахождение минимального веса в слабофундаментальном базисе также NP-трудно, ^{[ 7 ]} и аппроксимация его MAXSNP-трудна . ^{[ 20 ]} Если разрешены отрицательные веса и циклы с отрицательным весом, то поиск минимального базиса цикла (без ограничений) также является NP-трудным, поскольку его можно использовать для поиска гамильтонова цикла : если граф гамильтонов и всем ребрам присвоен вес — 1, то базис минимального весового цикла обязательно включает хотя бы один гамильтонов цикл.

В планарных графах

Базис цикла минимального веса для плоского графа не обязательно совпадает с базисом, образованным его ограниченными гранями: он может включать циклы, которые не являются гранями, а некоторые грани могут не включаться как циклы в базис цикла минимального веса. Однако существует базис цикла с минимальным весом, в котором никакие два цикла не пересекаются: для каждых двух циклов в базисе либо циклы заключают в себе непересекающиеся подмножества ограниченных граней, либо один из двух циклов заключает в себе другой. Этот набор циклов соответствует в двойственном графе данного планарного графа набору разрезов , которые образуют дерево Гомори – Ху двойственного графа, базис минимального веса его пространства разрезов . ^{[ 21 ]} На основе этой двойственности можно построить неявное представление базиса цикла с минимальным весом в плоском графе во времени. $O(n\log ^{3}n)$ . ^{[ 22 ]}

Приложения

Базы циклов использовались для решения периодических задач планирования, таких как проблема определения расписания системы общественного транспорта. В этом приложении циклы базиса циклов соответствуют переменным в целочисленной программе решения задачи. ^{[ 23 ]}

В теории жесткости и кинематики конструкций основы циклов используются для руководства процессом создания системы неизбыточных уравнений, которые можно решить для прогнозирования жесткости или движения конструкции. В этом приложении базисы минимального или почти минимального весового цикла приводят к более простым системам уравнений. ^{[ 24 ]}

В распределенных вычислениях базы циклов использовались для анализа количества шагов, необходимых для стабилизации алгоритма. ^{[ 25 ]}

В биоинформатике основания циклов использовались для определения информации о гаплотипах на основе данных последовательности генома. ^{[ 26 ]} использовались для анализа третичной структуры РНК Основания цикла также . ^{[ 27 ]}

Базис минимального весового цикла графа ближайших соседей точек, выбранных с трехмерной поверхности, может использоваться для реконструкции поверхности. ^{[ 28 ]}

В хемоинформатике базис минимального цикла молекулярного графа называется наименьшим набором наименьших колец . ^{[ 29 ]}^{[ 30 ]}^{[ 31 ]}

Ссылки

^ Перейти обратно: ^а ^б Дистель, Рейнхард (2012), «1.9 Некоторые линейные алгебры» , Теория графов , Тексты для выпускников по математике, том. 173, Спрингер, стр. 23–28 .
^ Перейти обратно: ^а ^б Гросс, Джонатан Л.; Йеллен, Джей (2005), «4.6 Графы и векторные пространства» , Теория графов и ее приложения (2-е изд.), CRC Press, стр. 197–207, ISBN 9781584885054 .
^ Перейти обратно: ^а ^б ^с ^д ^и Либхен, Кристиан; Рицци, Ромео (2007), «Классы базисов циклов», Дискретная прикладная математика , 155 (3): 337–355, doi : 10.1016/j.dam.2006.06.007 , MR 2303157 .
^ Дистель (2012) , стр. 32, 65.
^ Тутте, WT (1963), «Как нарисовать график», Труды Лондонского математического общества , третья серия, 13 : 743–767, doi : 10.1112/plms/s3-13.1.743 , MR 0158387 . См., в частности, теорему 2.5.
^ Крибб, Д.В.; Рингейзен, РД; Шир, Д. Р. (1981), «О циклических базисах графа», Труды двенадцатой Юго-восточной конференции по комбинаторике, теории графов и вычислениям, Vol. I (Батон-Руж, Луизиана, 1981) , Congressus Numerantium, vol. 32, стр. 221–229, МР 0681883 .
^ Перейти обратно: ^а ^б Рицци, Ромео (2009), «Трудно найти минимальные слабо фундаментальные основания цикла», Algorithmica , 53 (3): 402–424, doi : 10.1007/s00453-007-9112-8 , MR 2482112 , S2CID 12675654 .
^ Хартвигсен, Дэвид; Земель, Эйтан (1989), «Является ли каждый базис цикла фундаментальным?», Journal of Graph Theory , 13 (1): 117–137, doi : 10.1002/jgt.3190130115 , MR 0982873 .
^ Перейти обратно: ^а ^б Дистель (2012) , стр. 105–106.
^ Мак Лейн, С. (1937), «Комбинаторное условие для плоских графов» (PDF) , Fundamentals of Mathematics , 28 : 22–32, doi : 10.4064/fm-28-1-22-32 .
^ Веблен, Освальд (1912), «Применение модульных уравнений в анализе ситуации», Annals of Mathematics , Second Series, 14 (1): 86–94, doi : 10.2307/1967604 , JSTOR 1967604 .
^ Чикеринг, Дэвид М.; Гейгер, Дэн; Хекерман, Дэвид (1995), «О поиске базиса цикла с кратчайшим максимальным циклом», Information Processing Letters , 54 (1): 55–58, CiteSeerX 10.1.1.650.8218 , doi : 10.1016/0020-0190(94) 00231-М , МР 1332422 .
^ Хортон, JD (1987), «Алгоритм с полиномиальным временем для поиска базиса кратчайшего цикла графа», SIAM Journal on Computing , 16 (2): 358–366, doi : 10.1137/0216026 .
^ Бергер, Франциска; Грицманн, Питер; де Врис, Свен (2004), «Минимальные базисы циклов для сетевых графов», Algorithmica , 40 (1): 51–62, doi : 10.1007/s00453-004-1098-x , MR 2071255 , S2CID 9386078 .
^ Мельхорн, Курт ; Михаил, Димитриос (2006), «Реализация базовых алгоритмов минимального цикла» , ACM Journal of Experimental Algorithmics , 11 :2.5, CiteSeerX 10.1.1.60.1087 , doi : 10.1145/1187436.1216582 , S2CID 6198296 .
^ Кавита, Телекоммуникации ; Мельхорн, Курт ; Майкл, Димитриос; Палух, Катажина Е. (2008), "Ан ${\tilde {O}}(m^{2}n)$ Алгоритм для базиса минимального цикла графов», Algorithmica , 52 (3): 333–349, doi : 10.1007/s00453-007-9064-z , MR 2452919 .
^ Кавита, Теликепалли; Либхен, Кристиан; Мельхорн, Курт ; Михаил, Димитриос; Рицци, Ромео; Юкердт, Торстен; Цвейг, Катарина А. (2009), «Базы циклов в графах: характеристика, алгоритмы, сложность и приложения» , Computer Science Review , 3 (4): 199–243, doi : 10.1016/j.cosrev.2009.08.001 .
^ Амальди, Эдоардо; Юлиано, Клаудио; Рицци, Ромео (2010), «Эффективные детерминированные алгоритмы для поиска базиса минимального цикла в неориентированных графах», Целочисленное программирование и комбинаторная оптимизация: 14-я международная конференция, IPCO 2010, Лозанна, Швейцария, 9–11 июня 2010 г., Материалы лекций , конспекты лекций в области компьютерных наук, вып. 6080, Springer, стр. 397–410, Bibcode : 2010LNCS.6080..397A , doi : 10.1007/978-3-642-13036-6_30 , ISBN 978-3-642-13035-9 , МР 2661113 .
^ Део, Нарсингх; Прабху, генеральный директор; Кришнамурти, MS (1982), «Алгоритмы генерации фундаментальных циклов в графе», ACM Transactions on Mathematical Software , 8 (1): 26–42, doi : 10.1145/355984.355988 , MR 0661120 , S2CID 2260051 .
^ Гальбьяти, Джулия; Амальди, Эдоардо (2004), «Об аппроксимации задачи базиса минимального фундаментального цикла», Приближение и онлайн-алгоритмы: первый международный семинар, WAOA 2003, Будапешт, Венгрия, 16–18 сентября 2003 г., Переработанные статьи , Конспекты лекций по компьютеру Наука, том. 2909, Берлин: Springer, стр. 151–164, doi : 10.1007/978-3-540-24592-6_12 , ISBN. 978-3-540-21079-5 , МР 2089904 .
^ Хартвигсен, Дэвид; Мардон, Рассел (1994), «Проблема минимального разреза для всех пар и задача базиса минимального цикла на плоских графах», SIAM Journal on Discrete Mathematics , 7 (3): 403–418, doi : 10.1137/S0895480190177042 , MR 1285579 .
^ Боррадейл, Гленкора; Эппштейн, Дэвид ; Найери, Амир; Вульф-Нильсен, Кристиан (2016), «Минимальные сокращения для всех пар за почти линейное время для графов, встроенных в поверхность», Proc. 32-й Международный Симп. Вычислительная геометрия , Международные труды Лейбница по информатике (LIPIcs), том. 51, Schloss Dagstuhl, стр. 22:1–22:16, arXiv : 1411.7055 , doi : 10.4230/LIPIcs.SoCG.2016.22 , S2CID 215762172 .
^ Либхен, Кристиан (2007), «Периодическая оптимизация расписания общественного транспорта», Operations Research Proceedings 2006 , vol. 2006, стр. 29–36, номер документа : 10.1007/978-3-540-69995-8_5 , ISBN. 978-3-540-69994-1 .
^ Касселл, AC; Де Хендерсон, JC; Каве, А. (1974), «Основы цикла для анализа гибкости конструкций», Международный журнал численных методов в инженерии , 8 (3): 521–528, Бибкод : 1974IJNME...8..521C , doi : 10.1002 /nme.1620080308 .
^ Булинье, Кристиан; Пети, Франк; Злодей, Винсент (2004), «Когда теория графов помогает самостабилизации», Труды двадцать третьего ежегодного симпозиума ACM по принципам распределенных вычислений (PODC '04) , Нью-Йорк, Нью-Йорк, США: ACM, стр. 150– 159, CiteSeerX 10.1.1.79.2190 , doi : 10.1145/1011767.1011790 , ISBN 978-1581138023 , S2CID 14936510 .
^ Агиар, Дерек; Истраил, Сорин (2012), «HapCompass: базисный алгоритм быстрого цикла для точной сборки гаплотипов данных последовательностей», Journal of Computational Biology , 19 (6): 577–590, doi : 10.1089/cmb.2012.0084 , PMC 3375639 , PMID 22697235 .
^ Лемье, Себастьян; Майор, Франсуа (2006), «Автоматическое извлечение и классификация циклических мотивов третичной структуры РНК», Nucleic Acids Research , 34 (8): 2340–2346, doi : 10.1093/nar/gkl120 , PMC 1458283 , PMID 16679452 .
^ Гоцман, Крейг; Калигоси, Корица; Мельхорн, Курт ; Михаил, Деметриус; Евангелия (2007), «Циклические базы графов и выборочных многообразий», , 24 ( 8–9): 464–480 CiteSeerX Компьютерное геометрическое проектирование , Пирга , 001 , MR 2359763 .
^ Мэй, Джон В.; Стейнбек, Кристоф (2014), «Эффективное восприятие кольца для набора для разработки химии», Journal of Cheminformatics , 6 (3): 3, doi : 10.1186/1758-2946-6-3 , PMC 3922685 , PMID 24479757
^ Даунс, генеральный менеджер; Жилле, виджей; Холлидей, Джей Ди; Линч, М.Ф. (1989), «Обзор алгоритмов восприятия колец для химических графов», J. Chem. Инф. Вычислить. наук. , 29 (3): 172–187, doi : 10.1021/ci00063a007
^ Замора, А. (1979), «Алгоритм поиска наименьшего набора наименьших колец», J. Chem. Инф. Вычислить. наук. , 16 (1): 40–43, doi : 10.1021/ci60005a013

[diestel-1] Перейти обратно: ^а ^б Дистель, Рейнхард (2012), «1.9 Некоторые линейные алгебры» , Теория графов , Тексты для выпускников по математике, том. 173, Спрингер, стр. 23–28 .

[gy-2] Перейти обратно: ^а ^б Гросс, Джонатан Л.; Йеллен, Джей (2005), «4.6 Графы и векторные пространства» , Теория графов и ее приложения (2-е изд.), CRC Press, стр. 197–207, ISBN 9781584885054 .

[classes-3] Перейти обратно: ^а ^б ^с ^д ^и Либхен, Кристиан; Рицци, Ромео (2007), «Классы базисов циклов», Дискретная прикладная математика , 155 (3): 337–355, doi : 10.1016/j.dam.2006.06.007 , MR 2303157 .

[4] Дистель (2012) , стр. 32, 65.

[5] Тутте, WT (1963), «Как нарисовать график», Труды Лондонского математического общества , третья серия, 13 : 743–767, doi : 10.1112/plms/s3-13.1.743 , MR 0158387 . См., в частности, теорему 2.5.

[6] Крибб, Д.В.; Рингейзен, РД; Шир, Д. Р. (1981), «О циклических базисах графа», Труды двенадцатой Юго-восточной конференции по комбинаторике, теории графов и вычислениям, Vol. I (Батон-Руж, Луизиана, 1981) , Congressus Numerantium, vol. 32, стр. 221–229, МР 0681883 .

[rizzi-7] Перейти обратно: ^а ^б Рицци, Ромео (2009), «Трудно найти минимальные слабо фундаментальные основания цикла», Algorithmica , 53 (3): 402–424, doi : 10.1007/s00453-007-9112-8 , MR 2482112 , S2CID 12675654 .

[8] Хартвигсен, Дэвид; Земель, Эйтан (1989), «Является ли каждый базис цикла фундаментальным?», Journal of Graph Theory , 13 (1): 117–137, doi : 10.1002/jgt.3190130115 , MR 0982873 .

[d106-9] Перейти обратно: ^а ^б Дистель (2012) , стр. 105–106.

[10] Мак Лейн, С. (1937), «Комбинаторное условие для плоских графов» (PDF) , Fundamentals of Mathematics , 28 : 22–32, doi : 10.4064/fm-28-1-22-32 .

[11] Веблен, Освальд (1912), «Применение модульных уравнений в анализе ситуации», Annals of Mathematics , Second Series, 14 (1): 86–94, doi : 10.2307/1967604 , JSTOR 1967604 .

[12] Чикеринг, Дэвид М.; Гейгер, Дэн; Хекерман, Дэвид (1995), «О поиске базиса цикла с кратчайшим максимальным циклом», Information Processing Letters , 54 (1): 55–58, CiteSeerX 10.1.1.650.8218 , doi : 10.1016/0020-0190(94) 00231-М , МР 1332422 .

[13] Хортон, JD (1987), «Алгоритм с полиномиальным временем для поиска базиса кратчайшего цикла графа», SIAM Journal on Computing , 16 (2): 358–366, doi : 10.1137/0216026 .

[14] Бергер, Франциска; Грицманн, Питер; де Врис, Свен (2004), «Минимальные базисы циклов для сетевых графов», Algorithmica , 40 (1): 51–62, doi : 10.1007/s00453-004-1098-x , MR 2071255 , S2CID 9386078 .

[15] Мельхорн, Курт ; Михаил, Димитриос (2006), «Реализация базовых алгоритмов минимального цикла» , ACM Journal of Experimental Algorithmics , 11 :2.5, CiteSeerX 10.1.1.60.1087 , doi : 10.1145/1187436.1216582 , S2CID 6198296 .

[16] Кавита, Телекоммуникации ; Мельхорн, Курт ; Майкл, Димитриос; Палух, Катажина Е. (2008), "Ан ${\tilde {O}}(m^{2}n)$ Алгоритм для базиса минимального цикла графов», Algorithmica , 52 (3): 333–349, doi : 10.1007/s00453-007-9064-z , MR 2452919 .

[17] Кавита, Теликепалли; Либхен, Кристиан; Мельхорн, Курт ; Михаил, Димитриос; Рицци, Ромео; Юкердт, Торстен; Цвейг, Катарина А. (2009), «Базы циклов в графах: характеристика, алгоритмы, сложность и приложения» , Computer Science Review , 3 (4): 199–243, doi : 10.1016/j.cosrev.2009.08.001 .

[18] Амальди, Эдоардо; Юлиано, Клаудио; Рицци, Ромео (2010), «Эффективные детерминированные алгоритмы для поиска базиса минимального цикла в неориентированных графах», Целочисленное программирование и комбинаторная оптимизация: 14-я международная конференция, IPCO 2010, Лозанна, Швейцария, 9–11 июня 2010 г., Материалы лекций , конспекты лекций в области компьютерных наук, вып. 6080, Springer, стр. 397–410, Bibcode : 2010LNCS.6080..397A , doi : 10.1007/978-3-642-13036-6_30 , ISBN 978-3-642-13035-9 , МР 2661113 .

[19] Део, Нарсингх; Прабху, генеральный директор; Кришнамурти, MS (1982), «Алгоритмы генерации фундаментальных циклов в графе», ACM Transactions on Mathematical Software , 8 (1): 26–42, doi : 10.1145/355984.355988 , MR 0661120 , S2CID 2260051 .

[20] Гальбьяти, Джулия; Амальди, Эдоардо (2004), «Об аппроксимации задачи базиса минимального фундаментального цикла», Приближение и онлайн-алгоритмы: первый международный семинар, WAOA 2003, Будапешт, Венгрия, 16–18 сентября 2003 г., Переработанные статьи , Конспекты лекций по компьютеру Наука, том. 2909, Берлин: Springer, стр. 151–164, doi : 10.1007/978-3-540-24592-6_12 , ISBN. 978-3-540-21079-5 , МР 2089904 .

[21] Хартвигсен, Дэвид; Мардон, Рассел (1994), «Проблема минимального разреза для всех пар и задача базиса минимального цикла на плоских графах», SIAM Journal on Discrete Mathematics , 7 (3): 403–418, doi : 10.1137/S0895480190177042 , MR 1285579 .

[22] Боррадейл, Гленкора; Эппштейн, Дэвид ; Найери, Амир; Вульф-Нильсен, Кристиан (2016), «Минимальные сокращения для всех пар за почти линейное время для графов, встроенных в поверхность», Proc. 32-й Международный Симп. Вычислительная геометрия , Международные труды Лейбница по информатике (LIPIcs), том. 51, Schloss Dagstuhl, стр. 22:1–22:16, arXiv : 1411.7055 , doi : 10.4230/LIPIcs.SoCG.2016.22 , S2CID 215762172 .

[23] Либхен, Кристиан (2007), «Периодическая оптимизация расписания общественного транспорта», Operations Research Proceedings 2006 , vol. 2006, стр. 29–36, номер документа : 10.1007/978-3-540-69995-8_5 , ISBN. 978-3-540-69994-1 .

[24] Касселл, AC; Де Хендерсон, JC; Каве, А. (1974), «Основы цикла для анализа гибкости конструкций», Международный журнал численных методов в инженерии , 8 (3): 521–528, Бибкод : 1974IJNME...8..521C , doi : 10.1002 /nme.1620080308 .

[25] Булинье, Кристиан; Пети, Франк; Злодей, Винсент (2004), «Когда теория графов помогает самостабилизации», Труды двадцать третьего ежегодного симпозиума ACM по принципам распределенных вычислений (PODC '04) , Нью-Йорк, Нью-Йорк, США: ACM, стр. 150– 159, CiteSeerX 10.1.1.79.2190 , doi : 10.1145/1011767.1011790 , ISBN 978-1581138023 , S2CID 14936510 .

[26] Агиар, Дерек; Истраил, Сорин (2012), «HapCompass: базисный алгоритм быстрого цикла для точной сборки гаплотипов данных последовательностей», Journal of Computational Biology , 19 (6): 577–590, doi : 10.1089/cmb.2012.0084 , PMC 3375639 , PMID 22697235 .

[27] Лемье, Себастьян; Майор, Франсуа (2006), «Автоматическое извлечение и классификация циклических мотивов третичной структуры РНК», Nucleic Acids Research , 34 (8): 2340–2346, doi : 10.1093/nar/gkl120 , PMC 1458283 , PMID 16679452 .

[28] Гоцман, Крейг; Калигоси, Корица; Мельхорн, Курт ; Михаил, Деметриус; Евангелия (2007), «Циклические базы графов и выборочных многообразий», , 24 ( 8–9): 464–480 CiteSeerX Компьютерное геометрическое проектирование , Пирга , 001 , MR 2359763 .

[29] Мэй, Джон В.; Стейнбек, Кристоф (2014), «Эффективное восприятие кольца для набора для разработки химии», Journal of Cheminformatics , 6 (3): 3, doi : 10.1186/1758-2946-6-3 , PMC 3922685 , PMID 24479757

[30] Даунс, генеральный менеджер; Жилле, виджей; Холлидей, Джей Ди; Линч, М.Ф. (1989), «Обзор алгоритмов восприятия колец для химических графов», J. Chem. Инф. Вычислить. наук. , 29 (3): 172–187, doi : 10.1021/ci00063a007

[31] Замора, А. (1979), «Алгоритм поиска наименьшего набора наименьших колец», J. Chem. Инф. Вычислить. наук. , 16 (1): 40–43, doi : 10.1021/ci60005a013

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]

[ 12 ]

[ 13 ]

[ 14 ]

[ 15 ]

[ 16 ]

[ 17 ]

[ 18 ]

[ 19 ]

[ 20 ]

[ 21 ]

[ 22 ]

[ 23 ]

[ 24 ]

[ 25 ]

[ 26 ]

[ 27 ]

[ 28 ]

[ 29 ]

[ 30 ]

[ 31 ]