4. 1.5. Плотность p(g) графа g.

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

Плотностью p(G) графа G=<V, Г> называется максимальная мощность носителя полного подграфа F графа G.

Значит, для определения плотности p(G) графа G необходимо выделить в графе G все полные подграфы.

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

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

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

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

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

5. Устанавливаем, взвешена ли вершина v_α символом Ø. Если «нет», то переходим к п.2, если «да» - то к п.6.

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

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

Построение дерева для определения полных подграфов графа G аналогично построению дерева для определения пустых подграфов графа G с учетом особенностей алгоритма выделения полных подграфов и соответствующего закона поглощения.

Пример 11. Определить плотность p(G) графа G (рис. 1.1).

Используя алгоритм выделения полных подграфов, построим искомое ориентированное дерево (рис. 1.13).

1

2 6

3 5

4

1

6 6

3 4 4

3 6 6 6

1

^{Ø Ø Ø Ø}

^F₁ ^F₂ ^F₃ ^F₄

Рис. 1.13

Здесь F_i – полные подграфы. Из рисунка видно, что мощность носителей всех подграфов равна трем, значит.

р(G) = |{2, 4, 3}| = |{2, 4, 6}| = |{2, 1, 6}|= |{4, 5, 6}| = 3.

Каждое множество состоит из попарно смежных вершин. ■