1 Тема от Jt1k

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

Тема: Небольшой вопрос о вершинах в графе.

Доброго времени суток всем!!! Я решаю задачу о нахождении путей в графе, не пересекающихся по вершинам.  Решаю используя матрицу смежности и максимальный поток. Мне необходимо заменить все ребра двуноправленными дугами, а также заменить вершины ребрами(заменить вершины v вершинами v' и v'', соединенными ребром (v',v''), причем вершины, смежные с v, распределяются между новыми вершинами каким-то способом.) Как распределить смежные вершины? Заранее всем огромное спасибо!!!

2 Ответ от KADR

  • KADR
  • Участник
  • Неактивен
  • Откуда: Киев
  • Зарегистрирован: 2009-06-25
  • Сообщений: 231

Re: Небольшой вопрос о вершинах в графе.

Это можно сделать, например, так:
Пусть всего есть N вершин. Создадим новый граф, где каждой вершине V будет соответствовать пара V,V', причем номер вершины V' будет N+V. Если в изначальном графе вершина V была связана с W, тогда в новом графе добавим ребро из V в W'. Найдем в этом графе максимальное паросочетание. Тогда минимальное количество непересекающихся путей будет равно N-размер паросочетания.

3 Ответ от shona123

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

Re: Небольшой вопрос о вершинах в графе.

Как распределить смежные вершины? Заранее всем огромное спасибо..????

Whether you want to pass 1z0-238 exam exams or looking for testking certification, our bfit can provide guaranteed success in real exam of www.sckans.edu