Основа цикла - Cycle basis

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

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

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

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

Определения

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

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

Базы специального цикла

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

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

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

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

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

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

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

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

Циклы лица

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

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

Интегральные базы

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

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

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

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

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

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

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

NP-твердость

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

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

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

Приложения

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

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

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

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

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

В хеминформатика, базис минимального цикла молекулярный граф называется Самый маленький набор самых маленьких колец (СССР).^[29][30][31]

Рекомендации

1. Дистель, Рейнхард (2012), «1.9 Некоторая линейная алгебра», Теория графов, Тексты для выпускников по математике, 173, Springer, стр. 23–28..
2. Гросс, Джонатан Л .; Йеллен, Джей (2005), «4.6 Графы и векторные пространства», Теория графов и ее приложения (2-е изд.), CRC Press, стр. 197–207, ISBN  9781584885054.
3. Либхен, Кристиан; Рицци, Ромео (2007), "Классы основ цикла", Дискретная прикладная математика, 155 (3): 337–355, Дои:10.1016 / j.dam.2006.06.007, МИСТЕР  2303157.
4. Дистель (2012) С. 32, 65.
5. Тутте, В. Т. (1963), «Как нарисовать график», Труды Лондонского математического общества, Третья серия, 13: 743–767, Дои:10.1112 / плмс / с3-13.1.743, МИСТЕР  0158387. См., В частности, теорему 2.5.
6. Cribb, D.W .; Ringeisen, R.D .; Шиер, Д. Р. (1981), "О циклических базисах графа", Труды Двенадцатой Юго-Восточной конференции по комбинаторике, теории графов и вычислениям, Vol. I (Батон-Руж, штат Луизиана, 1981 г.), Congressus Numerantium, 32, стр. 221–229, МИСТЕР  0681883.
7. Рицци, Ромео (2009), «Трудно найти минимальные основы слабо фундаментального цикла», Алгоритмика, 53 (3): 402–424, Дои:10.1007 / s00453-007-9112-8, МИСТЕР  2482112, S2CID  12675654.
8. Хартвигсен, Дэвид; Земель, Эйтан (1989), «Является ли каждый цикл фундаментальным?», Журнал теории графов, 13 (1): 117–137, Дои:10.1002 / jgt.3190130115, МИСТЕР  0982873.
9. Дистель (2012) С. 105–106.
10. Мак Лейн, С. (1937), «Комбинаторное условие для плоских графов» (PDF), Fundamenta Mathematicae, 28: 22–32.
11. Веблен, Освальд (1912), "Применение модульных уравнений в анализе места", Анналы математики, Вторая серия, 14 (1): 86–94, Дои:10.2307/1967604, JSTOR  1967604.
12. Чикеринг, Дэвид М .; Гейгер, Дэн; Хекерман, Дэвид (1995), «О нахождении основы цикла с кратчайшим максимальным циклом», Письма об обработке информации, 54 (1): 55–58, CiteSeerX  10.1.1.650.8218, Дои:10.1016 / 0020-0190 (94) 00231-М, МИСТЕР  1332422.
13. Хортон, Дж. Д. (1987), "Полиномиальный алгоритм поиска базиса кратчайшего цикла графа", SIAM Журнал по вычислениям, 16 (2): 358–366, Дои:10.1137/0216026.
14. Бергер, Франциска; Грицманн, Питер; де Фрис, Свен (2004), "Минимальный цикл базисов для сетевых графов", Алгоритмика, 40 (1): 51–62, Дои:10.1007 / s00453-004-1098-х, МИСТЕР  2071255, S2CID  9386078.
15. Мельхорн, Курт; Михаил, Димитриос (2006), «Реализация алгоритмов на основе минимального цикла», ACM Журнал экспериментальной алгоритмики, 11: 2.5, Дои:10.1145/1187436.1216582, S2CID  6198296.
16. Кавита, Теликепалли; Мельхорн, Курт; Михаил, Димитриос; Палуч, Катажина Е. (2008), "Ан ${\displaystyle {\tilde {O}}(m^{2}n)}$ алгоритм минимального цикла базиса графов », Алгоритмика, 52 (3): 333–349, Дои:10.1007 / s00453-007-9064-z, МИСТЕР  2452919.
17. Кавита, Теликепалли; Либхен, Кристиан; Мельхорн, Курт; Михаил, Димитриос; Рицци, Ромео; Ueckerdt, Torsten; Цвейг, Катарина А. (2009), «Базы циклов в графах: характеристика, алгоритмы, сложность и приложения», Обзор компьютерных наук, 3 (4): 199–243, Дои:10.1016 / j.cosrev.2009.08.001.
18. Амальди, Эдоардо; Юлиано, Клаудио; Рицци, Ромео (2010), «Эффективные детерминированные алгоритмы для поиска базиса минимального цикла в неориентированных графах», Целочисленное программирование и комбинаторная оптимизация: 14-я международная конференция, IPCO 2010, Лозанна, Швейцария, 9-11 июня 2010 г., Труды, Конспект лекций по информатике, 6080, Springer, стр. 397–410, Bibcode:2010LNCS.6080..397A, Дои:10.1007/978-3-642-13036-6_30, ISBN  978-3-642-13035-9, МИСТЕР  2661113.
19. Део, Нарсингх; Прабху, Г. М .; Кришнамурти, М. С. (1982), "Алгоритмы для генерации фундаментальных циклов в графе", Транзакции ACM на математическом ПО, 8 (1): 26–42, Дои:10.1145/355984.355988, МИСТЕР  0661120, S2CID  2260051.
20. Гальбиати, Джулия; Амальди, Эдоардо (2004), "Об аппроксимируемости проблемы базиса минимального основного цикла", Аппроксимация и онлайн-алгоритмы: первый международный семинар, WAOA 2003, Будапешт, Венгрия, 16-18 сентября 2003 г., исправленные статьи, Конспект лекций по информатике, 2909, Берлин: Springer, стр. 151–164, Дои:10.1007/978-3-540-24592-6_12, ISBN  978-3-540-21079-5, МИСТЕР  2089904.
21. Хартвигсен, Дэвид; Мардон, Рассел (1994), "Проблема минимального разреза всех пар и проблема базиса минимального цикла на плоских графах", Журнал SIAM по дискретной математике, 7 (3): 403–418, Дои:10.1137 / S0895480190177042, МИСТЕР  1285579.
22. Боррадейл, Гленкора; Эппштейн, Дэвид; Найери, Амир; Вульф-Нильсен, Кристиан (2016), «Минимальные разрезы для всех пар за почти линейное время для графов, вложенных в поверхность», Proc. 32-й межд. Symp. Вычислительная геометрия, Международный журнал Лейбница по информатике (LIPIcs), 51, Schloss Dagstuhl, стр. 22: 1–22: 16, arXiv:1411.7055, Дои:10.4230 / LIPIcs.SoCG.2016.22.
23. Либхен, Кристиан (2007), "Оптимизация периодического расписания общественного транспорта", Материалы исследования операций, 2006: 29–36, Дои:10.1007/978-3-540-69995-8_5, ISBN  978-3-540-69994-1.
24. Cassell, A.C .; De Henderson, J.C .; Каве, А. (1974), "Цикл основы для анализа гибкости конструкций", Международный журнал численных методов в инженерии, 8 (3): 521–528, Bibcode:1974IJNME ... 8..521C, Дои:10.1002 / nme.1620080308.
25. Булинье, Кристиан; Пети, Франк; Злодей, Винсент (2004), "Когда теория графов помогает самостабилизации", Материалы двадцать третьего ежегодного симпозиума ACM по принципам распределенных вычислений (PODC '04), Нью-Йорк, Нью-Йорк, США: ACM, стр. 150–159, CiteSeerX  10.1.1.79.2190, Дои:10.1145/1011767.1011790, ISBN  978-1581138023, S2CID  14936510.
26. Агиар, Дерек; Истраил, Сорин (2012), «HapCompass: базовый алгоритм быстрого цикла для точной сборки гаплотипов данных последовательности», Журнал вычислительной биологии, 19 (6): 577–590, Дои:10.1089 / cmb.2012.0084, ЧВК  3375639, PMID  22697235.
27. Лемье, Себастьян; Майор, Франсуа (2006), "Автоматическая экстракция и классификация циклических мотивов третичной структуры РНК", Исследования нуклеиновых кислот, 34 (8): 2340–2346, Дои:10.1093 / нар / gkl120, ЧВК  1458283, PMID  16679452.
28. Гоцман, Крейг; Калигоси, Канела; Мельхорн, Курт; Михаил, Димитриос; Пирга, Евангелия (2007), "Цикл базисов графов и дискретных многообразий", Компьютерный геометрический дизайн, 24 (8–9): 464–480, CiteSeerX  10.1.1.298.9661, Дои:10.1016 / j.cagd.2006.07.001, МИСТЕР  2359763.
29. Мэй, Джон В .; Стейнбек, Кристоф (2014). «Эффективное восприятие кольца для набора для разработки химии». Журнал химинформатики. 6 (3): 3. Дои:10.1186/1758-2946-6-3. ЧВК  3922685. PMID  24479757.
30. Даунс, G.M .; Gillet, V.J .; Холлидей, J.D .; Линч, М.Ф. (1989). "Обзор алгоритмов восприятия кольца для химических графов". J. Chem. Инф. Comput. Sci. 29 (3): 172–187. Дои:10.1021 / ci00063a007.
31. Замора, А. (1979). «Алгоритм поиска наименьшего набора наименьших колец». J. Chem. Инф. Comput. Sci. 16 (1): 40–43. Дои:10.1021 / ci60005a013.