Документ взят из кэша поисковой машины. Адрес оригинального документа : http://www.mccme.ru/circles/oim/materials/list2.ps Дата изменения: Fri Oct 22 16:19:31 2004 Дата индексирования: Sat Dec 22 15:10:47 2007 Кодировка: koi8-r Поисковые слова: hydrogen

Всюду далее под графом понимается неориентированный граф без петель и кратных ребер.
Графические последовательности
Степенью вершины называется количество выходящих из вершины ребер. Последовательность
степеней вершин содержит степени всех вершин графа в порядке невозрастания. Мы используем
экспоненциальную запись невозрастающих целочисленных последовательностей: a k означает, что k
последовательных членов последовательности равны a.
Основной вопрос для всей серии задач, которая приводится ниже, состоитв том, чтобы опреде-
лить, какие последовательности являются графическими, то есть представляют последовательность
степеней вершн некоторого графа.
1. (Старинная олимпиадная задача) Графична ли последовательность (15 77 )?
2. Графичны ли последовательности а) (4 3 ; 1 6 ), б) (6 4 ; 2 3 ) в) (5 3 ; 3 3 ), г) (18 10 ; 12 3 ; 6 8 ), д) (15 8 ; 10 6 ; 3 4 )?
3. Докажите, что при любых 0 6 k 6 n таких, что kn | четное, существует граф на n вершинах,
степени которого равны k.
4. Назовем обменом следующее преобразование графа. Пусть a; b; c; d | вершины графа, причем (ab),
(cd) | рёбра, а (ac); (bd) | не рёбра. Обмен состоит в выбрасывании рёбер (ab); (cd) и добавлении
рёбер (ac); (bd).
Пусть G 1 , G 2 | два графа с одинаковыми последовательностями степеней d 1 > d 2 >


> dn .
Докажите, что обменами можно перевести граф G 1 в граф G 2 .
4 1
2 . Докажите, что для любой вершины v найдется такая последовательность обменов, после кото-
рой вершина v будет соединена с вершианми максимально возможной степени.
Всюду далее под графом понимается неориентированный граф без петель и кратных ребер.
Графические последовательности
Степенью вершины называется количество выходящих из вершины ребер. Последовательность
степеней вершин содержит степени всех вершин графа в порядке невозрастания. Мы используем
экспоненциальную запись невозрастающих целочисленных последовательностей: a k означает, что k
последовательных членов последовательности равны a.
Основной вопрос для всей серии задач, которая приводится ниже, состоитв том, чтобы опреде-
лить, какие последовательности являются графическими, то есть представляют последовательность
степеней вершн некоторого графа.
1. (Старинная олимпиадная задача) Графична ли последовательность (15 77 )?
2. Графичны ли последовательности а) (4 3 ; 1 6 ), б) (6 4 ; 2 3 ) в) (5 3 ; 3 3 ), г) (18 10 ; 12 3 ; 6 8 ), д) (15 8 ; 10 6 ; 3 4 )?
3. Докажите, что при любых 0 6 k 6 n таких, что kn | четное, существует граф на n вершинах,
степени которого равны k.
4. Назовем обменом следующее преобразование графа. Пусть a; b; c; d | вершины графа, причем (ab),
(cd) | рёбра, а (ac); (bd) | не рёбра. Обмен состоит в выбрасывании рёбер (ab); (cd) и добавлении
рёбер (ac); (bd).
Пусть G 1 , G 2 | два графа с одинаковыми последовательностями степеней d 1 > d 2 >


> dn .
Докажите, что обменами можно перевести граф G 1 в граф G 2 .
4 1
2
. Докажите, что для любой вершины v найдется такая последовательность обменов, после кото-
рой вершина v будет соединена с вершианми максимально возможной степени.

Невозрастающую последовательность из n неотрицательных целых чисел будем называть правиль-
ной, если первый ее член не превосходит n 1, а сумма всех членов четна.
5. Дерево | связный граф без циклов. В дереве на n вершинах ровно n 1 ребро. Докажите, что
если сумма членов правильной последовательности (d 1 ; : : : ; dn ) равна 2(n 1) и dn > 0, то существует
дерево, для которого данная последовательность является последовательностью степеней вершин.
6. Приведите пример правильной неграфической последовательности из n чисел, для всех членов ко-
торой выполняются неравенства n=2004 > d i > 2004.
7. Докажите, что правильная последовательность n положительных чисел, в которой d i 6
p
n=2, |
графическая.
8. Докажите, что правильная последовательность является графической тогда и только тогда, когда
выполняются следующие условия:
k
X
i=1
d i 6 k(k 1) +
n
X
i=k+1
min(k; d i ) для любого 1 6 k 6 n 1:
9.* Можно ли опустить какие-нибудь неравенства из условия предыдущей задачи так, чтобы ее утвер-
ждение осталось верным? Если да, попробуйте найти минимально возможный набор неравенств.
10.* Если слить две графические последовательности, то обязательно получится графическая последова-
тельность. А какие графические последовательности обладают тем свойством, что их нельзя разбить
на две графические последовательности?
Невозрастающую последовательность из n неотрицательных целых чисел будем называть правиль-
ной, если первый ее член не превосходит n 1, а сумма всех членов четна.
5. Дерево | связный граф без циклов. В дереве на n вершинах ровно n 1 ребро. Докажите, что
если сумма членов правильной последовательности (d 1 ; : : : ; dn ) равна 2(n 1) и dn > 0, то существует
дерево, для которого данная последовательность является последовательностью степеней вершин.
6. Приведите пример правильной неграфической последовательности из n чисел, для всех членов ко-
торой выполняются неравенства n=2004 > d i > 2004.
7. Докажите, что правильная последовательность n положительных чисел, в которой d i 6
p
n=2, |
графическая.
8. Докажите, что правильная последовательность является графической тогда и только тогда, когда
выполняются следующие условия:
k
X
i=1
d i 6 k(k 1) +
n
X
i=k+1
min(k; d i ) для любого 1 6 k 6 n 1:
9.* Можно ли опустить какие-нибудь неравенства из условия предыдущей задачи так, чтобы ее утвер-
ждение осталось верным? Если да, попробуйте найти минимально возможный набор неравенств.
10.* Если слить две графические последовательности, то обязательно получится графическая последова-
тельность. А какие графические последовательности обладают тем свойством, что их нельзя разбить
на две графические последовательности?