ОС - ВУМ

процессы, ребра общие данные.

X1

X2

X3

X4

X5

X6

и раскраска графа конфликтов.

X1

X2

X3

X4

X5

X6

Внутренне устойчивое множество (ВУМ) –
подмножество несвязанных вершин графа (не имеющих общих ребер).
Максимальное ВУМ – ВУМ, которое теряет свойство внутренней устойчивости при добавлении любой вершины из оставшихся.
Для нахождения ВУМ воспользуемся алгоритмом Магу.
Запишем логическое выражение: в ВУМ может войти либо одна, либо другая вершина каждого ребра. Минимизируем это выражение. Если полученные множества вершин исключить из множества всех вершин графа, то останется ВУМ.

+ X2*X4*X6 + X1*X3*X4*X5*X6 +X1*X2*X5*X6)=
X2*X3*X4+ X1*X3*X4*X5+ X1*X2*X3*X5 + X2*X4*X6 + X1*X2*X5*X6
ПОМОЩЬ: X*X=X, X+X=X, X1+X1*X2=X1,
(X1+X2)(X1+X3)=X1+X2*X3

X1*X3*X4*X5 ={X2,X6}
M3= X - X1*X2*X3*X5 ={X4,X6}
M4= X - X2*X4*X6={X1,X3,X5}
M5= X - X1*X2*X5*X6 ={X3,X4}
|M1|=|M4|=3 число внутренней устойчивости

1

2

3

4

5

Входящие в ВУМ вершины не конфликтуют по данным!!!

X - X1*X2*X3*X5 ={X4,X6}
M4= X - X2*X4*X6={X1,X3,X5}
M5= X - X1*X2*X5*X6 ={X3,X4}

Раскрасить граф – поставить в соответствие каждой вершине графа некоторый цвет так, чтобы смежные вершины были окрашены в разные цвета.

Запишем логическое выражение: каждая вершина может быть окрашена в один из цветов (ВУМ). Минимизируем это выражение. Наименьшее количество цветов – хроматическое число графа.

(М1+М4) *М2*(М4+М5) (М3+М5) (М1+М4) (М1+М2+М3)=
(М1*М2 + М2*М4) * (М5+М3*М4)=
М1*М2*М5+М2*М4*М5+М1*М2*М3*М4+М2*М3*М4*М5=
М1*М2*М5+М2*М4*М5+М1*М2*М3*М4

1

2

3

|C2|=3 (хроматическое число графа)