Структурный анализ графов. Максимальные полные и максимальные пустые подграфы

Ключевые понятия к данной теме:
─ подграф графа;
─

Постановка задачи

Требуется найти в графе G =(X,U) все максимальные
пустые подграфы.

Определение максимального

G1=(X,U): X={(3,2)}; U =Ø

G2=(X,U): X= {(4,1)}; U = Ø

G3=(X,U): X= {(5)};

Независимое множество вершин
(внутренне устойчивое множество)

максимальные пустые подграфы

граф G = (X,U)

нахождения в графе G всех
максимальных пустых подграфов

Рассмотрим алгоритм Х.Магу, Дж.Уэйсмана

Законы алгебры логики

Эквивалентные преобразования

f = x1v x2

f = x1x2 v x1x2

f

(a+b) (a+c)… (a+p)= a+bc…p

x v xy = x

операция поглощения

операция склеивания

x(x  y) =  (xx  xy) = x 

Дан граф G=(X,U)

граф G=(X,U)

Усовершенствованная матрица инциденций графа G=(X, U).

Для её получения вводится система «псевдобулевских»

граф G=(X,U)

Составим произведение П:

ПG = (x1 + x3) (x2 + x3) (x2

Получили произведение П:

ПG = x1x2x4x6 + x1x2x4x7 + x1x2x5x6 + x2x3x4x6

S=

(x3x5x7), (x3x5x6), (x3x4x7), (x1x2 x5x6), (x1x2x4), (x1x5x7), (x1x4x7).

Алгебраические дополнения:

П = x1x2x4x6

S=

(x3x5x7), (x3x5x6), (x3x4x7), (x1x2 x5x6), (x1x2x4), (x1x5x7), (x1x4x7)

Максимальные пустые подграфы графа

Раскраска графа

Правильная раскраска вершин графа

Хроматическое число графа

Хроматическое число графа — минимальное

Максимальные пустые подграфы:

5

Алгебраические дополнения:

5

Алгебраические дополнения:

5

Максимальные полные подграфы

Задача : найти в графе G все максимальные полные подграфы.

Решение.

П= (x1+x4x3)(x3 + x5) = x1x3 +x1x5 +
+x4x3 +x4x3x5.

Алгебраические дополнения:
S

Раскраска графа

Пример рёберной правильной раскраски с помощью алгоритма Дж.Магу, Х.Уэйсмана

П =

Пg* = (1 + 23)(3+ 245)(4+5) = (13+1245+23+2345)(4+5) =
= 134+135+1245+234+2345+2345

Пример 2