Покрытие графа циклами?

Question

[floppa322]

Немного не понял доказательство (оно под ней сразу) к лемме 2.18

Разве это нельзя намного проще доказать: в графе бывают вершины (in deg = 0, out deg = 0), пути (все in deg = 1, out deg = 1, кроме 2-х вершин - начало и конец) и циклы (все вершины in deg = 1, out deg = 1). В полном паросочетании (если левая доля это out а правая in) у каждой вершины out deg = 1 ну и поскольку паросочетание полное, то и in deg = 1, значит тут нет ни просто вершин, ни путей, а только циклы (т.е. паросочетание просто назначает одновременно in и out deg вершинам). Ну а если покрытие было, а он его не нашёл (парсоч < n), то как такое могло получиться, ведь у покрытия Σin = Σout = n, что в точности полный парсоч. Или здесь что-то не учтено ?

p.s.: ещё немного смущает, что такой алгоритм может найти разбиение графа на тривиальные циклы длиной 2: i->j, j->i

Answer 1

[Wataru]

Вы расписали то, что в доказательстве скрывается за "clearly, any 2-factor of G translates into a perfect matching of G' and vice versa". Можно было бы чуть поформальнее, но основная идея правильная. Или можно еще проще: разбиение на циклы равносильно перестановке, которая для каждой вершины задает следующую в цикле. Перестановка равнозначна максимальному паросочетанию.

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

Comments

[floppa322]

Спасибо за ответ

Или можно еще проще: разбиение на циклы равносильно перестановке, которая для каждой вершины задает следующую в цикле. Перестановка равнозначна максимальному паросочетанию.

а, ну да, видимо про маппинг в обе стороны это и имелось в виду

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

как я понял, для неориентированных графов нет алгоритма, чтобы он нет включал циклы длины 2, мб только, если он нашёл дополняющий путь i->j, j->i, какую-то персистентность алгоритму добавить, чтобы он назад до некоторого состояния алгоритма откатился и попробовал пойти "в другую сторону" искать дополняющий путь, но может так получиться, что ему придётся откатиться до самого старта и просто стартовать с другой вершины

[floppa322]

https://cstheory.stackexchange.com/questions/46819...

хотя видимо с циклами длины больше 2 есть серьёзные проблемы

[Wataru]

floppa322, Да, исключить циклы длины 2 очень не просто.