Версия для печати темы
Нажмите сюда для просмотра этой темы в обычном формате
Форум «Всё о Паскале» _ Задачи _ Найти максимальный разрез в графе
Автор: Незнайка 013 21.05.2008 22:45
НАРОД,ПОМОГИТЕ !!!!!!!!!!
нужно написать прогу на паскале ищущюю максимальный разрез в графе.Искал в и-нете ничего не нашёл 
Автор: trew 21.05.2008 23:02
постораемся
а у тебя нет набросков
Автор: Незнайка 013 22.05.2008 0:14
К сожалению вобще ничего нет :-(
Автор: trew 22.05.2008 0:34
зайди в мою тему
volvo
Автор: volvo 22.05.2008 0:54
Граф какой? Нахождение максимального разреза (maximal cut) - это NP-полная задача... Существует несколько алгоритмов для планарных графов, работающих за полиномиальное время: 0.5-randomized approximation algorithm и 0.878-approximation algorithm by Goemans and Williamson (если что - информация из англоязычной Википедии)... Можешь поискать информацию по этим алгоритмам, но скорее всего русскоязычных источников не найдешь...
Есть в сети и программы, реализующие поиск макс. разреза, но поскольку они не на Паскале - если нужно - обращайся в личку, дам ссылку...
Автор: Незнайка 013 22.05.2008 2:34
В условии так и сказано В ГРАФЕ (в каком ? - нет)