Материал: Дискретная математика. учебное пособие. Собенина О.В

Опишем алгоритм нахождения всех максимальных независимых множеств вершин графа.

Начальная установка.

Шаг 1. Пусть S₀ = Q₀^- = , Q₀⁺= X, k=0.

Прямой шаг.

Шаг 2. Выбрать вершину x_ikQ_k⁺ и сформировать S_k+1, Q_k^-₊₁ и Q_k⁺₊₁, оставив Q_k^- и Q_k⁺ нетронутыми. Положить k=k+1.

Проверка.

Шаг 3. Если выполняется условие (4.5), то перейти к шагу 5 иначе к шагу 4.

Шаг 4. Если Q_k⁺=Q_k^- =, то напечатать максимальное независимое множество S_k и перейти к шагу 5. Если Q_k⁺=, а Q_k^-, то перейти к шагу 5, иначе  к шагу 2.

Шаг возвращения.

Шаг 5. Положить k=k–1. Удалить x_ik из S_k+1, чтобы получить S_k. Исправить Q_k⁺ и Q_k^-, удалив вершину x_ik из Q_k⁺ и добавив ее к Q_k^-. Если k0, то перейти к шагу 3, иначе если Q₀⁺=, то остановиться (к этому моменту будут напечатаны все максимальные независимые множества), иначе перейти к шагу 2.

П ример. Найти все максимальные независимые множества графа G.

Матрица смежности графа G:

А=		x1	x2	x3	x4	x5	x6	x7
	x1	0	1	1	0	0	0	0
	x2	1	0	0	1	0	1	0
	x3	1	0	0	0	1	0	1
	x4	0	1	0	0	1	1	0
	x5	0	0	1	1	0	0	1
	x6	0	1	0	1	0	0	1
	x7	0	0	1	0	1	1	0

1. Начальная установка:

S₀ = Ø; Q₀^- = Ø; Q₀⁺ = {x₁, x₂, x₃, x₄, x₅, x₆, x₇}; k=0.

2. Прямой шаг:

x₁; S₁ = {x₁}; Q₁^- = Ø; Q₁⁺ = {x₄, x₅, x₆, x₇}; k = 1.

3. Проверка.

Условие не выполняется, переходим к шагу 4 (→ 4).

4. Условие не выполняется → 2.

2. x₄; S₂ = {x₁, x₄}; Q₂^- = Ø; Q₂⁺ = {x₇}; k = 2.

3. Условие не выполняется → 4.

4. Условие не выполняется → 2.

2. x₇; S₃ = {x₁, x₄, x₇}; Q₃^- = Ø; Q₃⁺ = Ø; k = 3.

3. Условие не выполняется → 4.

4. S₃ = {x₁, x₄, x₇}  максимальное независимое множество → 5.

5. k = 2; S₂ = {x₁, x₄}; Q₂^- = {x₇}; Q₂⁺ = Ø → 3.

3. Условие выполняется → 5.

5. k = 1; S₁ = {x1}; Q₁^- = {x₄}; Q₁⁺ = {x₅, x₆, x₇} → 3.

3. Условие не выполняется → 4.

4. Условие не выполняется → 2.

2. x₅; S₂ = {x₁, x₅}; Q₂^- = Ø; Q₂⁺ = {x₆}; k = 2.

3. Условие не выполняется → 4.

4. Условие не выполняется → 2.

2. x₆; S₃ = {x₁, x₅, x₆}; Q₃^- = Ø; Q₃⁺ = Ø; k = 3.

3. Условие не выполняется → 4.

4. S₃ = {x₁, x₅, x₆}  максимальное независимое множество → 5.

5. k = 2; S₂ = {x₁, x₅}; Q₂^- = {x₆}; Q₂⁺ = Ø → 3.

3. Условие выполняется → 5.

5. k = 1; S₁ = {x₁}; Q₁^- = {x₄, x₅}; Q₁⁺ = {x₆, x₇} → 3.

3. Условие не выполняется → 4.

4. Условие не выполняется → 2.

2. x₆; S₂ = {x₁, x₆}; Q₂^- = {x₅}; Q₂⁺ = Ø; k = 2.

3. Условие выполняется → 5.

5. k = 1; S₁ = {x₁}; Q₁^- = {x₄, x₅, x₆}; Q₁⁺ = {x₇} → 3.

3. Условие выполняется → 5.

5. k = 0; S₀ = Ø; Q₀^- = {x₁}; Q₀⁺ = {x₂, x₃, x₄, x₅, x₆, x₇} → 2.

2. x₂; S₁ = {x₂}; Q₁^- = Ø; Q₁⁺ = {x₃, x₅, x₇}; k = 1.

3. Условие не выполняется → 4.

4. Условие не выполняется → 2.

2. x₃; S₂ = {x₂, x₃}; Q₂^- = Ø; Q₂⁺ = Ø; k = 2.

3. Условие не выполняется → 4.

4. S₂ = {x₂, x₃} — максимальное независимое множество → 5.

5. k = 1; S₁ = {x₂}; Q₁^- = {x₃}; Q₁⁺ = {x₅, x₇} → 3.

3. Условие не выполняется → 4.

4. Условие не выполняется → 2.

2. x₅; S₂ = {x_2, x₅}; Q₂^- = Ø; Q₂⁺ = Ø; k = 2.

3. Условие не выполняется → 4.

4. S₂ = {x₂, x₅} — максимальное независимое множество → 5.

5. k = 1; S₁ = {x₂}; Q₁^- = {x₃, x₅}; Q₁⁺ = {x₇} → 3.

3. Условие не выполняется → 4.

4. Условие не выполняется → 2.

2. x₇; S₂ = {x₂, x₇}; Q₂^- = Ø; Q₂⁺ = Ø; k = 2.

3. Условие не выполняется → 4.

4. S₂ = {x₂, x₇} — максимальное независимое множество → 5.

5. k = 1; S₁ = {x₂}; Q₁^- = {x₃, x₅, x₇}; Q₁⁺ = Ø → 3.

3. Условие выполняется → 5.

5. k = 0; S₀ = Ø; Q₀^- = {x₁, x₂}; Q₀⁺ = {x₃, x₄, x₅, x₆, x₇} → 3.

3. Условие не выполняется → 4.

4. Условие не выполняется → 2.

2. x₃; S₁ = {x₃}; Q₁^- = {x₂}; Q₁⁺ = {x₄, x₆}; k = 1.

3. Условие не выполняется → 4.

4. Условие не выполняется → 2.

2. x₄; S₂ = {x₃, x₄}; Q₂^- = Ø; Q₂⁺ = Ø; k = 2.

3. Условие не выполняется → 4.

4. S₂ = {x₃, x₄} — максимальное независимое множество → 5.

5. k = 1; S₁ = {x₃}; Q₁^- = {x₂, x₄}; Q₁⁺ = {x₆} → 3.

3. Условие не выполняется → 4.

4. Условие не выполняется → 2.

2. x₆; S₂ = {x₃, x₆}; Q₂^- = Ø; Q₂⁺ = Ø; k = 2.

3. Условие не выполняется → 4.

4. S₂ = {x₃, x₆} — максимальное независимое множество → 5.

5. k = 1; S₁ = {x₃}; Q₁^- = {x₂, x₄, x₆}; Q₁⁺ = Ø → 3.

3. Условие выполняется → 5.

5. k = 0; S₀ = Ø; Q₀^- = {x₁, x₂, x₃}; Q₀⁺ = {x₄, x₅, x₆, x₇} → 2.

2. x₄; S₁ = {x₄}; Q₁^- = {x₁, x₃}; Q₁⁺ = {x₇}; k = 1.

3. Условие выполняется → 5.

5. k = 0; S₀ = Ø; Q₀^- = {x₁, x₂, x₃, x₄}; Q₀⁺ = {x₅, x₆, x₇} → 2.

2. x₅; S₁ = {x₅}; Q₁^- = {x₁, x₂}; Q₁⁺ = {x₆}; k = 1.

3. Условие выполняется → 5.

5. k = 0; S₀ = Ø; Q₀^- = {x₁, x₂, x₃, x₄, x₅}; Q₀⁺ = {x₆, x₇} → 2.

2. x₆; S₁ = {x₆}; Q₁^- = {x₁, x₃, x₅}; Q₁⁺ = Ø; k = 1.

3. Условие выполняется → 5.

5. k = 0; S₀ = Ø; Q₀^- = {x₁, x₂, x₃, x₄, x₅, x₆}; Q₀⁺ = {x₇} → 2.

2. x₇; S₁ = {x₇}; Q₁^- = {x₁, x₂, x₄}; Q₁⁺ = Ø; k = 1.

3. Условие выполняется → 5.

5. k = 0; S₀ = Ø; Q₀^- = {x₁, x₂, x₃, x₄, x₅, x₆, x₇}; Q₀⁺ = Ø → останов.

Таким образом, данный граф имеет семь максимальных независимых множеств:

S₁ = {x₁, x₄, x₇}; S₂ = {x₁, x₅, x₆}; S₃ = {x₂, x₃}; S₄ = {x₂, x₅}; S₅ = {x₂, x₇}; S₆ = {x₃, x₄}; S₇ = {x₃, x₆}.

Ядро  множество, которое является одновременно минимальным доминирующим и максимальным независимым.

Утверждение 4.9.1. Конечный граф без петель, не содержащий контуров нечетной длины, обладает ядром.

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

Кликовое число – максимальное число вершин в кликах данного графа.

Утверждение. 4.9.2. Максимальное независимое множество графа G соответствует клике графа G и наоборот.