 |
|
|
 
|
|
Удаление дорог между городами, задача на графы 
| Чупакабро |
|
|||
 Бывалый  Профиль Группа: Участник Сообщений: 220 Регистрация: 27.2.2007 Репутация: нет Всего: 4 |
Помогите решить задачу:
Есть N городов. Между некоторыми из них имеются дороги, которые нигде не пересекаются. Каждая дорога задаётся парой городов, которые она соединяет. Какое минимальное число дорог нужно удалить, чтобы из города с номером i нельзя было проехать в город с номером j. Буду благодарен за подсказку, куда копать или за ссылку --------------------
Project Project1.exe raised exception class EAccessViolation with message 'Access violation at address 00459B8B in module 'Project1.exe'. Read of address 0000019C'. Process stopped. Use Step or Run to continue. |
|||
|
||||
Загрузка ...
| 1000000dollars |
|
|||
 Бывалый Профиль Группа: Участник Сообщений: 231 Регистрация: 6.10.2007 Репутация: 1 Всего: 8 |
При текущей постановке задачи от нуля до бесконечности.
Копать в теорию графов и сетей. |
|||
|
||||
| Чупакабро |
|
||||
|
Бывалый Профиль Группа: Участник Сообщений: 220 Регистрация: 27.2.2007 Репутация: нет Всего: 4 |
Что не так с постановкой задачи? мне нужен алгоритм, разве его не существует при такой постановке?
Очень растяжимое понятие... Смотрел максимальный поток и минимальное сечение, но что-то это, видимо, не то. --------------------
Project Project1.exe raised exception class EAccessViolation with message 'Access violation at address 00459B8B in module 'Project1.exe'. Read of address 0000019C'. Process stopped. Use Step or Run to continue. |
||||
|
|||||
| Pavia |
|
|||
|
Опытный Профиль Группа: Участник Сообщений: 418 Регистрация: 6.12.2008 Репутация: 11 Всего: 12 |
Задача такова разделить граф на два графа путем удаления минимального числа ребер. При этом две данных вершины попа в разные подграфы.
Я бы посмотрел в сторону минимального разрезание графа (graph cut). Если найдешь решения напиши. |
|||
|
||||
| maxdiver |
|
|||
|
Опытный Профиль Группа: Участник Сообщений: 381 Регистрация: 29.1.2008 Где: Саратов Репутация: 16 Всего: 18 |
Да, это постановка задачи нахождения минимального разреза между двумя заданными вершинами. Обычное решение - с помощью графовых потоков: одну вершину делаем истоком, другую стоком, пропускные способности каждого ребра полагаем равными их стоимостям, ищем максимальный поток в полученном графе (см. алгоритм Форда-Фалкерсона), и затем к одной компоненте относим все вершины, достижимые из истока по не полностью насыщенным рёбрам, к другой компоненте относим все остальные вершины, а сами искомые рёбра, которые надо удалить - это все рёбра между разными компонентами.
|
|||
|
||||
| Чупакабро |
|
|||
|
Бывалый Профиль Группа: Участник Сообщений: 220 Регистрация: 27.2.2007 Репутация: нет Всего: 4 |
Спасибо всем ответившим, но окончательно вопрос так и не прояснился. Вот, посмотрите:
Присоединённый файл ( Кол-во скачиваний: 22 ) 
______.JPG 94,10 Kb--------------------
Project Project1.exe raised exception class EAccessViolation with message 'Access violation at address 00459B8B in module 'Project1.exe'. Read of address 0000019C'. Process stopped. Use Step or Run to continue. |
|||
|
||||
| maxdiver |
|
|||
|
Опытный Профиль Группа: Участник Сообщений: 381 Регистрация: 29.1.2008 Где: Саратов Репутация: 16 Всего: 18 |
Ещё раз: в первую группу отнесём вершины, достижимые из истока по не полностью насыщенным рёбрам.
Видимо, не получилось потому, что для графа с неориентированными вершинами есть тонкость: каждое неор. ребро распадается на 2 ор. ребра в обе стороны, а у каждого этого ребра есть ещё по собственному обратному ребру. По обратному ребру, согласно определению, можно пройти, если по соответствующему прямому ребру протек ненулевой поток. Поэтому из 2 в 3 и обратно мы пройти могли - по обратным рёбрам. Ещё, скажем, мы могли бы пройти из 5 в 2 или из 6 в 3 (но они не достижимы из истока). |
|||
|
||||
| Чупакабро |
|
|||
|
Бывалый Профиль Группа: Участник Сообщений: 220 Регистрация: 27.2.2007 Репутация: нет Всего: 4 |
Ну, если так, то я программу написал правильно... Спасибо --------------------
Project Project1.exe raised exception class EAccessViolation with message 'Access violation at address 00459B8B in module 'Project1.exe'. Read of address 0000019C'. Process stopped. Use Step or Run to continue. |
|||
|
||||
|
|
| Правила форума "Алгоритмы" | |
|
|
Форум "Алгоритмы" предназначен для обсуждения вопросов, связанных только с алгоритмами и структурами данных, без привязки к конкретному языку программирования и/или программному продукту.
Если Вам понравилась атмосфера форума, заходите к нам чаще! С уважением, maxim1000. |
| 0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей) | |
| 0 Пользователей: | |
| « Предыдущая тема | Алгоритмы | Следующая тема » |
[ Время генерации скрипта: 0.0479 ] [ Использовано запросов: 21 ] [ GZIP включён ]
Реклама на сайте Информационное спонсорство
|
|
По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности Powered by Invision Power Board(R) 1.3 © 2003 IPS, Inc. |