Документ взят из кэша поисковой машины. Адрес оригинального документа : http://www.mccme.ru/mmks/dec08/Rukhovich.pdf Дата изменения: Tue Dec 2 14:32:47 2008 Дата индексирования: Tue Oct 2 11:23:17 2012 Кодировка: koi8-r

Степенные последовательности для графов без петель Рухович А.
брами) с n вершинами степеней d1 ; d2 ; :::; dn 1 сушествует тогда и только тогда, когда выполнены следующие три условия: 1) d1 + d2 + ::: + dn делится на 2; 2) 2di d1 + d2 + ::: + dn для любого i; 3) 2n - 2 d1 + d2 + ::: + dn . Наметим доказательство нео бходимости. Обозначим через e количество ре бер в графе. Нео бходимость условий (1) и (3) известна, поскольку d1 + d2 + ::: + dn = 2e. Условие (2) нео бходимо, поскольку в графе нет петель, а значит степень каждой вершины не больше суммы степеней остальных вершин. Теорема 1. Граф без петель (но, возможно, с кратными ребрами и, возможно, не связный) с n вершинами степеней d1 ; d2 ; :::; dn 0 существует тогда и только тогда, когда выполнены условия (1) и (2) основной теоремы. Доказательство. Нео бходимость доказывается аналогично нео бходимости в основной теореме. Докажем достаточность индукцией по d1 + d2 + ::: + dn . База индукции: утверждение для d1 + d2 + ::: + dn = 0 очевидно. Докажем шаг индукции. Пусть утверждение для d1 +d2 +:::+dn < k. Докажем, что оно верно и для d1 +d2 +:::+dn = k 1. Из k 1 и условия (2) следует, что найдутся хотя бы две вершины ненулевой степени. Можно считать, что d1 d2 ::: dn . Рассмотрим набор d1 - 1; d2 - 1; d3 ; :::; dn . Условия (1) и (2) для него выполнены, поскольку сумма степеней вершин уменьшилась на 2, а степень каждой вершины понизилась не более, чем на 1. Поэтому можно воспользоваться предположением индукции: существует граф для набора d1 - 1; d2 - 1; d3 ; :::; dn . В этом графе соединим ре бром вершины 1 и 2. Поскольку эти вершины различны, то петель не появилось. Следовательно, новый граф не содержит петель. Ясно, что набор степеней его вершин | d1 ; d2 ; d3 ; :::; dn . QED Доказательство достаточности в основной теореме. Рассмотрим граф, полученный по теореме 1. Обозначим через c количество компонент связности этого графа. Докажем, что если c > 1, то можно уменьшить количество компонент связности, не меняя степеней вершин. Ввиду условия (3) e n - 1 > n - c. Поэтому хотя бы в одной компоненте связности есть цикл. Тогда можно взять ре бро a1 a2 этого цикла и ре бро b1 b2 из другой компоненты связности. Удалим эти ре бра, и вместо них до бавим ре бра a1 b1 и a2 b2 . Тогда степени вершин сохранятся, а количество компонент связности уменьшится на 1. Такими операциями можно понизить количество компонент связности до 1. Получится связный граф без петель с заданными степенями вершин.

Основная Теорема. Связный граф без петель (но, возможно, с кратными ре-

1