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