Понятие степени вершины было введено выше.
ОПРЕДЕЛЕНИЕ 29.Графовым вектором(иногда говорят о графовом разбиении) неориентированного графа называется вектор (d1, d2,…, dp), компоненты которого равны степеням всех вершин графа.
Примеры. У полного графа все компоненты графового вектора равны (p-1), у вполне несвязного – 0, у цикла – 2.
Естественно, встают два вопроса: как узнать, является ли заданный вектор с целыми неотрицательными компонентами графовым и если это так, как соответствующий граф построить?
Очевидное необходимое условие «число четное и di≤p-1», как мы увидим далее, достаточным не является.
Справедлива следующая
Теорема 22. Вектор D1=(d1, d2,…, dp), где p-1³d1³ d2³…³dp³0 является графовым тогда и только тогда, когда графовым является вектор
.
Вектор D2 получен из D1 следующим образом. Первая компонента удаляется, из d1 компонент, начиная со второй, вычитается по 1, остальные компоненты не меняются,. Например, если D1=(4, 4, 3, 2, 2, 2, 1), то D2=(3, 2, 1, 1, 2, 1). Важно, что размерность вектора D2 на единицу меньше, чем D1.
Доказательство. 1. Пусть вектор D2 графовый и Г2 – соответствующий граф. Пусть граф Г1 получен из Г2 добавлением вершины и дуг, связывающих эту вершину с p первыми вершинами Г2 (в нумерации D2). Очевидно, графовый вектор графа Г1 совпадает с D1.
2. Пусть вектор D1 графовый и Г1 – соответствующий граф. Если первая вершина является смежной с d1 вершинами, следующими по степеням за первой, то, исключая из графа эту вершину вместе с инцидентными дугами, получим граф Г2 с графовым вектором D2.
Пусть это условие нарушается. Это означает, что существуют такие вершины u,v, что вершина a с самой большой степенью смежна с u, несмежна с v и при этом deg(v)>deg(u). Докажем, что граф Г1 можно перестроить таким образом, что графовый вектор не изменится и при этом вершина a будет смежной с v и несмежной с u. Для этого заметим, что существует вершина w, смежная с v и несмежная с u. Добавим в граф Г1 дуги (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. Вектор (d1, d2,…, dp) (p³2, d1³ d2³…³dp) является графовым вектором дерева тогда и только тогда, когда
и при этом dp>0.
Графовый вектор с такими свойствами могут иметь не только деревья!
Доказательство. Графовый вектор дерева обладает указанными свойствами, поскольку у него нет изолированных вершин (степени 0) и число равно удвоенному числу дуг, которое равно p-1 (теорема 17).
Пусть теперь вектор обладает указанными свойствами. Доказательство проведем по индукции. Если p=2, то вектор имеет вид (1,1), т.е. граф состоит из двух смежных вершин и дуги – это дерево. Пусть теперь для некоторого p³2 утверждение справедливо и дан вектор (d1, d2,…, dp+1) с нужными свойствами. Во-первых, dp+1=1. В противном случае dp+1³2, т.е. - противоречие. Во-вторых, d1³2. В противном случае d1=1 и
при p³2. Рассмотрим вектор (d1-1, d2,…, dp). Этот вектор обладает всеми свойствами из условия теоремы, следовательно, является графовым вектором некоторого дерева. Добавим к нему лист, соединив его дугой с вершиной степени d1-1. Полученный граф связный, поскольку связным был исходный граф. Циклов в полученном графе также не возникнет, т.е. этот граф является деревом. Его графовый вектор совпадает с (d1, d2,…, dp+1).