Построение Клики

Клика

Клика - максимально большой полный подграф данного графа.

a

f b

e c

d

	a	b	c	d	e	f
a
b
c
d
e
f

	a	b	c	d	e	f
a
b
c
d
e
f

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. Причем, максимальный из подграфов дает клику.

Дата добавления: 2014-01-06