Элементарные циклы в графе

[histrix]

Чтобы быть кратким, приведу конкретный пример:



Есть ли стандартные методы для нахождения простейших контуров (т.е. простых треугольников из трех вершин и простых контуров между двумя рёбрами, т.е. случай когда 2 вершины связаны многими рёбрами) в графе представленном на изображении сверху?

Можно ли найти хотя бы все элементарные циклы в таком графе (если нахождение простейших контуров слишком сложно)?

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

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

P.S.: http://en.wikipedia.org/wiki/Spanning_t ... tal_cycles говорит, что минимальное дерево даст все фундаментальные циклы, т.е. если я правильно понял, то все "простые треугольники" и "замкнутые двурёберники" можно найти через минимальное дерево. Верно ли это в общем случае?

[Sonic86]

Можно и все элементарные циклы найти, не только 2-х и 3-хзвенные.
2-хзвенные циклы вообще легко найти. Если граф задан списком вершин и ребер $\{a,b\}$, то нужно просто список отсортировать и искать в нем все ребра вида $\{a,b\}$ и $\{b,a\}$ (я предполагаю, что у Вас именно ребра, а не дуги).
Для нахождения циклов длины $k$ достаточно возвести матрицу связности $A$ в $k$-ю степень. В результате на главной диагонали число будет $a_{ii}>0$ тогда и только тогда, когда $i$ принадлежит циклу длины $k$.
Можно и перебором искать: перебрать все тройки смежных вершин или ребер. Как только одно ребро или вершину обработали - можем его выкинуть.

[histrix]

Sonic86 в сообщении #828436 писал(а):

Можно и все элементарные циклы найти, не только 2-х и 3-хзвенные.

Спасибо! Т.е. просто надо возводить матрицу связности в N-ю степень и выбирать циклы длины N, потом брать N+1 .. Вопрос тогда до какого N+M надо так делать? До степени N+M равной половине количества рёбер графа, или есть способы оценки длины (в количестве рёбер) самого длинного элементарного цикла?

И верно ли, что все треугольники и двухзвенные элементарные циклы и прочие "элементарные фигуры" в графе являются фундаментальными циклами? Тогда их можно найти через минимальное дерево (см. P.S. к вопросу). Именно "элементарные фигуры" мне и нужны вообще-то для решения. Известно, что каждая "элементарная фигура" - элементарный цикл, но я пока сомневаюсь, верно ли что каждая "элементарная фигура" - фундаментальный цикл (т.к. графы лишь немного сам учил).

Как из всего множества элементарных циклов отсортировать "нужные" (т.е. "элементарные фигуры") мне известно по условию задачи.

[Sender]

Sonic86 в сообщении #828436 писал(а):

Для нахождения циклов длины $k$ достаточно возвести матрицу связности $A$ в $k$-ю степень.

Таким образом будут посчитаны все циклы, не только элементарные.

[ИСН]

BTW, что такое фундаментальные циклы? Из текста понял, что они определяются в зависимости от дерева. А дерево само определяется неоднозначно.

[histrix]

ИСН в сообщении #828501 писал(а):

BTW, что такое фундаментальные циклы

Вот как по-русски фундаментальные циклы я не знаю, т.к. у меня в ВУЗе не было дискретной математики (не та специальность).

Но вот подборка сообщений из интернета:

http://stackoverflow.com/questions/1678 ... in-a-graph
http://stackoverflow.com/questions/1311 ... in-a-graph

Хорошее описание задачи (см. ссылку 2): рёбра это улицы в районе, а вершины - это перекрёстки улиц. Надо выделить границы блоков домов между улицами. Можно найти все элементарные циклы, а потом отобрать "нужные" (что для меня вариант "хотя бы"), но вроде обсуждаются некие minimal cycles, которые и будут блоками домов. Их и надо найти.

Граф можно считать "unweighted" (т.е. у каждого ребра единичный вес), если DFS (Depth-first search, Поиск в глубину) тут поможет, то можете напишисать как, а если нет, то лучше сказать об этом сразу.. Я о графах пока только основы основ знаю.

P.S.: Тему возможно стоит переименовать в Элементарные/минимальные циклы в графе

[Sender]

Обладает ли ваш граф свойством планарности, т.е. может ли быть уложен на плоскости так, чтобы его рёбра не пересекались?

[histrix]

Граф планарный и без мостов. Надо в идеале найти набор "минимальных" элементарных циклов, которые покрывают весь граф, при этом из условия ясно, что одно ребро может быть использовано 1-2 раза (2 раза если его делят "циклы-соседи")

[Sonic86]

Sender в сообщении #828479 писал(а):

Таким образом будут посчитаны все циклы, не только элементарные.

А если $k=3$? Неэлементарные циклы начинаются ведь только с $k=6$
Хотел еще сказать, что в общем случае число ответов $=O(n^3)$, где $n$ - число вершин. Потому можно хоть перебором их искать. Наверное

[Sender]

Ещё раз внимательно перечитал условие. Похоже, тут просто требуется найти все грани плоской укладки графа, причём она уже дана: граф представлен набором отрезков. Думаю, тут всё же подойдёт алгоритм, использующий расположение этих точек на плоскости. В моём представлении он может выглядеть так:
Пусть на плоскости задана прямоугольная декартова система координат с координатными векторами $\boldsymbol{i},\;\boldsymbol{j} $. Также задано рассматриваемое множество отрезков.
1. Среди концов рассматриваемых отрезков возьмём точку $p_1$, заведомо принадлежащую внешней грани, а именно какую-нибудь точку с наименьшей координатой $x$.
2. Среди всех точек, соединённых отрезками с точкой $p_1$, выберем точку $p_2$, такую, что угол между $\boldsymbol{j}$ и $\overrightarrow{p_1p_2}$, отсчитываемый по часовой стрелке, минимален.
3. Находясь в точке $p_i$, выбираем следующую точку, $p_{i+1}$, среди всех точек, соединённых отрезками с $p_i$, кроме $p_{i-1}$, такую, что угол между $\overrightarrow{p_{i-1}p_i}$ и $\overrightarrow{p_{i}p_{i+1}}$, отсчитываемый по часовой стрелке, максимален.
Повторять этот шаг до возвращения в точку $p_1$.
4. Найденная последовательность точек представляет собой очередную грань. Отрезок $p_1p_2$ не принадлежит никакой другой грани. Исключим его из дальнейшего рассмотрения.
4а. Если имеется "висячая" точка, являющаяся концом только одного отрезка, исключим эту точку и этот отрезок из дальнейшего рассмотрения. Будем повторять этот шаг, пока таких точек не останется.
5. Если у нас ещё остались отрезки, перейдём к шагу 1.

Взаимную ориентацию векторов можно определить с помощью векторного произведения.

[histrix]

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

Если бы рёбра графа в плоской укладке были прямыми, я бы скорее предпочёл геометрический алгоритм. Но из-за того что геометрия рёбер может быть произвольной, решил формализм графов использовать, т.к. графы только учитывают связи между вершинами, без рассмотрения формы этих связей.

Если кривые соединяющие "перекрёстки"/вершины графа заданы набором точек (т.е. кусочно-линейные прямые), то возможно алгоритм Sender'a может сработать, если, начиная от определённого перекрёстка, брать угол между $\overrightarrow{p_1p_k}$ и $j$, где $p_k$ следующие "точки построения" криволинейных отрезков, а не их конечные точки... Не уверен, что сработает для криволинейных отрезков произвольной формы.

[Sender]

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

[histrix]

Пытаюсь реализовать приведённый Sender'ом алгоритм. На графе внизу выбрал первую вершину $V_0$. Первое ребро (наименьший угол по ЧС с ортом j) $V_0V_4$ ведёт в "тупик", исключаем, берём следующее по ЧС ребро $V_0V_3$. В вершине $V_3$ выбираем направленное ребро $V_3V_2$, т.к. у него с предыдущим направленным ребром $V_0V_3$ наибольший угол по ЧС (считая от $V_0V_3$). Однако в вершине $V_2$, если считать угол по ЧС от $V_3V_2$, то наибольший угол будет у $V_2V_8$, а не у $V_2V_0$.



Т.е. вопрос, как верно считать угол? Алгоритм кажется верным, нашел что-то подобное на английском http://www.geometrictools.com/Documenta ... eBasis.pdf (пример на рисунке взят оттуда, читать можно с 18й страницы, до неё там поиск в глубину описывают). Но там очень путанные объяснения, одно с другим, скажем так, непросто соотнести. Я расшифровываю, конечно, но может мне и тут парадокс с углами прояснят? Я пока не пробовал писать векторные произведения и проч. код, т.к. хочу сначала в голове уяснить, как это будет работать.

[Sender]

Хм, да, похоже, ошибся с углами. Идея в том чтобы отмерять все углы в каком-то одном направлении, оставаясь при этом внутри грани.
Вот так точно должно сработать: находясь в точке $p_i$, выбираем следующую точку, $p_{i+1}$, среди всех точек, соединённых отрезками с $p_i$, кроме $p_{i-1}$, такую, что угол между $\overrightarrow{p_{i}p_{i-1}}$ и $\overrightarrow{p_{i}p_{i+1}}$, отсчитываемый против часовой стрелки, минимален.

[histrix]

От которого из 2х векторов угол между $\overrightarrow{p_{i}p_{i-1}}$ и $\overrightarrow{p_{i}p_{i+1}}$ отсчитывать против часовой стрелки? Это, по-моему, зависит от того, идём мы по контуру по ЧС или же против ЧС. Но т.к. пока контур не замкнут, направление обхода по нему не определишь (особенно при начале обхода, когда взят один отрезок только), то возникают трудности с реализацией идеи.

К счастью, нашёл тему http://math.stackexchange.com/questions ... in-a-graph, там дан простой для понимания алгоритм нахождения всех граней планарной укладки графа. Будет время - переведу. Пока, увы, времени очень мало.