Алгоритм выделения пустых подграфов

1. Сопоставляем корню строящегося дерева заданный граф G .

2. Фиксируем в графе вершину с минимальной степенью и сопоставляем ее концу дуги, исходящей из корня. Строим все дуги, исходящие из корня, число которых равно и конец каждой из них сопоставляем вершине окрестности .

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

4. Считаем построенного яруса корнем нового дерева.

5. Устанавливаем, взвешена ли вершина символом Ø . Если “нет”, то переходим к п. 2, если “да”, то – к п. 6.

6. Каждая ветвь построенного дерева однозначно определяет пустой подграф заданного графа G .

Закон поглощения. Если в k – ом ярусе дерева вершины v_i и v_j не смежны, поддерево с корнем v_i построено и если в поддереве с корнем v_j появляется вершина v_i , то соответствующая ветвь не строится.

Закон поглощения используется для того, чтобы в дереве не было одинаковых ветвей. Ветви дерева строятся слева направо. Если при построении некоторой ветви получается ветвь, которая слева уже была построена, то эта ветвь не строится .

Пример. Определить все пустые подграфы и число внутренней устойчивости графа G , изображенного на рис. 5.8.

□ Используя алгоритм выделения пустых подграфов, построим дерево:

Каждая ветвь дерева соответствует пустому подграфу графа G. При построении дерева два раза использовался закон поглощения. Заданный граф имеет восемь пустых подграфов: Е₁ = {4, 8, 3}, E₂ = {4, 8, 6}, E₃ = {4, 2, 6}, E₄ = {4, 7}, E₅ = {1, 5, 7}, E₆ = {1, 5, 8}, E₇ = {1, 6, 8}, E₈ = {5, 2}.

Число внутренней устойчивости равно:

. ■

Замечание. Аналогично можно определить и вычислить реберное число независимости графа G.