Новые сообщения [новые:0]
Дайджест
Горячие темы
Избранное [новые:0]
Форумы
Пользователи
Статистика
Статистика нагрузки
Мод. лог
Поиск
|
|
28.03.2010, 13:10:23
|
|||
|---|---|---|---|
Минимальный разрез в графе |
|||
|
#18+
Здравствуйте! Подскажите пожалуйста алгоритм поиска минимального разреза в графе и ребер, которые входят в этот разрез. Для графа я нашел с помощью алгоритма Форда-Фалкерсона максимальный поток. Как написано в книге по теории графов Величина Максимального потока равна Величине Минимального разреза. А как найти ребра, которые входят в этот разрез. Граф задан матрицей смежности Искал и в Гугле и в Яндексе но че то непонятно там как то, в книге Кристофедеса тоже про этот алгоритм че то не сказано. Буду благодарен также за ссылку с описанием этого алгоритма с примером ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
28.03.2010, 14:45:18
|
|||
|---|---|---|---|
Минимальный разрез в графе |
|||
|
#18+
Если ты нашёл вершины то и рёбра тоже сможешь найти. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
03.04.2010, 13:58:13
|
|||
|---|---|---|---|
|
|||
Минимальный разрез в графе |
|||
|
#18+
После завершения поиска максимального потока алгоритмом Форда-Фулкерсона, у тебя должна остаться некоторая остаточная сеть (residual network), в которой не существует маршрута от источника к стоку. Для нахождения минимального разреза, необходимо: 1. построить множество вершин, достижимых из стока в этой остаточной сети (поиск в глубину пройдёт на ура); 2. все рёбра исходного графа, инцидентные одной и только одной вершине из построенного множества, и будут составлять минимальный разрез. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
start [/forum/topic.php?fid=16&mobile=1&tid=1343779]: |
0ms |
get settings: |
9ms |
get forum list: |
14ms |
check forum access: |
2ms |
check topic access: |
2ms |
track hit: |
35ms |
get topic data: |
9ms |
get forum data: |
2ms |
get page messages: |
39ms |
get tp. blocked users: |
1ms |
| others: | 191ms |
| total: | 304ms |
| 0 / 0 |
