Степенная последовательность вершин графа

При синтезе сетей связи с заданными свойствами важное значение имеют показатели степеней вершин. Степенной последовательностью называют список степеней вершин графа. Чаще всего этот список задают в виде упорядоченного (вариационного) ряда по мере убывания или возрастания степеней.

Свойства графов связаны со свойствами степенных последовательностей как минимум на уровне необходимых условий. Так, чтобы графы были изоморфными, необходимым условиям является равенство степенных рядов, чтобы граф был максимально связен, необходимо равенство степеней или максимум однородности степеней и т.д. таким образом, свойства степенных последовательностей во многом определяют свойства графов, и по заданным степенным последовательностям иногда удается синтезировать графы с заданными свойствами.

Прежде всего возникает вопрос- по всякой ли конечной последовательности целых чисел d₁, d₂,…,d_n можно построить граф. Последовательность целых чисел называют графической, если можно построить такой граф, чтобы члены последовательности были степенями вершин.

Чтобы последовательность была графической, она должна быть сжимаемой.

Степенную последовательность называют правильной если выполняются два условия:

n-1≥ d₁≥d₂….≥d_n;

- четное число.

Проверку последовательности на сжимаемость проведем вместе с алгоритмом построения графа на примере.

Пусть задана последовательность чисел, удовлетворяющая условию

k₁≥ k₁≥….≥k_n

П₁=5; 4; 3; 3; 2; 1.

Последовательность сжимается путем выполнения следующих операций:

из k₁ вычитается k₁;

из k₂; k₃; k₃;…; k_k+1; вычитается 1

полагается k₁ = 0;

из оставшихся чисел формируется новая последовательность k₁ ≥ k₂ ≥….≥ k_n;

сжатие производится до тех пор, пока все числа не станут равными нулю, или появятся отрицательные.

k₁; k₂; k₃; k₄ ; k₅; k₆ k₁; k₂; k₃; k₄ k₂; k₃

5; 4; 3; 3; 2; 1 3; 2; 2; 1 1; 1

3; 2; 2; 1; 0 1; 1; 0 0

v₁; v₂; v₃; v₄; v₅; v₆ v₂; v₃; v₄ v₃; v₄

Последовательность сжимаемая, значит графическая, граф состоит из 6 вершин со степенями к_i = d_i.

Первый шаг сжатия последовательности является первым шагом построения графа, т.е. из вершины k₁ проводятся k₁=5ребер в вершины v₂; v₃; v₄; v₅; v₆.(Ребра показаны сплошными линиями).

Второй шаг сжатия последовательности является вторым шагом построения графа. Из вершины v₂ с k₁ =3 проводятся 3 ребра в вершины v₃; v₄; v₅.(Ребра показаны пунктирными линиями).

Третий шаг –из вершины v₃ проводятся ребро в v₄ граф со степенным рядом вершин d:{5;4;3;3;2;1} построен.(ребро V₃V₄ показана штрих-пунктирной).

Рис. 1. Граф G₁ (П₁)

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

П₂ = 5; 4; 4; 3; 2; 2

Первый шаг – ведущая вершина v₁(5) соединяется с вершинами v₂; v₃; v₄; v₅; v₆, степенная последовательность принимает вид: 0 3 3 2 1 1

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

Третий шаг- ведущая вершина v₃ соединяется с вершинами v₄; v₆, конец.

Рис. 2. Граф G₂(П₂)

Для последовательностей П₁, П₂ выполняется одно из необходимых условий изоморфного вхождения графа G₁(П₁) в граф G₂(П₂), а именно П₂≥ П₁, т.е. . В данном случае этого условия достаточно, чтобы граф G₁ вкладывался в граф G₂. Графы будут изоморфны, если удалить ребро v₃v₆, в этом случае совпадут и последовательности П₁ и П₂. Однако в общем случае этого условия не достаточно.

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