 Метод Магу, Помощь в реализации |
Прочтите прежде чем задавать вопрос!
1. Заголовок темы должен быть информативным. В противном случае тема удаляется ...
2. Все тексты программ должны помещаться в теги [code=pas] ... [/code].
3. Прежде чем задавать вопрос, см. "FAQ", если там не нашли ответа, воспользуйтесь ПОИСКОМ, возможно такую задачу уже решали!
4. Не предлагайте свои решения на других языках, кроме Паскаля (исключение - только с согласия модератора).
5. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
6. Одна тема - один вопрос (задача)
7. Проверяйте программы перед тем, как разместить их на форуме!!!
8. Спрашивайте и отвечайте четко и по существу!!!
| Maxx |
 7.11.2006 14:04
Сообщение
#1
|
|
Группа: Пользователи Сообщений: 5 Пол: Мужской Реальное имя: Максим Репутация:  0   |
Помогите реализовать метод Магу отыскания семейства минимальных внешне устойчивых (доминирующих) множеств заданного орграфа.
Суть метода можно изложить в три шага: 1) По матрице смежности графа строится КНФ (в каждой скобке обязательно находится i-тая вершина, где i - номер скобки; и все оставшиеся вершины с ней смежные; количество скобок равно количеству вершин в графе); 2)Строим сокращенную ДНФ из КНФ, пользуясь правилами поглощения и дистрибутивности; 3)По сокращенной ДНФ выводим семейства. Например: матрица смежности графа: 01101 00100 00010 00000 00010 КНФ:(v1Vv2Vv3Vv5)^(v2Vv3)^(v3Vv4)^v4^(v5Vv4) Сокращенная ДНФ: v2v4Vv3v4 Семейство минимальных внешне устойчивых (доминирующих) множеств: v2v4;v3v4. Сообщение отредактировано: Maxx - 7.11.2006 20:17 |
   |
 
|
Сообщений в этой теме
Maxx Метод Магу 7.11.2006 14:04
мисс_граффити а на каком из этапов проблемы? 7.11.2006 18:39 Maxx Проблема встала на этапе 2: построение сокращенной... 7.11.2006 20:04
мисс_граффити посмотри вот здесь про преобразования. 10.11.2006 17:10  |
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0
|
Текстовая версия | 24.07.2025 0:17 |