Дан неориентированный граф из N вершин и M ребер (N <= 2500, M <= 4*N). Требуется сказать, можно ли данный граф разбить на циклы длинной не менее 3 вершин?

Уточните, пожалуйста, условие. "Разбить" - понятие растяжимое: надо ли распределить все рёбра между циклами (или можно удалить некоторые рёбра), можно ли одну вершину включать в несколько циклов сразу.

В смысле — можно ли граф разбить на самонепересекающиеся циклы, использование всех ребер необязательно. У меня была идея — каким-либо хитрым способом ориентировать граф, и далее проверить просто, можно ли его разбить на сильносвязанные компоненты, но непонятно как граф ориентировать.

Каждая вершина должна оказаться ровно в одном цикле?

Т.е. на таком тесте будет ответ "NO": 1-2, 1-3, 2-3, 3-4, 3-5, 4-5?

Да, каждая вершина должна принадлежать только одному циклу. Да, ответ на этот тест будет NO.

Это сообщение отредактировал(а) Vasiliyvaya - 9.12.2011, 16:15

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

Это не очень подойдет для графа из 2500 вершин и 10000 ребер.

Я потратил несколько дней на эту задачу, потом порылся в литературе, но полного решения я пока не знаю.

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


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

Решение - через сведение задачи к максимальному потоку. Построим такую сеть:
1) из истока сети подведём по одному ребру к каждой вершине первой доли с пропускной способностью 2.
2) из каждой вершины второй доли подведём ребро к стоку, тоже все рёбра с пропускной способностью 2.
3) каждое ребро двудольного графа заориентируем от первой доли ко второй, и дадим ему пропускную способность 1.
Найдём в этой сети максимальный поток. Что мы тем самым получим? Утверждается, что то, как потечёт поток - и есть искомый набор циклов. В самом деле, если нашёлся поток величины 2N (т.е. все вершины насытились по максимуму), то он выберет 2N рёбер исходного двудольного графа, причём у каждой вершины получится степень ровно 2.


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


Решение для произвольных неориентированных графов - как утверждают немногочисленные статьи, которые мне удалось найти - было придумано ещё Эдмондсом почти полвека назад. Помимо весьма известного алгоритма поиска максимального паросочетания в произвольных графах, Эдмондс, как утверждают эти статьи, придумал и алгоритм для 2-сочетания ("binary 2-matching"), который и есть ваша задача. Однако толкового описания этого алгоритма я не нашёл - в большинстве статей на него просто ссылаются, в части статей описываются какие-то алгоритмы (но, на вид, исполинской сложности), а часть статей мне не удалось посмотреть, т.к. доступ к ним платный.

•  Edmonds. Maximum Matching and a Polyhedron with 0,1-Vertices. 1964
  Здесь в самом конце (Section 8) говорится лишь о существовании алгоритма на основе доказанных теорем.
•  Hartvigsen. Extensions of Matching Theory. 1984
  Chapter 2 посвящён описанию авторского алгоритма решения задачи. На вид - алгоритм похож на алгоритмы Эдмондса сжатия цветков, но описание его очень объёмно и запутанно.
•  Hassin, Khuller. z-Approximations. 2000(?)
  В разделе "2 The traveling salesman problem" упоминается, что решение задачи "cycle cover", она же "binary 2-matching", для неориентированных графов известно, и ссылаются на два источника (статью Hartvigsen, и ещё книгу Nemhauser, Wolsey, которую мне не удалось найти в открытом доступе).
•  и т.д.

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

Понятно, спасибо, попробую разобраться. 

Это сообщение отредактировал(а) Vasiliyvaya - 16.12.2011, 19:20

Ой, а вы тут оказывается уже стёрли из последнего поста новую задачу - а она ведь крутилась у меня в голове все эти дни 

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

Ну я всё же напишу здесь это решение. Условие было таким: дан граф из n<=4000 вершин и m<=4000 рёбер. Требуется найти количество таких четвёрок вершин, что между вершинами этой четвёрки нет ни одного ребра.

При решении первый ход, казалось бы, довольно стандартный: воспользуемся формулой включений-исключений, тогда задача превращается в такую: узнать, сколько всего бывает четвёрок вершин; узнать, сколько есть таких четвёрок, которые накрывают хотя бы одно ребро (причём если четвёрка накрывает несколько рёбер, то и считать её надо несколько раз); узнать, сколько есть четвёрок, накрывающих >=3 рёбер (опять же, если эти 3 ребра можно выбирать несколькими способами, то их все надо считать отдельными). Короче, нам надо научиться считать величину cnt[i], где i - это сколько рёбер мы покрываем, а cnt[i] - сколько есть таких четвёрок.

Тогда ответом на задачу будет величина:



(останавливаемся на 6 рёбрах, т.к. внутри одной четвёрки больше шести рёбер быть не может).

Дальше, казалось бы, надо лишь научиться считать эти величины, что должно быть более-менее просто, учитывая, что рёбер всего 4000. Однако дьявол, как говорится, кроется в мелочах 

Чему равно cnt[0] (т.е. количество любых четвёрок вершин) - узнать совсем просто, это n * (n - 1) * (n - 2) * (n - 3) / 24.

Так же просто узнать и cnt[1]: это m * (n - 2) * (n - 3) / 2 (поскольку для каждого ребра есть (n-2) * (n-3) / 2 способа подобрать к нему ещё две вершины, чтобы они образовывали четвёрку).

Для двух рёбер (cnt[2]) всё уже несколько сложнее. Давайте мы переберём пару рёбер ((a,b) и (c,d)), тогда, если все эти четыре вершины (a,b,c,d) различны - прибавляем к cnt[2] единицу, а вот если среди них есть пара одинаковых вершин - то прибавляем n-3. Откуда берётся это n-3? Но, в самом деле, если мы взяли два ребра, исходящих из одной и той же вершины, то эти два ребра покрыли лишь три вершины, а четвёртую мы можем брать произвольно (и способов сделать это будет как раз n-3).

Самый ад наступает, когда мы переходим к подсчёту величин cnt[3]...cnt[6]. (Мы помним о том, что нам подходит решение за O(m^2), не более того).

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

Исключения составляют только два случая: цикл длины 3, а также случай, когда из одной вершины исходят три ребра. В обоих этих случаях нельзя выделить два непересекающихся ребра, поэтому в описанном ниже решении такие конфигурации не посчитаются правильно. Но обе этих конфигурации - довольно просты, и их легко посчитать отдельно: найти все циклы длины 3 за O(m^2) (просто перебрав все пары рёбер, имеющих общую вершину), а со второй конфигурацией легко справиться, просто прибавив к cnt[3] сумму sz[v] * (sz[v] - 1) * (sz[v] - 2) / 6 по всем вершинам v.

Итак, теперь мы будем иметь дело только с такими конфигурациями, в которых можно найти два "опорных" ребра, которые не имеют общих вершин, а, значит, которые однозначно задают четвёрку вершин. Итак, мы перебираем все пары рёбер ((a,b) и (c,d)), проверяем, что среди (a,b,c,d) нет одинаковых, и переходим к центральной части решения (всё решение до этого - лишь прелюдия  ). Мы имеем четвёрку вершин (a,b,c,d), и нам надо что-то прибавить к ответам cnt[3]..cnt[6], учитывая эту четвёрку. Для этого посчитаем количество рёбер внутри этой четвёрки (a,b,c,d) - пусть это количество равно e. Тогда к cnt[3] мы должны прибавить C_e^3 (биномиальное число из e по 3), к cnt[4] - прибавить C_e^4, и т.д.

Но если мы просто так прибавим, то будет неправильно: а именно, есть две проблемы. Во-первых, так мы одни и те же четвёрки можем учесть несколько раз - но этого можно избежать, проверяя, не могли ли мы эту же четвёрку (a,b,c,d) получить другой парой рёбер ранее (это делается всего несколькими сравнениями). Во-вторых, так мы можем случайно учесть случаи цикла длины 3 и другую конфигурацию, которые мы и так уже учли в ответе. Поэтому после прибавления этих биномиальных коэффициентов мы должны ещё перебрать все способы выбрать цикл длины 3 и выбрать вторую конфигурацию из нашей четвёрки, и уменьшить cnt[3].


Ну, вот, такое вот идеологически монструозное решение, которое начиналось с невинной фразы "принцип включений-исключений"  Впрочем, как решать такую задачу по-другому за время O(m^2) или быстрее - я не знаю.


P.S. Поскольку быть уверенным в таком страшном решении было нельзя, я его сегодня реализовал и пустил тестироваться на случайных тестах (супротив тупого решения за O(n^4)). Решение оказалось правильным.

Это сообщение отредактировал(а) maxdiver - 22.12.2011, 22:07

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