 Найти максимальный разрез в графе |
Прочтите прежде чем задавать вопрос!
1. Заголовок темы должен быть информативным. В противном случае тема удаляется ...
2. Все тексты программ должны помещаться в теги [code=pas] ... [/code].
3. Прежде чем задавать вопрос, см. "FAQ", если там не нашли ответа, воспользуйтесь ПОИСКОМ, возможно такую задачу уже решали!
4. Не предлагайте свои решения на других языках, кроме Паскаля (исключение - только с согласия модератора).
5. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
6. Одна тема - один вопрос (задача)
7. Проверяйте программы перед тем, как разместить их на форуме!!!
8. Спрашивайте и отвечайте четко и по существу!!!
  |
| Незнайка 013 |
 21.05.2008 18:45
Сообщение
#1
|
 Новичок  Группа: Пользователи Сообщений: 11 Пол: Мужской Реальное имя: Евгений Репутация:  0   |
НАРОД,ПОМОГИТЕ !!!!!!!!!!
нужно написать прогу на паскале ищущюю максимальный разрез в графе.Искал в и-нете ничего не нашёл  |
   |
 
|
| trew |
21.05.2008 19:02
Сообщение
#2
|
 Пионер в программировании Группа: Пользователи Сообщений: 66 Пол: Мужской Репутация: 0 |
постораемся
а у тебя нет набросков |
|
|
|
| Незнайка 013 |
21.05.2008 20:14
Сообщение
#3
|
|
Новичок Группа: Пользователи Сообщений: 11 Пол: Мужской Реальное имя: Евгений Репутация: 0 |
К сожалению вобще ничего нет :-(
|
|
|
|
| trew |
21.05.2008 20:34
Сообщение
#4
|
|
Пионер в программировании Группа: Пользователи Сообщений: 66 Пол: Мужской Репутация: 0 |
зайди в мою тему
volvo |
|
|
|
| volvo |
21.05.2008 20:54
Сообщение
#5
|
|
Гость |
Граф какой? Нахождение максимального разреза (maximal cut) - это NP-полная задача... Существует несколько алгоритмов для планарных графов, работающих за полиномиальное время: 0.5-randomized approximation algorithm и 0.878-approximation algorithm by Goemans and Williamson (если что - информация из англоязычной Википедии)... Можешь поискать информацию по этим алгоритмам, но скорее всего русскоязычных источников не найдешь...
Есть в сети и программы, реализующие поиск макс. разреза, но поскольку они не на Паскале - если нужно - обращайся в личку, дам ссылку... |
|
|
|
| Незнайка 013 |
21.05.2008 22:34
Сообщение
#6
|
|
Новичок Группа: Пользователи Сообщений: 11 Пол: Мужской Реальное имя: Евгений Репутация: 0 |
В условии так и сказано В ГРАФЕ (в каком ? - нет)
|
|
|
|
|
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0
|
Текстовая версия | 24.04.2024 19:21 |