Алгоритм определения внешне устойчивых множеств вершин

Используя полученные результаты, алгоритм нахождения всех доминирующих множеств вершин графа можно сформулировать следующим образом:

1. Получить матрицу A’ =EvA.

2. Обозначить вершины графа логическими переменными, например, x₁,x₂,x₃,…,x_n, гдеx_i= 1, если вершина принадлежит какому либо внешне устойчивому множеству, иx_i= 0 в противном случае.

3. Для каждой вершины графа, используя матрицу A’, записать выражение

где – x_iвершина, соответствующая выбранной строке,

x_k,x_l,…,x_q– вершины, смежные ей.

Для изолированных вершин, а для орграфа и для тупиковых вершин, логические выражения будут содержать по одной переменной.

4. Сформировать логическое выражение в виде произведения полученных сумм

П = C_i C_j …C_k.

4. Провести преобразования логического выражения П для получения минимальной дизъюнктивной нормальной формы (МДНФ).

5. Каждая конъюнкция полученной МДНФ будет являться доминирующим множеством вершин графа, а количество переменных в минимальной из них будет числом внешней устойчивости данного графа β(G). В совокупности получим семейство из всех внешне устойчивых множеств графа.