Версия для печати темы

Нажмите сюда для просмотра этой темы в обычном формате

Форум «Всё о Паскале» _ Задачи _ Метод Магу

Автор: Maxx 7.11.2006 18:04

Помогите реализовать метод Магу отыскания семейства минимальных внешне устойчивых (доминирующих) множеств заданного орграфа.
Суть метода можно изложить в три шага:
1) По матрице смежности графа строится КНФ (в каждой скобке обязательно находится i-тая вершина, где i - номер скобки; и все оставшиеся вершины с ней смежные; количество скобок равно количеству вершин в графе);
2)Строим сокращенную ДНФ из КНФ, пользуясь правилами поглощения и дистрибутивности;
3)По сокращенной ДНФ выводим семейства.
Например:
матрица смежности графа:
01101
00100
00010
00000
00010

КНФ:(v1Vv2Vv3Vv5)^(v2Vv3)^(v3Vv4)^v4^(v5Vv4)
Сокращенная ДНФ: v2v4Vv3v4
Семейство минимальных внешне устойчивых (доминирующих) множеств: v2v4;v3v4.

Автор: мисс_граффити 7.11.2006 22:39

а на каком из этапов проблемы?

Автор: Maxx 8.11.2006 0:04

Проблема встала на этапе 2: построение сокращенной ДНФ (или просто ДНФ я уже точно не знаю, в одних источниках так в других по другому) из КНФ.
P.S. В классическом представлении КНФ (для данного примера) будет выглядеть, как двумерный массив:

v1v2v3v5
v2v3
v3v4
v4
v5v4
Но как я не пытался у меня не получилось сделать преобразование с такой формой, потому что нужно поглотить, где можно и т.д.

Автор: мисс_граффити 10.11.2006 21:10

посмотри http://forum.pascal.net.ru/index.php?showtopic=6976&st=0 про преобразования.