2018-02-14
1747
Пример: (задан граф пересечений)
| u1 | u2 | u3 | u4 | u5 | u6 | |
| x1 | 1 | 1 | 1 | 0 | 0 | 0 |
| x2 | 1 | 0 | 0 | 1 | 0 | 0 |
| x3 | 0 | 1 | 0 | 1 | 1 | 0 |
| x4 | 0 | 0 | 1 | 0 | 0 | 1 |
| x5 | 0 | 0 | 0 | 0 | 1 | 1 |
1. Определение непополнимых внутренне устойчивых вершин графа.
Подмножество несмежных вершин графа называют внутренне устойчивым. Непополнимое внутренне устойчивое подмножество вершин графа - такое подмножество, что добавление любой вершины в это подмножество приведет к нарушению свойству внутренней устойчивости.
Представим граф пересечений в виде матрицы смежности S:
Образуем конъюнкцию дизъюнкций вершин, инцидентных каждому ребру:
ПG = (x1∨x2)∧(x1∨x3)∧(x1∨x4)∧(x2∨x3)∧(x3∨x5)∧(x4∨x5) =... приведем к ДНФ... =
= x1x2x5 ∨ x1x3x4 ∨ x2x3x4 ∨ x1x3x5 = (обозначим) = K1 ∨ K2 ∨ K3 ∨ K4
Тогда непополнимые внутренне устойчивые подмножества можно определить как Fi = X \ Ki, где X - полное множество вершин графа.
F1 = X \ K1 = {x1, x2, x3, x4, x5} \ {x1, x2, x5} = {x3, x4}
F2 = {x2, x5} F3 = {x1, x5} F4 = {x2, x4}
2. Получение матрицы V, определяющей вхождение вершины в каждое из этих подмножеств:
| 0 | F1 | F2 | F3 | F4 |
| x1 | 0 | 0 | 1 | 0 |
| x2 | 0 | 1 | 0 | 1 |
| x3 | 1 | 0 | 0 | 0 |
| x4 | 1 | 0 | 0 | 1 |
| x5 | 0 | 1 | 1 | 0 |
Образуем конъюнцию дизъюнкций подмножеств по вершинам:
v = F3∧(F2∨F4)∧F1∧(F1∨F4)∧(F2∨F3) = F3∧F1∧(F2∨F4) = F1F2F3 ∨ F1F3F4
В полученном выражении находится конъюнкция с наименьшим числом термов (для определенности возьмем F1F2F3) - это число и есть хроматическое число.
3. Распределение проводников по слоям
| F1 {x3, x4} | F2 {x2, x5} | F3 {x1, x5} | |
| 1 | {x3, x4} | {x2, x5} | {x1} |
| 2 | {x3, x4} | {x2} | {x1, x5} |
(таким образом, у нас - два варианта исключения повторяющихся вершин). Если k - количество повторяющихся вершин, то всего возможно 2k вариантов.
Эвристический алгоритм раскраски вершин графа.
1. Вершины графа пересечений упорядочиваются в невозрастающем порядке по локальной степени вершины.
2. Берется первая вершина (с самой большой локальной степенью вершины). Она окрашивается в цвет 1 и удаляется из списка.
3. В этот же цвет окрашиваются и другие вершины, которые не являются смежными с первой вершиной, а также между собой. Окрашенные вершины удаляются из списка.
4. Берется новый цвет и повторяются пункты 2-3 до тех пор, пока все вершины не окрашены.
Преимущество: высокое быстродействие
Недостаток: невысокое качество полученного результата
| x1 | x2 | x3 | x4 | x5 | x6 | x7 | r | ||
| x1 | 0 | 1 | 1 | 0 | 0 | 0 | 0 | 2 | |
| x2 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 4 | |
| x3 | 1 | 1 | 0 | 0 | 1 | 1 | 1 | 5 | |
| R= | x4 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 3 |
| x5 | 0 | 1 | 1 | 1 | 0 | 0 | 0 | 3 | |
| x6 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 2 | |
| x7 | 0 | 1 | 1 | 1 | 0 | 0 | 0 | 3 |
Упорядочиваем вершины по убыванию локальной степени: {x3,x2,x4,x5,x7,x1,x6}
Берём х3. Смежной с ней не является только вершина х4. Они окрашиваются в первый цвет.
Вычеркиваем из матрицы строки х3 и х4.
| x1 | x2 | x5 | x6 | x7 | r | ||
| x1 | 0 | 1 | 0 | 0 | 0 | 2 | |
| x2 | 1 | 0 | 1 | 0 | 1 | 4 | |
| R¢= | x5 | 0 | 1 | 0 | 0 | 0 | 3 |
| x6 | 0 | 0 | 0 | 0 | 0 | 2 | |
| x7 | 0 | 1 | 0 | 0 | 0 | 3 |
Новый список: {x2, x5,x7,x1,x6} Берём х2. С ней смежной не является вершина х6. Эти две вершины окрашиваются во второй цвет. Вычеркиваем из матрицы строки х2 и х6.
| x1 | x5 | x7 | r | ||
| x1 | 0 | 0 | 0 | 2 | |
| R¢¢= | x5 | 0 | 0 | 0 | 3 |
| x7 | 0 | 0 | 0 | 3 |
Новый список: { x5,x7,x1 } Берём х5. Вершины х7 и х1 обе не являются смежными с х5, а также между собой. Поэтому все три оставшиеся вершины окрашиваются в третий цвет.
