34. Графическое разбиение.

d1+d2+…+dn=2m (m-число рёбер) d1, …,dn-степени вершин

Сумма степеней вершин графа равна удвоенному числу рёбер.

Представление натурального числа p=d1+…+dn в сумме натуральных чисел называется разбиением этого числа.

Разбиение называется графическим, если полученый набор слагаемых является набором степеней вершин некоторого графа.

П=(d1,…,dn)-графическое разбиение, элементы разбиения -набор степеней вершин графа.

Сумма степеней вершин-всегда чётное число.

Предпологаем, что элементы разбиения расположены в порядке невозростания (d1≥d2≥…≥dn)

Пусть П=d1,….,dn-некоторое разбиение

Модефицированым разбиением разбиения П назыв разбиение П’, которое получается следующим образом: первый элемент d1 из разбиения удаляется, а из последующих d1 элемента вычитается по единице, и если необходимо, то элементы упорядочиваются.

Теорема. Разбиение П является графическим тогда и только тогда, когда графически модефицированное разбиение является П’.

Доказательство.Необходимость. Пусть модефицированное разбиение П’ является графическим, и необходимо показать, что П является графическим изображением тоже. Пусть разбиению П’ соответствует граф G’. Разбиению П тогда соответствует граф G, который строится след образом: добавлябтся новые вершины и добавляются рёбра, которые связывают эту вершину с вершинами d1’, d2’,…,dd1’.

Достаточность. Возможно 2 случая:

1.Вершина с номером 1 смежна в графе G с вершинами, которые имеют 2,3,…,d1+1

2.Данные ситуации не имеют места.

В первом случае граф G’, реализующий разбиение П’ (по графу G строится след образом:удал вершина с номером 1 и все инциндентны ей рёбра)

Во втором случае в графе G найдётся некоторая вершина с номером і, которая смежна вершине с номером1, а в разбиение П этой вершине предшествует вершина с номером k такая, что вершины 1 и kне смежны между собой.

В этом случае существует вершина j, смежная с вершиной k и не смежная с вершиной i. Это следует из того, что элементыразбиения упорядоченные в порядке не возрастания.

Перестроим граф G. Удалим рёбра (1, i),(k,j) и добавим рёбра (j,i),(1,k).

В новом графе сумма степеней вершин, смежных с вершиной 1, больше чем в старом графе G. Новый граф тоже реализуется разбиением П. Через конечное число перестановок придём к случаю 1.