Алгоритм синтеза графов с максимальной связностью

В зависимости от выбора ведущей вершины ℓ- процедура может строить различные реализации графов, в том числе и с заданными свойствами. Так с помощью ℓ- процедуры можно построить такую реализацию графа, у которой реберная связность l(G) будет максимальной. Основанием для этого служит теорема Д. Уэла: каждая правильная графическая степенная последовательность имеет реализацию, число реберной связности которой l(G)=d_n.

Такая реализация строится ℓ- процедурой, на каждом шаге которой ведущей является вершина с минимальной степенью.

Пример. Задана последовательность:

П₃= 5 4 4 3 2 2.

Построить граф с максимальной реберной связностью

1шаг- ведущая вершина v₆(2) соединяется с v₁ и v₃, последовательность принимает вид: 4 3 4 3 2 0;

2шаг- ведущая вершина v₅(2) соединяется с вершинами v₁,v₃, последовательность принимает вид: 3 3 3 3 0 0;

3^-ий шаг- ведущая вершина v₁(3) соединяется с вершинами v₂, v₃ и v₄, последовательность принимает вид: 0 2 2 0 0;

4^-ый шаг- ведущая вершина v₂(2) соединяется с v₃, v₄, последовательность принимает вид 0 0 1 1 0 0;

5^-ый шаг- соединяются вершины v₃ и v₄, конец.

Рис.3. Граф G₃(П₃).

Полученный граф G₃(П₃) изоморфен графу G₂(П₂). Изоморфность доказывается равенством последовательностей П₂ = П₃(необходимое условие) и наличием гамильтоновых циклов:

С₂ = v₁ v₆ v₃ v₄ v₂ v₅ v₁

C₃ = v₁ v₅ v₃ v₄ v₂ v₆ v₁ , которые совпадают при подстановке v₅→v₆ и наоборот, т.е. при перенумерации вершин v₅ и v₆ любого из графов (достаточное условие).