Лекция: Построение Клики.

1. Строим дополнительный граф исходного графа.

G a

f b

e c

d

2. Найдем множество внутренней устойчивости для графа G.

(a Ú d)(a Ú e)(a Ú f)(b Ú c)(c Ú d)

(a Ú de)(a Ú f)(c Ú bd)

(a Ú def)(cÚ bd)

ac Ú cdef Ú bdef Ú abd

{b, d, e, f}, {c, e, f}, {a, b}, {a, c}

3. Множества полученных вершин дают всевозможные полные подграфы исходного графа G. Причем, максимальный из подграфов дает клику.