Алгоритмы на графах. Независимые и доминирующие множества

Если Q является семейством всех независимых множеств графа G, то число.Метод генерации всех максимальных независимых множеств графа.Множества вершин (1, 2) , (3, 4, 5) , (4, 7) , (5, 6) - независимые.Основная сложность алгоритма в выборе очередной вершины графа.В процессе решения нам придется многократно рассматривать вершины графа, смежные с данной.Упростим нахождение смежных вершин за счет использования нового способа описания графа.Используем множественный тип данных.Вершины, соединенные ребром, называются смежными.Ребра, имеющие общую вершину, также называются смежными.Ребро и любая из его двух вершин называются инцидентными.