 Метод Магу, Помощь в реализации |
Прочтите прежде чем задавать вопрос!
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 |
   |
 
|
| мисс_граффити |
7.11.2006 18:39
Сообщение
#2
|
 просто человек  Группа: Модераторы Сообщений: 3 641 Пол: Женский Реальное имя: Юлия Репутация: 55 |
а на каком из этапов проблемы?
-------------------- Все содержимое данного сообщения (кроме цитат) является моим личным скромным мнением и на статус истины в высшей инстанции не претендует.
На вопросы по программированию, физике, математике и т.д. в аське и личке не отвечаю. Даже "один-единственный раз" в виде исключения! |
|
|
|
| Maxx |
7.11.2006 20:04
Сообщение
#3
|
|
Группа: Пользователи Сообщений: 5 Пол: Мужской Реальное имя: Максим Репутация: 0 |
Проблема встала на этапе 2: построение сокращенной ДНФ (или просто ДНФ я уже точно не знаю, в одних источниках так в других по другому) из КНФ.
P.S. В классическом представлении КНФ (для данного примера) будет выглядеть, как двумерный массив: v1v2v3v5 v2v3 v3v4 v4 v5v4 Но как я не пытался у меня не получилось сделать преобразование с такой формой, потому что нужно поглотить, где можно и т.д. Сообщение отредактировано: Maxx - 7.11.2006 20:16 |
|
|
|
| мисс_граффити |
10.11.2006 17:10
Сообщение
#4
|
|
просто человек Группа: Модераторы Сообщений: 3 641 Пол: Женский Реальное имя: Юлия Репутация: 55 |
посмотри вот здесь про преобразования.
-------------------- Все содержимое данного сообщения (кроме цитат) является моим личным скромным мнением и на статус истины в высшей инстанции не претендует.
На вопросы по программированию, физике, математике и т.д. в аське и личке не отвечаю. Даже "один-единственный раз" в виде исключения! |
|
|
|
|
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0
|
Текстовая версия | 23.07.2025 11:46 |