Что такое пересекающиеся циклы граф
Граф с окрашенными рёбрами для иллюстрации пути H-A-B, замкнутого пути или обхода с повторением вершин B-D-E-F-D-C-B и цикла без повторения рёбер или вершин H-D-G-H
В теории графов два типа объектов обычно называются циклами.
Один тип циклов, чаще называющиеся замкнутым обходом, состоит из последовательности вершин, начинающейся и заканчивающейся в той же самой вершине, и каждые две последовательные вершины в последовательности смежны. Другой тип циклов, иногда называемых простыми циклами, – это замкнутые обходы без повторного прохода по ребру или посещения вершины дважды, за исключением начальной и конечной вершин. Простые циклы можно описать набором рёбер, в отличие от замкнутых обходов, в которых наборы рёбер (с возможным повторением) не определяют однозначно порядок вершин. Ориентированный цикл в орграфе – это последовательность вершин, начинающаяся и завершающаяся в той же самой вершине, и в этой последовательности для любых двух последовательных вершин существует дуга из более ранней в более позднюю. Такое же различие между простыми циклами и обходами, как выше, можно определить и для ориентированных графов[1].
Циклы без хорд[править | править код]
Цикл без хорд в графе, также называемый дырой или порождённым циклом, – это цикл, в котором никакие две вершины цикла не соединены ребром, разве что это ребро само принадлежит циклу. Антидыра – это дополнение дыры. Графы без хорд можно использовать для описания совершенных графов – согласно строгой теореме о совершенных графах граф является совершенным в том и только в том случае, когда он не содержит дыр и антидыр с нечётным числом вершин больше трёх. Хордальный граф – это специальный тип совершенных графов, в котором нет дыр размером больше трёх.
Обхват графа – это длина наименьшего цикла. Этот цикл обязательно не будет иметь хорд. Клетки – это наименьшие регулярные графы с заданной степенью вершин и обхватом.
Периферийный цикл – это цикл в графе со свойством, что любые два ребра, не принадлежащие циклу, можно соединить путём внутренние точки которого не принадлежат циклу. В графе, не образованном добавлением одного ребра к циклу, периферийный цикл должен быть порождённым циклом.
Пространство циклов[править | править код]
Понятие цикл может также относиться к элементам пространства циклов графа. Оно состоит из множеств рёбер, которые имеют чётную степень для каждой вершины. Множества образуют векторное пространство над конечным полем из двух элементов. Используя методы алгебраической топологии его можно обобщить до векторных пространств или модулей над другими кольцами, такими как целые числа, вещественные числа и т. д. По теореме Веблена любой элемент пространства циклов можно получить путём комбинирования простых циклов. База циклов графа – это множество простых циклов, которые образуют базис пространства циклов[2][3].
Поиск цикла[править | править код]
Неориентированный граф имеет цикл в том и только в том случае, когда поиск в глубину (DFS) находит ребро, которое приводит к уже посещённой вершине (обратная дуга)[4]. Таким же образом, все обратные рёбра, которые алгоритм DFS обнаруживает, являются частями циклов[5]. Для неориентированных графов требуется только время O(n) для нахождения цикла в графе с n вершинами, поскольку максимум n − 1 рёбер могут быть рёбрами дерева.
Ориентированный граф имеет цикл в том и только в том случае, когда DFS находит обратную дугу. Дуги вперёд и поперечные дуги не обязательно говорят о цикле. Многие алгоритмы топологических сортировок также обнаруживают циклы, поскольку они мешают существованию топологического порядка. Если ориентированный граф разделён на компоненты сильной связности, циклы существуют только в компонентах, но не между ними, поскольку циклы сильно связаны[5].
Приложения алгоритмов нахождения циклов включают графы ожидания для нахождения взаимных блокировок в системах с параллельными потоками[6].
Покрытие графов циклами[править | править код]
В работе 1736 года о проблеме семи мостов Кёнигсберга, общепринято считающейся днём рождения теории графов, Леонард Эйлер доказал, что для того, чтобы конечный неориентированный граф имел замкнутый обход всех рёбер ровно по одному разу, необходимо и достаточно, чтобы он был связан и имел чётную степень всех вершин. Соответствующее описание существования замкнутого обхода каждого ребра ровно один раз в ориентированном графе состоит в требовании, чтобы граф был сильно связан и каждая вершина имела одинаковое число входящих и исходящих дуг. В обоих случаях полученный путь известен как эйлеров цикл. Если конечный неориентированный граф имеет чётную степень каждой вершины, независимо от того, связан он или нет, можно найти множество простых циклов, которые покрывают каждое ребро ровно раз – это теорема Веблена[7]. Если связный граф не удовлетворяет условиям теоремы Эйлера, замкнутый обход минимальной длины, покрывающий все рёбра по меньшей мере один раз может быть найден, тем не менее, за полиномиальное время путём решения задачи об инспекции дорог (англ.)русск..
Задача поиска простого цикла, проходящего через каждую вершину ровно один раз, в отличие от покрытия рёбер, намного сложнее. Такие циклы известны как гамильтоновы циклы, и задача определения существуют ли такие циклы NP-полна[8]. Опубликовано множество исследований относительно классов графов, заведомо содержащих гамильтоновы циклы. Примером может служить теорема Оре о том, что гамильтонов цикл может быть найден в графе всегда, если при сложении степеней любой пары несмежных вершин получим по меньшей мере общее число вершин графа[9].
Гипотеза о двойном покрытии циклами утверждает, что для любого графа без мостов существует мультимножество простых циклов, покрывающих каждое ребро графа в точности два раза. Доказательство гипотезы, либо контрпример пока не найдены[10].
Классы графов, определяемые циклами[править | править код]
Некоторые важные классы графов можно определить или описать их циклами. Это:
- Двудольный граф – граф без нечётных циклов.
- Кактус – граф, в котором любая нетривиальная двусвязная компонента является циклом.
- Граф-цикл – граф, состоящий из единственного цикла.
- Хордальный граф – граф, в котором нет порождённых циклов длиной больше трёх.
- Ориентированный ациклический граф – ориентированный граф без циклов.
- Совершенный граф – граф без порождённых циклов нечётной длины более трёх, либо их дополнений.
- Псевдолес – граф, в котором каждая связная компонента имеет максимум один цикл.
- Сильно связный граф – ориентированный граф, в котором любая дуга входит в какой-либо цикл.
- Граф без треугольников – граф, в котором нет циклов длины три.
Примечания[править | править код]
- ↑ V. K. Balakrishnan. Schaum’s outline of theory and problems of graph theory. – McGraw-Hill, 2005. – ISBN 978-0070054899.
- ↑ Jonathan L. Gross, Jay Yellen. 4.6 Graphs and Vector Spaces // Graph Theory and Its Applications. – 2nd. – CRC Press, 2005. – С. 197-207. – ISBN 9781584885054.
- ↑ Reinhard Diestel. 1.9 Some linear algebra // Graph Theory. – Springer, 2012. – Т. 173. – С. 23-28. – (Graduate Texts in Mathematics).. Перевод: Рейнгард Дистель. 1.9 Немного линейной алгебры // Теория графов. – Новосибирск: Издательство Института математики, 2002. – С. 35-40. – ISBN 5-86134-101-X..
- ↑ Alan Tucker. Chapter 2: Covering Circuits and Graph Colorings // Applied Combinatorics. – 5th. – Hoboken: John Wiley & sons, 2006. – С. 49. – ISBN 978-0-471-73507-6.
- ↑ 1 2 Robert Sedgewick. Graph algorithms. – Addison-Wesley, 1983. – ISBN 0-201-06672-6.
- ↑ Abraham Silberschatz, Peter Galvin, Greg Gagne. Operating System Concepts. – John Wiley & Sons, INC., 2003. – С. 260. – ISBN 0-471-25060-0.
- ↑ Oswald Veblen. An Application of Modular Equations in Analysis Situs // Annals of Mathematics. – 1912. – Т. 14, вып. 1. – С. 86-94.
- ↑ Richard M. Karp. Complexity of Computer Computations / R. E. Miller and J. W. Thatcher. – New York: Plenum, 1972. – С. 85-103.
- ↑ Ø. Ore. Note on Hamilton circuits // American Mathematical Monthly. – 1960. – Т. 67, вып. 1. – С. 55.
- ↑ F. Jaeger. Annals of Discrete Mathematics 27 – Cycles in Graphs. – 1985. – Т. 27. – С. 1-12. – (North-Holland Mathematics Studies). – doi:10.1016/S0304-0208(08)72993-1.
Источник
Граф циклов группы иллюстрирует различные циклы в группе и, в частности, используется для визуализации структуры малых конечных групп.
Цикл – это множество степеней элемента a группы, где an, n-ая степень элемента a, определяется как произведение a на себя n раз. Говорят, что элемент a генерирует цикл. В конечной группе некоторая ненулевая степень элемента a должна быть равна нейтральному (единичному) элементу e . Наименьшая такая степень называется порядком цикла и она равна числу различных элементов в цикле. В графе циклов цикл представляется многоугольником, в котором вершины отражают элементы группы, а соединяющие вершины рёбра указывают, что вершины многоугольника являются членами одного цикла.
Циклы[править | править код]
Циклы могут накладываться или не иметь общих элементов, кроме единичного. Граф циклов показывает каждый цикл в виде многоугольника.
Если a генерирует цикл порядка 6 (или, более коротко, имеет порядок 6), то a6 = e. В этом случае степени квадрата элемента a2, {a2, a4, e} образуют цикл, но в реальности этот факт не даёт никакой дополнительной информации. Аналогично, a5 генерирует тот же самый цикл, что и сам a.
Таким образом, нужно рассматривать только простые циклы, а именно те, которые не являются подмножествами других циклов. Каждый из этих циклов генерируется некоторым простым элементом a. Возьмём одну вершину для каждого элемента исходной группы. Для каждого простого элемента соединим ребром e с a, a с a2, …, an−1 с an, и т.д., пока не получим опять e. Результатом будет граф циклов.
Если a2 = e, a имеет порядок 2 (является инволюцией) и соединено с единичным элементом e двумя рёбрами. Кроме случаев, когда хотят подчеркнуть два ребра цикла, обычно рисуется[1] только одно ребро.
Свойства[править | править код]
В качестве примера графа циклов группы рассмотрим диэдральную группу Dih4. Таблица умножения этой группы показана ниже, а граф циклов показан на рисунке справа (e показывает единичный элемент).
| o | e | b | a | a2 | a3 | ab | a2b | a3b |
|---|---|---|---|---|---|---|---|---|
| e | e | b | a | a2 | a3 | ab | a2b | a3b |
| b | b | e | a3b | a2b | ab | a3 | a2 | a |
| a | a | ab | a2 | a3 | e | a2b | a3b | b |
| a2 | a2 | a2b | a3 | e | a | a3b | b | ab |
| a3 | a3 | a3b | e | a | a2 | b | ab | a2b |
| ab | ab | a | b | a3b | a2b | e | a3 | a2 |
| a2b | a2b | a2 | ab | b | a3b | a | e | a3 |
| a3b | a3b | a3 | a2b | ab | b | a2 | a | e |
Обратим внимание на цикл e, a, a2, a3. Его можно видеть в таблице как последовательные степени a. Обратный проход тоже подходит. Другими словами, (a3)2 = a2, (a3)3 = a и (a3)4 = e. Это поведение остаётся верным в любом цикле любой группы – цикл можно проходить в любом направлении.
Граф циклов группы кватернионов Q8.
Циклы, содержащие непростые значения элементов, неявно содержат циклы, не показанные в графе. Для группы Dih4 выше мы можем нарисовать ребро между a2 и e, поскольку (a2)2 = e, но a2 является частью большего цикла, так что ребро не проведено.
Может существовать неопределённость, если два цикла содержат элемент, не являющийся единичным элементом. Рассмотрим, например, группу кватернионов, граф циклов которой показан справа. Каждый элемент в среднем ряду, умноженный на себя, даёт −1. В этом случае мы можем использовать различные цвета для отражения циклов, хотя просто соглашение о симметрии будет работать так же хорошо.
Как упоминалось ранее, два ребра цикла из двух элементов обычно изображаются единственным ребром.
Обратный элемент можно найти в графе циклов следующим образом: это элемент, находящийся на том же расстоянии от единицы, но в обратном направлении.
История[править | править код]
Графы циклов рассматривал специалист по теории чисел Дэниел Шенкс в начале 1950-х как средство изучения мультипликативных групп колец вычетов[2]. Шенкс первым опубликовал идею в первом издании (1962) его книги «Solved and Unsolved Problems in Number Theory» («Решённые и нерешённые проблемы теории чисел»)[3]. В книге Шенкс исследует, какие группы имеют изоморфные графы циклов и когда граф циклов планарен[4]. Во втором издании (1978) Шенкс рассуждает о своих исследованиях групп классов идеалов и разработке алгоритма больших и малых шагов[5]:
Графы циклов используются в качестве учебного средства во вводном учебнике Натана Картера (Nathan Carter, 2009) «Visual Group Theory» («Наглядная теория групп»)[6].
Графы циклов некоторых семейств групп[править | править код]
Некоторые виды групп имеют типичные графы:
Циклические группы Zn порядка n имеют единственный цикл, который можно нарисовать как многоугольник с n сторонами:
Если n является простым числом, группы вида (Zn)m имеют (nm − 1)/(n − 1) циклов длины n с общим единичным элементом:
Диэдральные группы Dihn имеют порядок 2n и состоят из цикла длины n и n 2-элементных циклов:
Дициклические группы, Dicn = Q4n имеют порядок 4n:
Другие прямые произведения:
Симметрическая группа Sn для любой группы порядка n содержит подгруппу, изоморфную этой группе, так что граф циклов любой группы порядка n можно найти в качестве подграфа графа циклов Sn.
Смотрите пример: Подгруппы группы S4.
Пример: Подгруппы полной октаэдральной группы[править | править код]
Полная октаэдральная группа[en] является прямым произведением симметрической группы S4 и циклической группы Z2.
Группа имеет порядок 48 и содержит подгруппы любого порядка, делящего 48.
В примерах ниже вершины, связанные друг с другом, расположены рядом,
Так что представленные графы циклов не являются наиболее простыми графами этих групп (сравните с графами циклов тех же групп в начале раздела).
Подобно всем другим графам графы циклов можно представить различными способами, чтобы подчеркнуть различные свойства. Два представления графа циклов группы S4 являются примером этого.
См. также[править | править код]
- Список групп малого порядка
- Граф Кэли
Примечания[править | править код]
- ↑ Sarah Perkins. Commuting Involution Graphs for A˜n, Section 2.2, p.3, first figure. Birkbeck College, Malet Street, London, WC1E 7HX: School of Economics, Mathematics and istics (2000). Дата обращения: 31 января 2016.
- ↑ Shanks, 1978, p. 246.
- ↑ Shanks, 1978, с. xii.
- ↑ Shanks, 1978, с. 83-98, 206-208.
- ↑ Shanks, 1978, p. 225.
- ↑ Carter, 2009.
Литература[править | править код]
- Steven Skiena. §4.2.3 Cycles, Stars, and Wheels // Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. – Addison-Wesley, 1990. – С. 144-147. – ISBN 0201509431.
- Daniel Shanks. Solved and Unsolved Problems in Number Theory. – 2nd. – New York: Chelsea Publishing Company, 1978. – ISBN 0-8284-0297-3.
- Sriram Pemmaraju, Steven S. Skiena. §6.2.4 Cycles, Stars, and Wheels // Computational Discrete Mathematics: Combinatorics and Graph Theory in Mathematics. – Cambridge, England: Cambridge University Press, 2003. – С. pp. 248-249. – ISBN 0-521-80686-0.
- Nathan Carter. Visual Group Theory. – Mathematical Association of America, 2009. – (Classroom Resource Materials). – ISBN 978-0-88385-757-1.
Ссылки[править | править код]
- Weisstein, Eric W. Cycle Graph (англ.) на сайте Wolfram MathWorld.
Источник
| myltykritik | Транспозиция пересекающихся циклов 27.01.2017, 16:08 |
Здравствуйте! Решаю задачник Кострикина по алгебре и натолкнулась на следующую задачу: Цитата: Определить четность подстановки: Будь это транспозиция непересекающихся циклов, я бы легко привела её к виду и подсчитала количество инверсий. Но тут транспозиция пересекающихся циклов, поэтому так просто разобраться не получается. В учебниках, в основном, пишут про то, как обычный вид представить в качестве произведения скобок с двумя элементами, но не наоборот (если кто подскажет хороший ресурс, как сделать транспозицию пересекающихся скобок с количеством элементов в них больше двух, буду благодарна). Я пыталась склеить по третьей скобке , но в первых скобках помимо этих чисел есть ещё повторяющиеся, которые не дают мне сделать преобразование. Других подходящих методов больше не нашла. Прошу направить на путь истинный! | |
| Sinoid | Re: Транспозиция пересекающихся циклов 27.01.2017, 16:27 |
Будь это транспозиция непересекающихся циклов, я бы легко привела её к виду и подсчитала количество инверсий. А что мешает вам также поступить и в этом случае? Я думал, там нужно что-то этакое, а вы согласны на простой подсчет, ну дык и посчитайте, предварительно перемножив. | |
| Sonic86 | Re: Транспозиция пересекающихся циклов 27.01.2017, 17:42 |
Будь это транспозиция непересекающихся циклов, я бы легко привела её к виду и подсчитала количество инверсий. Но тут транспозиция пересекающихся циклов, поэтому так просто разобраться не получается. Вычислять произведение циклов вообще, конечно, надо уметь, но для вычисления четности подстановки саму подстановку можно не вычислять. https://www.algebraical./doku.php?id … 0%BA%D0%B8 Вычислить все произведение можно через вычисление образа элементов для каждого . В учебниках, в основном, пишут про то, как обычный вид представить в качестве произведения скобок с двумя элементами, но не наоборот Ну просто попробуйте обратите процесс да и все. Начните с того, как представить простой цикл в обычном виде | |
| myltykritik | Re: Транспозиция пересекающихся циклов 27.01.2017, 18:42 |
В целом, не понимаю, как перемножить. И говоря «перемножить», вы имеете виду: привести к обычному виду? Типа: умножить на и потом на третью скобочку? И уже у этого посчитать инверсию? Будь это транспозиция непересекающихся циклов, я бы легко привела её к виду и подсчитала количество инверсий. А что мешает вам также поступить и в этом случае? Я думал, там нужно что-то этакое, а вы согласны на простой подсчет, ну дык и посчитайте, предварительно перемножив. | |
| Sonic86 | Re: Транспозиция пересекающихся циклов 27.01.2017, 18:57 |
И говоря «перемножить», вы имеете виду: привести к обычному виду? Мне без разницы – к любому виду, лишь бы умножение исчезло. И уже у этого посчитать инверсию? Для решения исходной задачи я предлагаю вообще ничего не перемножать, а вычислять инверсию сразу, от произведения: ( – четность перестановки, – перестановки) В целом, не понимаю, как перемножить. Ну елки, так начните с самого простого. Перестановки – это биекции на множестве , произведение перестановок – это обычная композиция функций: т.е. если , то . Например, если , то , итого . Потом рассмотрите запись перестановки в виде цикла и вытащите оттуда правило умножения перестановок в виде циклов. | |
| vpb | Re: Транспозиция пересекающихся циклов 28.01.2017, 00:32 |
А что такое “транспозиция циклов”, хоть пересекающихся, хоть нет? Разве есть такой термин? Что такое “транспозиция”? | |
| Brukvalub | Re: Транспозиция пересекающихся циклов 28.01.2017, 06:36 |
“транспозиция” следует читать “композиция”, т.е. последовательное выполнение отображений, известное также как “сложная функция”. | |
| myltykritik | Re: Транспозиция пересекающихся циклов 30.01.2017, 13:08 |
vpb , тему разбираю недавно, но, кажется, в учебниках именно так называется перемножение циклов. — 30.01.2017, 16:08 — Brukvalub , а как это применимо к моему примеру? Не могу понять, как перемножать эти скобочки. — 30.01.2017, 16:11 — Sonic86 , спасибо! — 30.01.2017, 16:14 — Перестановки – это биекции на множестве , произведение перестановок – это обычная композиция функций: т.е. если , то . Например, если , то , итого . Потом рассмотрите запись перестановки в виде цикла и вытащите оттуда правило умножения перестановок в виде циклов. У вас здесь пример с циклами, которые я умею перемножать. Но у меня в примере пересекающиеся циклы! И у меня не получается применить ваш совет к ним. | |
| Sinoid | Re: Транспозиция пересекающихся циклов 30.01.2017, 15:06 |
Но у меня в примере пересекающиеся циклы! И у меня не получается применить ваш совет к ним. Так это ничего не меняет. Смотрим, ага, в первом множителе 1 переходит в 4, во втором множителе 4 переходит в 8, в третьем множителе 8 вообще ни во что не переходит. Значит, в произведении (конечном) 1 переходит в… — 30.01.2017, 19:10 — Кстати, а порядок умножения-то слева направо? | |
| vpb | Re: Транспозиция пересекающихся циклов 30.01.2017, 15:43 |
Да, именно так, как Вы писали в посте от 21:42 27.01, и сделайте. Если по Кострикину вдруг непонятно, как обращаются с подстановками, почитайте Куроша “Курс высшей алгебры”, самое начало, там еще проще. Или ван дер Варден “Алгебра”, начало гл.2. | |
| arseniiv | Re: Транспозиция пересекающихся циклов 30.01.2017, 15:48 |
У вас здесь пример с циклами, которые я умею перемножать. Но у меня в примере пересекающиеся циклы! И у меня не получается применить ваш совет к ним. Пример Sonic86 как раз-таки с пересекающимися циклами и . А совет просто в том, чтобы проследить, какой элемент в какой переходит по определению композиции перестановок . И даже расписано. В результате было бы интересно знать, что у вас не получается, если вам интересно, чтобы с этим что-то сделали. | |
| Sinoid | Re: Транспозиция пересекающихся циклов 30.01.2017, 16:21 |
А совет просто в том, чтобы проследить, какой элемент в какой переходит по определению композиции перестановок. Да тут недопонимание самого определения композиции перестановок | |
| myltykritik | Re: Транспозиция пересекающихся циклов 31.01.2017, 09:57 |
Кстати, а порядок умножения-то слева направо? А вот это вопрос. Уточнять буду, потому что, вроде бы, в каких-то примерах я и справа налево умножала. — 31.01.2017, 12:58 — Да, именно так, как Вы писали в посте от 21:42 27.01, и сделайте. Если по Кострикину вдруг непонятно, как обращаются с подстановками, почитайте Куроша “Курс высшей алгебры”, самое начало, там еще проще. Или ван дер Варден “Алгебра”, начало гл.2. А вот тут ещё подняли вопрос: порядок умножения же тоже должен быть важен? Или если я привожу к стандартному виду, то уже нет? — 31.01.2017, 13:03 — У вас здесь пример с циклами, которые я умею перемножать. Но у меня в примере пересекающиеся циклы! И у меня не получается применить ваш совет к ним. Пример Sonic86 как раз-таки с пересекающимися циклами и . А совет просто в том, чтобы проследить, какой элемент в какой переходит по определению композиции перестановок . И даже расписано. В результате было бы интересно знать, что у вас не получается, если вам интересно, чтобы с этим что-то сделали. Пример, как перемножить и встречается чуть ли не первым в учебниках, а вот – нет. — 31.01.2017, 13:04 — Да тут недопонимание самого определения композиции перестановок [/quote] Возможно. | |
| arseniiv | Re: Транспозиция пересекающихся циклов 31.01.2017, 11:28 |
а вот – нет Тут всё совершенно аналогично. Будем пока так же предполагать, что умножение справа налево. Начнём, скажем, с 1: . Будем сразу получать циклы результата, потому дальше проверим 4: . Дальше: . Цикл не хочет заканчиваться, ну что ж: ; ; ; . Всё, мы знаем, что результат – это произведение цикла и ещё, возможно, каких-то непересекающихся (и с ним, и друг с другом). Здесь видно, что больше никаких, потому что больше никаких точек ни один из циклов в исходном произведении не двигал. Если бы там нашлась, скажем, 5 или 11, мы бы пошли с неё искать следующий цикл, и так до тех пор, пока необработанные точки, встречавшиеся в циклах, не кончатся. Теперь найдите произведение . (Ответ) | |
| Sonic86 | Re: Транспозиция пересекающихся циклов 31.01.2017, 14:46 |
А вот тут ещё подняли вопрос: порядок умножения же тоже должен быть важен? Порядок вычисления произведений неважен, потому что умножение подстановок ассоциативно (а оно ассоциативно по очевидной причине). Пример, как перемножить и встречается чуть ли не первым в учебниках, а вот – нет. В этих задачах нет решительно никакой разницы. Ну в крайнем случае можно циклы преобразовать в перестановки и потом их стандартно перемножить. | |
Источник