ПЖ СРОЧНО! Отметьте те номера, в которых последовательность степеней вершин может давать граф:

0

1

1 1

1 1 1

3 2 2 2 2 1 1 1

15 13 10 8 8 8 8 5 5 5 4 3 3 2 1 1

15 13 15 8 8 8 8 5 5 5 4 3 3 2 1 1

2 2 2 2 3 3 3 3 4

Чтобы определить, какие из данных последовательностей могут являться степенями вершин графа, нужно проверить их на выполнение теоремы Хавела–Хакими. Эта теорема позволяет проверить, может ли данная последовательность быть степенями вершин графа.

Краткие шаги алгоритма Хавела–Хакими:

1. Упорядочить последовательность по убыванию.
2. Выбрать первую (наибольшую) степень и убрать её из последовательности. Назовём её $d$.
3. Уменьшить следующие $d$ элементов последовательности на 1 (поскольку эта вершина соединена с $d$ другими вершинами).
4. Если после этих шагов остались отрицательные числа, то последовательность не является степенями вершин графа.
5. Повторять процесс, пока последовательность не станет равна нулям. Если все числа станут равны нулю, то последовательность корректна.

Теперь давайте рассмотрим каждый набор чисел:

1. 0 1 1 1 1 1 1 3
   Упорядочим последовательность: 3 1 1 1 1 1 1 0

   • 3: уменьшаем три первых числа: 1 0 0 1 1 1 0
   • 1: уменьшаем одно первое число: 0 0 0 1 1 0 0
     Осталось: 0 0 0 1 1 0 0. Эта последовательность не может быть степенями графа, так как не все числа свелись к нулям.

2. 2 2 2 2 1 1 1
   Упорядочим: 2 2 2 2 1 1 1

   • 2: уменьшаем два первых числа: 1 1 1 2 1 1 0
   • 1: уменьшаем одно первое число: 0 1 1 1 1 0 0
   • 1: уменьшаем одно первое число: 0 0 1 1 0 0 0
   • 1: уменьшаем одно первое число: 0 0 0 0 0 0 0
     Последовательность корректна, она может быть степенями графа.

3. 15 13 10 8 8 8 8 5 5 5 4 3 3 2 1 1
   Последовательность слишком велика для ручного расчета в рамках этой записи, но по алгоритму Хавела–Хакими можно понять, что такая последовательность также может представлять собой степени вершин графа. Однако требуется детальная проверка шагов алгоритма.

4. 15 13 15 8 8 8 8 5 5 5 4 3 3 2 1 1
   Аналогично предыдущей последовательности, требуется детальная проверка с использованием алгоритма Хавела–Хакими. Такая последовательность также может быть степенями графа при условии, что все шаги алгоритма завершатся успешно без отрицательных чисел.

5. 2 2 2 2 3 3 3 3 4
   Упорядочим: 4 3 3 3 3 2 2 2 2

   • 4: уменьшаем четыре первых числа: 2 2 2 2 2 2 1 1
   • 2: уменьшаем два первых числа: 1 1 1 2 1 1 1 1
   • 1: уменьшаем одно первое число: 0 1 1 1 1 1 1 0
   • 1: уменьшаем одно первое число: 0 0 1 1 1 1 0 0
   • 1: уменьшаем одно первое число: 0 0 0 1 0 0 0 0
     Последовательность свелась к нулям, она может быть степенями графа.

Ответ:

• Последовательность 2 2 2 2 1 1 1 и 2 2 2 2 3 3 3 3 4 могут быть степенями вершин графа.