Далее отсортируем вершины таким образом, чтобы их степени убывали: 2 6 3 7 1 4 8 5 Р1 Р2 Р2 Р3 Р3 Р4 Р3 Р1 Первую неокрашенную вершину раскрашиваем в Р1, далее проверяем наличие связи со следующей неокрашенной вершиной. В данном случае в Р1 окрасится 5ая вершина. По этому же принципу раскрашиваем оставшиеся вершины графа. В результате получаем близкую к минимальной раскраску вершин графа.
2. Получить минимальную систему ДНФ для следующей системы полностью определенных булевых функций: x1 x2 x3 x4 f1 f2 f3 [█(1 0 1 0@0 0 1 0@0 0 0 0@0 1 1 1@0 1 0 0@0 1 1 0@0 1 0 1@0 0 0 1)] [█(0 1 0@0 0 1@1 0 0@1 1 0@1 0 1@1 0 1@1 1 0@0 1 0)] Решение: Минимизируем данную систему ДНФ методом Квайна-Мак-Класки. В СДНФ функций f1, f2, f3 заменим все конституенты единицы их двоичными кодами: f =1010(2)+0010(3)+0000(1)+0111(1,2)+0100(1,3)+0110(1,3)+0101(1,2)+0001(2) Образуем группы двоичных номеров. Признаком образования i-ой группы является i единиц в двоичном номере конституенты единицы. 0: 0000(1) 1: 0010(3) 0100(1,3) 0001(2) 2: 1010(2) 0110(1,3) 0101(1,2) 3: 0111(1,2) 4: - Склеим номера из соседних групп х_ _ _ : - _х_ _ : 0х00(1) 0х10(3) 0х01(2) _ _х_ : 01х0(1,3) 01х1(1,2) : 01хх(1) _ _ _х : 010х(1) 011х(1) : 01хх(1)
Вычислим значения , где - число столбцов таблицы переходов, в которых строки и имеют одинаковые элементы, т.е. число значений переменной , при которых . Таблица переходов: 00 01 11 10 1 2 3 2 1 2 1 4 3 1 3 - 2 - 4 4 3 1 2 1
А , где - число состояний автомата, - число пар вида , причем и , а входные символы и имеют соседние коды, удобно задать в виде таблицы:
5 3 3
2 1
1
где строки и столбцы соответствуют состояниям автомата. На первом шаге получаем два одномерных гиперкуба с максимальными значениями весов и .
А теперь выберем один двумерный гиперкуб, для которого выбираются два ребра с максимальной суммой весов.
Получаем один двумерный гиперкуб с максимальным весом добавленных ребер.
Теперь можем составить таблицу кодирования состояний:
0 0
1 0
1 1
0 1
Минимальная система булевых функций, описывающая заданное поведение, представляется следующими матрицами:
