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