Алгоритмы раскраски графа
5. Если R ≠ ∅, то переход к п. 2, иначе к п. 6; 1. В матрице соединений R для каждой вершины подсчитывается число ненулевых элементов ri; 2. Находится вершина xi с max ri, если таких вершин несколько, то выбирается любая; 3. Для выбранной вершины xi записывается выражение Ci = (xi ∨ xa xb...xq), где Гxi = {xa, xb, ..., xq}; 4. Из матрицы R удаляются строка и столбец, соответствующие вершине xi; 6. Составляется конъюнкция П = ∧Ci. Раскрываются скобки. В полученной дизъюнкции на основе законов булевой алгебры выполняется минимизация. 7. Результат минимизации записывается в виде П = ∨ Kj; 9. Для каждой вершины xi∈Х определяются подмножества ϕj, в которые входит вершина xi∈ϕj. Составляется дизъюнкция ti = ∨ϕj; 8. Для каждого Kj ищутся вершины графа, не вошедшие в него. Получено ϕj и семейство МВУМ Ψ = {ϕ1, ϕ2, ..., ϕl}; 10. Составляется конъюнкция П’ = ∧ti. Раскрываются скобки. В полученной дизъюнкции на основе законов булевой алгебры выполняется минимизация; 11. Получена дизъюнкция конъюнктивных термов П’ = ∨(∧ϕj). Выбирается конъюнктивный терм ∧ϕj с минимальным числом сомножителей. Количество сомножителей в этом терме и есть хроматическое число графа. Число минимальных термов – число вариантов раскраски графа. А каждое ϕj – множество вершин, которые можно окрасить в один цвет. Заметим, что п.п. 1-8 составляют метод Магу, а п.п. 9-11 – метод Петрика.
