Контрольная по дискретной математике

нет

В графе, представленном следующей матрицей смежности, найти все максимальные независимые множества и одно наименьшее доминирующее множество.


Решение.
Построим последовательность, где S10 представляет совокупность независимых множеств:
S1={1};
S2={{1},{2}};
S3={{1,3},{2,3}};
S4={{1,3,4},{2,3},{3,4}};
S5={{1,3,4},{2,3},{3,4,5}};
S6={{1,3,4},{2,3},{3,4,5},{2,6},{4,6},{5,6}};
S7={{1,3,4},{2,3},{3,4,5},{2,6,7},{4,6,7},{5,6},{1,7},{6,7}};
S7={{1,3,4},{2,3},{3,4,5},{2,6,7},{4,6,7},{5,6},{1,7},{6,7}};
S8={{1,3,4},{2,3},{3,4,5,8},{2,6,7,8},{4,6,7,8},{5,6,8},{1,7},{6,7,8}};
S9={{1,3,4},{2,3},{3,4,5,8,9},{2,6,7,8},{4,6,7,8},{5,6,8},{1,7,9},{6,7,8},{7,9)};
S10={{1,3,4},{2,3},{3,4,5,8,9},{2,6,7,8,10},{4,6,7,8},{5,6,8,10},{1,7,9},{6,7,8},{7,9,10},{8,10}};
Последняя строка представляет совокупность всех максимальных независимых множеств заданного графа.
Чтобы свести данную задачу к задаче о кратчайшем покрытии, преобразуем матрицу смежности заданного графа, подставив единицы по всем элементам главной диагонали:

Минимальная совокупность строк, где каждый столбец имеет единицу хотя бы в одной из этих строк, соответствует наименьшему доминирующему множеству.
Согласно 1-му правилу редукции удаляем

нет