В теории графов , раздел математики, цикл основа из неориентированного графа представляет собой набор простых циклов , который образует основу из пространства цикла графа. То есть это минимальный набор циклов, который позволяет каждому подграфу четной степени быть выраженным как симметричная разность базисных циклов.
Фундаментальный цикл основа может быть образована из любого покрывающего дерева или остовного леса данного графика, выбрав циклы , образованные сочетанием пути в дереве и одного ребра вне дерева. В качестве альтернативы, если ребра графа имеют положительные веса, базис цикла с минимальным весом может быть построен за полиномиальное время .
В планарных графах множество ограниченных циклов вложения графа образует базис цикла. Минимальный вес цикла основе плоского графа соответствует дерево Гомори-Ху из двойственного графа .
Определения
Охватывающий подграф данного графа G имеет тот же набор вершин как G самого , но, возможно, меньше ребер. Граф G или один из его подграфов называется эйлеровым, если каждая из его вершин имеет четную степень (количество инцидентных ребер). Каждый простой цикл в графе является эйлеровым подграфом, но могут быть и другие. Пространство циклов графа - это совокупность его эйлеровых подграфов. Он образует векторное пространство над двухэлементным конечным полем . Операция сложения векторов - это симметричная разность двух или более подграфов, которая образует другой подграф, состоящий из ребер, которые появляются нечетное количество раз в аргументах операции симметричной разности. [1]
Базис цикла - это основа этого векторного пространства, в котором каждый базисный вектор представляет собой простой цикл. Он состоит из набора циклов, которые можно комбинировать с помощью симметричных разностей, чтобы сформировать каждый эйлеров подграф, и это минимально с этим свойством. Каждый базис цикла данного графа имеет одинаковое количество циклов, которое равно размерности его пространства циклов. Это число называется рангом схемы графа, и оно равно где количество ребер в графе, - количество вершин, а - количество связанных компонентов . [2]
Базы специального цикла
Были изучены несколько специальных типов базисов цикла, включая базисы фундаментальных циклов, слабофундаментальные базисы циклов, разреженные (или 2-) базисы циклов и целые базисы цикла. [3]
Индуцированные циклы
Каждый граф имеет базис цикла, в котором каждый цикл является индуцированным циклом . В трехвершинно-связном графе всегда существует базис, состоящий из периферийных циклов , циклов, удаление которых не разделяет оставшийся граф. [4] [5] В любом графе, кроме графа, образованного добавлением одного ребра к циклу, периферийный цикл должен быть индуцированным циклом.
Фундаментальные циклы
Если это покрывающее дерево или охватывающий лес данного графа, а также это ребро, не принадлежащее , то основной цикл определяется простой цикл, состоящий из вместе с путем в соединение конечных точек . Есть ровно фундаментальные циклы, по одному на каждое ребро, не принадлежащее . Каждый из них линейно независим от остальных циклов, поскольку включает реброчего нет ни в каком другом фундаментальном цикле. Таким образом, фундаментальные циклы составляют основу пространства циклов. [1] [2] Построенный таким образом базис цикла называется базисом фундаментального цикла или сильно фундаментальным базисом цикла . [3]
Также возможно характеризовать фундаментальные основы цикла без указания дерева, для которого они являются фундаментальными. Существует дерево, для которого данный базис цикла является фундаментальным тогда и только тогда, когда каждый цикл содержит ребро, которое не входит ни в какой другой базисный цикл, то есть каждый цикл не зависит от других. Отсюда следует, что набор циклов является фундаментальной основой цикла тогда и только тогда, когда он обладает свойством независимости и имеет правильное количество циклов, чтобы быть основой . [6]
Слабо фундаментальные циклы
Базис цикла называется слабо фундаментальным, если его циклы могут быть расположены в таком линейном порядке, что каждый цикл включает по крайней мере одно ребро, которое не входит ни в один из предыдущих циклов. Фундаментальный базис цикла автоматически является слабофундаментальным (для любого порядка ребер). [3] [7] Если каждый циклный базис графа является слабо фундаментальным, то же самое верно для каждого минора графа. Основываясь на этом свойстве, класс графов (и мультиграфов ), для которых каждый базис цикла является слабо фундаментальным, можно охарактеризовать пятью запрещенными минорами : графом квадратной пирамиды , мультиграфом, образованным удвоением всех ребер четырехвершинного цикла, два мультиграфа, образованные удвоением двух ребер тетраэдра , и мультиграф, образованный утроением ребер треугольника. [8]
Циклы лица
Если связный конечный планарный граф вложен в плоскость, каждая грань вложения ограничена циклом ребер. Одна грань обязательно неограничена (в нее входят точки, произвольно удаленные от вершин графа), а остальные грани ограничены. По формуле Эйлера для плоских графов существует ровноограниченные лица. Симметричная разность любого набора циклов граней является границей соответствующего набора граней, а разные наборы ограниченных граней имеют разные границы, поэтому невозможно представить один и тот же набор как симметричную разность циклов граней более чем в одном. способ; это означает, что набор циклов граней линейно независим. Как линейно независимый набор из достаточного количества циклов, он обязательно образует основу цикла. [9] Это всегда слабо фундаментальный базис цикла, и он фундаментален тогда и только тогда, когда вложение графа внешнепланарное .
Для графов, должным образом вложенных в другие поверхности, так что все грани вложения являются топологическими дисками, в общем случае неверно, что существует базис цикла, использующий только циклы граней. Циклы граней этих вложений порождают собственное подмножество всех эйлеровых подграфов. Группа гомологий данной поверхности характеризует эйлеровы подграфы, которые не могут быть представлены как граница набора граней. Критерий планарности Мак Лейна использует эту идею для характеристики планарных графов с точки зрения базисов цикла: конечный неориентированный граф является плоским тогда и только тогда, когда он имеет базис разреженных циклов или 2-базис , [3] базис, в котором каждое ребро граф участвует не более чем в двух базисных циклах. В плоском графе базис цикла, образованный множеством ограниченных граней, обязательно разрежен, и, наоборот, базис разреженного цикла любого графа обязательно образует множество ограниченных граней планарного вложения его графа. [9] [10]
Интегральные базы
Пространство циклов графа можно интерпретировать с помощью теории гомологий как группу гомологий из симплициального комплекса с точкой для каждой вершины графа и линейного сегмента для каждого ребра графа. Эту конструкцию можно обобщить на группу гомологийнад произвольным кольцом . Важным частным случаем является кольцо целых чисел , для которого группа гомологийявляется свободная абелева группа , подгруппа свободной абелевой группы , порожденной ребер графа. Менее абстрактно эту группу можно построить, задав произвольную ориентацию ребрам данного графа; затем элементыпредставляют собой разметку ребер графа целыми числами со свойством, что в каждой вершине сумма меток входящих ребер равна сумме меток исходящих ребер. Групповая операция - это сложение этих векторов меток. Целочисленный цикл основа представляет собой набор простых циклов , которые генерируют эту группу. [3]
Минимальный вес
Если ребрам графа присвоены веса действительных чисел, вес подграфа может быть вычислен как сумма весов его ребер. Минимальный вес базис пространства цикла обязательно цикл основа: по теореме Веблена , [11] каждый эйлеров подграф , который сам по себе не простой цикл можно разбить на несколько циклов простых, которые обязательно имеют меньший вес.
По стандартным свойствам базисов в векторных пространствах и матроидах базис цикла с минимальным весом не только минимизирует сумму весов его циклов, но также минимизирует любую другую монотонную комбинацию весов цикла. Например, это основа цикла, которая минимизирует вес самого длинного цикла. [12]
Алгоритмы полиномиального времени
В любом векторном пространстве и, в более общем смысле, в любом матроиде базис минимального веса может быть найден с помощью жадного алгоритма, который рассматривает потенциальные базисные элементы по одному, в отсортированном порядке по их весам, и который включает элемент в базис, когда он линейно не зависит от выбранных ранее базисных элементов. Проверка на линейную независимость может быть выполнена методом исключения Гаусса . Однако неориентированный граф может иметь экспоненциально большой набор простых циклов, поэтому было бы невозможно с вычислительной точки зрения сгенерировать и протестировать все такие циклы.
Хортон (1987) предоставил первый алгоритм с полиномиальным временем для нахождения базиса минимального веса в графах, для которых каждый вес ребра положителен. Его алгоритм использует этот подход генерации и тестирования, но ограничивает сгенерированные циклы небольшим наборомциклы, называемые циклами Хортона . Цикл Хортона - это фундаментальный цикл дерева кратчайших путей данного графа. Существует не более n различных деревьев кратчайших путей (по одному на каждую начальную вершину), и каждое из них имеет менее m фундаментальных циклов, что дает оценку общего числа циклов Хортона. Как показал Хортон, каждый цикл в основе цикла минимального веса является циклом Хортона. [13] Использование алгоритма Дейкстры для поиска каждого дерева кратчайших путей и последующее использование исключения Гаусса для выполнения шагов тестирования алгоритма жадного базиса приводит к алгоритму с полиномиальным временем для базиса цикла с минимальным весом. Последующие исследователи разработали улучшенные алгоритмы для этой проблемы [14] [15] [16] [17], уменьшающие временную сложность наихудшего случая для нахождения базиса цикла минимального веса в графе с края и вершины к . [18]
NP-твердость
Нахождение фундаментального базиса с минимально возможным весом тесно связано с проблемой поиска остовного дерева, которое минимизирует среднее значение попарных расстояний; оба NP-трудны . [19] Нахождение слабо фундаментального базиса минимального веса также является NP-трудным, [7] и его аппроксимация MAXSNP-трудным . [20] Если отрицательные веса и отрицательно взвешенные циклы разрешены, то поиск базиса минимального цикла (без ограничений) также NP-труден, поскольку его можно использовать для поиска гамильтонова цикла : если граф гамильтонов, и все ребра с учетом веса −1 базис цикла с минимальным весом обязательно включает в себя хотя бы один гамильтонов цикл.
В плоских графах
Базис цикла минимального веса для плоского графа не обязательно совпадает с базисом, образованным его ограниченными гранями: он может включать в себя циклы, которые не являются гранями, и некоторые грани не могут быть включены как циклы в базис цикла минимального веса. Однако существует базис цикла минимального веса, в котором никакие два цикла не пересекаются друг с другом: для каждых двух циклов в базисе либо циклы охватывают непересекающиеся подмножества ограниченных граней, либо один из двух циклов охватывает другой. Этот набор циклов соответствует в двойственном графе данного плоского графа набору разрезов, которые образуют дерево Гомори – Ху двойственного графа, базис минимального веса его пространства разрезов . [21] На основе этой двойственности неявное представление базиса цикла минимального веса в плоском графе может быть построено за время.. [22]
Приложения
Базы циклов использовались для решения задач периодического планирования, таких как задача определения расписания для системы общественного транспорта. В этом приложении циклы базиса цикла соответствуют переменным в целочисленной программе для решения задачи. [23]
В теории жесткости конструкции и кинематики основы цикла используются для управления процессом создания системы неизбыточных уравнений, которые можно решить для прогнозирования жесткости или движения конструкции. В этом приложении базисы цикла с минимальным или почти минимальным весом приводят к более простым системам уравнений. [24]
В распределенных вычислениях базы циклов использовались для анализа количества шагов, необходимых для стабилизации алгоритма. [25]
В биоинформатике базы циклов использовались для определения информации о гаплотипах из данных последовательности генома. [26] Цикл основы также были использованы для анализа третичной структуры из РНК . [27]
Базис цикла минимального веса графа ближайшего соседа точек, выбранных с трехмерной поверхности, может использоваться для получения реконструкции поверхности. [28]
В хеминформатике базис минимального цикла молекулярного графа называется наименьшим набором наименьших колец (SSSR). [29] [30] [31]
Рекомендации
- ^ a b Дистель, Рейнхард (2012), «1.9 Некоторые линейные алгебры» , Теория графов , Тексты для выпускников по математике, 173 , Springer, стр. 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 , МР 2303157.
- ^ Diestel (2012) , стр. 32, 65.
- ^ Tutte, WT (1963), "Как нарисовать график", Труды Лондонского математического общества , Третья серия, 13 : 743-767, DOI : 10.1112 / ПНИЛ / s3-13.1.743 , MR 0158387. См., В частности, теорему 2.5.
- ^ Крибб, DW; Ringeisen, RD; Shier, DR (1981), "О циклических базисах графа", Труды Двенадцатой Юго-Восточной конференции по комбинаторике, теории графов и вычислениям, Vol. I (Батон-Руж, штат Луизиана, 1981) , Congressus Numerantium, 32 , стр. 221–229, MR 0681883.
- ^ а б Рицци, Ромео (2009), "Минимальные слабо фундаментальные основы цикла трудно найти", Algorithmica , 53 (3): 402-424, DOI : 10.1007 / s00453-007-9112-8 , МР 2482112 , S2CID 12675654.
- ^ Хартвигсен, Дэвид; Земель, Эйтан (1989), "Является ли каждый цикл основа фундаментальной?", Журнал теории графов , 13 (1): 117-137, DOI : 10.1002 / jgt.3190130115 , MR 0982873.
- ^ a b Diestel (2012) , стр. 105–106.
- ^ Mac Lane, S. (1937), "Комбинаторное условие для плоских графов" (PDF) , Fundamenta Mathematicae , 28 : 22-32, DOI : 10,4064 / фм-28-1-22-32.
- ^ Веблен, Освальд (1912), "Применение модульных уравнений в анализе места нахождения", Анналы математики , второй серии 14 (1): 86-94, DOI : 10,2307 / 1967604 , JSTOR 1967604.
- ^ Чикеринг, Дэвид М .; Гейгер, Дэн; Хекерман, Дэвид (1995), «О нахождении основы цикла с кратчайшим максимальным циклом», Письма об обработке информации , 54 (1): 55–58, CiteSeerX 10.1.1.650.8218 , doi : 10.1016 / 0020-0190 (94) 00231-М , MR 1332422.
- ^ Horton, JD (1987), "Полином времени алгоритм , чтобы найти самый короткий цикл основы графа", SIAM журнал по вычислениям , 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.
- ^ Мельхорн, Курт ; Michail, Димитриос (2006), "Реализация базисных алгоритмов минимального цикла" , ACM Журнал экспериментальной Algorithmics , 11 : 2,5, DOI : 10,1145 / 1187436,1216582 , S2CID 6198296.
- ^ Кавита, Теликепалли; Мельхорн, Курт ; Михаил, Димитриос; Палуч, Катажина Е. (2008), "АнАлгоритм минимального цикла основе графов», Algorithmica , 52 (3): 333-349, DOI : 10.1007 / s00453-007-9064-г , МР 2452919.
- ^ Кавита, Теликепалли; Либхен, Кристиан; Мельхорн, Курт ; Михаил, Димитриос; Рицци, Ромео; Ueckerdt, Torsten; Цвейг, Катарина А. (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.
- ^ Део, Нарсингх; Прабху, GM; Кришнамуртите, МС (1982), "Алгоритмы для генерации фундаментальных циклов в графе", ACM Сделки по математическому обеспечению , 8 (1): 26-42, DOI : 10,1145 / 355984,355988 , МР 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, MR 2089904.
- ^ Хартвигсен, Дэвид; Мардон, Рассел (1994), «весь-пар проблема мин кроя и минимальный цикл основа задача о плоских графах», SIAM журнал по дискретной математике , 7 (3): 403-418, DOI : 10,1137 / S0895480190177042 , МР 1285579.
- ^ Боррадейл, Гленкора; Эпштейн, Дэвид ; Найери, Амир; Wulff-Nilsen, Christian (2016), "Минимальные разрезы для всех пар за почти линейное время для графов, вложенных в поверхность", Proc. 32-й межд. Symp. Вычислительная геометрия , Leibniz International Proceedings in Informatics (LIPIcs), 51 , Schloss Dagstuhl, стр. 22: 1–22: 16, arXiv : 1411.7055 , doi : 10.4230 / LIPIcs.SoCG.2016.22.
- ^ Либхен, Кристиан (2007), «Периодическая оптимизация расписания общественного транспорта», Протоколы исследования операций , 2006 : 29–36, DOI : 10.1007 / 978-3-540-69995-8_5 , ISBN 978-3-540-69994-1.
- ^ Cassell, AC; Де Хендерсон, JC; Кавех А. (1974), "Цикл базис для анализа гибкости конструкций", Международный журнал численных методов в инженерии , 8 (3): 521–528, Bibcode : 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.
- ^ Агиар, Дерек; Istrail, Сорин (2012), "HapCompass: быстрый цикл Basis Алгоритм Точная гаплотип Собрания последовательности данных", журнал вычислительной биологии , 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 , ПМК 1458283 , PMID 16679452.
- ^ Гоцман, Крейг; Калигоси, Канела; Мельхорн, Курт ; Михаил, Димитриос; Пирга, Евангелия (2007), «Циклические основы графов и дискретных многообразий», Компьютерное геометрическое проектирование , 24 (8–9): 464–480, CiteSeerX 10.1.1.298.9661 , doi : 10.1016 / j.cagd.2006.07. 001 , Руководство MR 2359763.
- ^ Мэй, Джон В .; Стейнбек, Кристоф (2014). «Эффективное восприятие кольца для набора для разработки химии» . Журнал химинформатики . 6 (3): 3. DOI : 10,1186 / 1758-2946-6-3 . PMC 3922685 . PMID 24479757 .
- ^ Даунс, GM; Gillet, VJ; Холлидей, JD; Линч, MF (1989). «Обзор алгоритмов восприятия кольца для химических графов». J. Chem. Инф. Comput. Sci. 29 (3): 172–187. DOI : 10.1021 / ci00063a007 .
- ^ Замора, А. (1979). «Алгоритм поиска наименьшего набора наименьших колец». J. Chem. Инф. Comput. Sci. 16 (1): 40–43. DOI : 10.1021 / ci60005a013 .