Графовые векторы

Понятие степени вершины было введено выше.

ОПРЕДЕЛЕНИЕ 29. Графовым вектором (иногда говорят о графовом разбиении) неориентированного графа называется вектор (d ₁, d ₂,…, d_p), компоненты которого равны степеням всех вершин графа.

Примеры. У полного графа все компоненты графового вектора равны (p -1), у вполне несвязного – 0, у цикла – 2.

Естественно, встают два вопроса: как узнать, является ли заданный вектор с целыми неотрицательными компонентами графовым и если это так, как соответствующий граф построить?

Очевидное необходимое условие «число четное и d_i ≤ p- 1», как мы увидим далее, достаточным не является.

Справедлива следующая

Теорема 22. Вектор D ₁=(d ₁, d ₂,…, d_p), где p- 1³ d ₁³ d ₂³…³ d_p ³0 является графовым тогда и только тогда, когда графовым является вектор

.

Вектор D ₂ получен из D ₁ следующим образом. Первая компонента удаляется, из d ₁ компонент, начиная со второй, вычитается по 1, остальные компоненты не меняются,. Например, если D ₁=(4, 4, 3, 2, 2, 2, 1), то D ₂=(3, 2, 1, 1, 2, 1). Важно, что размерность вектора D ₂ на единицу меньше, чем D ₁.

Доказательство. 1. Пусть вектор D ₂ графовый и Г₂ – соответствующий граф. Пусть граф Г₁ получен из Г₂ добавлением вершины и дуг, связывающих эту вершину с p первыми вершинами Г₂ (в нумерации D ₂). Очевидно, графовый вектор графа Г₁ совпадает с D ₁.

2. Пусть вектор D ₁ графовый и Г₁ – соответствующий граф. Если первая вершина является смежной с d ₁ вершинами, следующими по степеням за первой, то, исключая из графа эту вершину вместе с инцидентными дугами, получим граф Г₂ с графовым вектором D ₂.

Пусть это условие нарушается. Это означает, что существуют такие вершины u, v, что вершина a с самой большой степенью смежна с u, несмежна с v и при этом deg(v)>deg(u). Докажем, что граф Г₁ можно перестроить таким образом, что графовый вектор не изменится и при этом вершина a будет смежной с v и несмежной с u. Для этого заметим, что существует вершина w, смежная с v и несмежная с u. Добавим в граф Г₁ дуги (a,v), (u,w), исключив дуги (a,u), (v,w). Степени всех вершин при этом преобразовании сохранились. Продолжая подобные преобразования, придем к графу нужного вида. Теорема доказана.

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

1. (4,4,3,2,2,2,1)® (3, 2, 1, 1, 2, 1)=(3, 2, 2, 1, 1, 1) ®(1, 1, 0, 1, 1)= (1, 1, 1, 1, 0)®(0, 1, 1, 0)= (1, 1, 0, 0) ®(0, 0, 0) – исходный вектор графовый. Равенства означают, что компоненты вектора сохраняются, но располагаются по убыванию, т.е. это не есть равенство векторов в обычном понимании – используется только символ. Построение графа можно реализовать на основе первой части доказательства теоремы: начиная с последнего вектора, добавлять последовательно вершины с нужными степенями. Следует иметь в виду, что граф по вектору в общем случае восстанавливается не однозначно!

2. (4,4,4,4,1,1)®(3,3,3,0,1)=(3,3,3,1,0)®(2,2,0,0). Дальнейшее преобразование невозможно, следовательно, исходный вектор не графовый.

Для деревьев графовый вектор устроен следующим образом.

Теорема 23. Вектор (d ₁, d ₂,…, d_p) (p ³2, d ₁³ d ₂³…³ d_p) является графовым вектором дерева тогда и только тогда, когда
и при этом d_p >0.

Графовый вектор с такими свойствами могут иметь не только деревья!

Доказательство. Графовый вектор дерева обладает указанными свойствами, поскольку у него нет изолированных вершин (степени 0) и число равно удвоенному числу дуг, которое равно p -1 (теорема 17).

Пусть теперь вектор обладает указанными свойствами. Доказательство проведем по индукции. Если p =2, то вектор имеет вид (1,1), т.е. граф состоит из двух смежных вершин и дуги – это дерево. Пусть теперь для некоторого p ³2 утверждение справедливо и дан вектор (d ₁, d ₂,…, d_{p+ 1}) с нужными свойствами. Во-первых, d_{p+ 1}=1. В противном случае d_{p+ 1}³2, т.е. - противоречие. Во-вторых, d ₁³2. В противном случае d ₁=1 и

при p ³2. Рассмотрим вектор (d ₁-1, d ₂,…, d_p). Этот вектор обладает всеми свойствами из условия теоремы, следовательно, является графовым вектором некоторого дерева. Добавим к нему лист, соединив его дугой с вершиной степени d ₁-1. Полученный граф связный, поскольку связным был исходный граф. Циклов в полученном графе также не возникнет, т.е. этот граф является деревом. Его графовый вектор совпадает с (d ₁, d ₂,…, d_{p+ 1}).