1 Тема от Zayakin_Andrey Отредактировано Zayakin_Andrey (2011-02-14 17:45:54)

  • Зарегистрирован: 2009-06-21
  • Сообщений: 28

Тема: Задачи о покрытиями графа циклами.

Задача :
дан направленный взешенный граф без кратных ребер и петель (V <= 200, E <= 20000). Нужно покрыть его ориентированными циклами так чтобы каждая вершина принадлежала ровно одному циклу и сумма весов всех циклов была минимальна.

Решение :
построим двудольный граф, где в правой доле будут копии вершин. Если в графе было ребро (u; v) с весом w, проведем ребро из u первой доли в v второй доли c весом w. Теперь найдем максимальное паросочетание минимального веса. Если количество ребер равно количеству вершин исходного графа, то граф покрывается циклами и вес этого паросочетания равен искомой величине, иначе покрытия не существует.
Объясните, почему это правильно.

2 Ответ от 2rf

  • 2rf
  • Участник
  • Неактивен
  • Зарегистрирован: 2009-08-14
  • Сообщений: 42

Re: Задачи о покрытиями графа циклами.

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

3 Ответ от goodman

  • goodman
  • Участник
  • Неактивен
  • Зарегистрирован: 2011-12-07
  • Сообщений: 1

Re: Задачи о покрытиями графа циклами.

а какой алгоритм будет для неориентированного графа?

4 Ответ от ilyaraz

  • ilyaraz
  • Участник
  • Неактивен
  • Зарегистрирован: 2012-01-26
  • Сообщений: 1

Re: Задачи о покрытиями графа циклами.

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

5 Ответ от e-maxx

  • e-maxx
  • admin
  • Неактивен
  • Откуда: Саратов
  • Зарегистрирован: 2009-06-10
  • Сообщений: 360

Re: Задачи о покрытиями графа циклами.

ilyaraz пишет:

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

Правильно ли я понимаю, что это сведение нетривиально, и первым его привёл Эдмондс?
(в 1964 г.; я пытался разобраться по этой статье, но не смог понять, как решать данную задачу)
Также нашлась статья Hartvigsen, но не менее понятная.

Сайтe-maxx