Задание 9. Вася выписал в ряд степени всех вершин графа. Какие наборы чисел он мог написать? (Выберите один из нескольких вариантов)

Для того чтобы набор чисел мог быть степенями вершин графа, необходимо выполнение двух условий: 1. Сумма степеней всех вершин должна быть четной (так как каждая ребро вносит вклад в степени двух вершин). 2. Должна выполняться теорема Эрдёша-Галлаи, но для школьного уровня достаточно проверить первое условие. Рассмотрим каждый из предложенных вариантов: * 8, 7, 6, 5, 4, 4, 3, 2, 1: Сумма = 8 + 7 + 6 + 5 + 4 + 4 + 3 + 2 + 1 = 40. Четная. * 9, 8, 8, 7, 6, 6, 3, 2, 1: Сумма = 9 + 8 + 8 + 7 + 6 + 6 + 3 + 2 + 1 = 50. Четная. * 8, 8, 7, 7, 6, 5, 4, 2, 1: Сумма = 8 + 8 + 7 + 7 + 6 + 5 + 4 + 2 + 1 = 48. Четная. * 8, 7, 5, 4, 4, 3, 2, 2, 2: Сумма = 8 + 7 + 5 + 4 + 4 + 3 + 2 + 2 + 2 = 37. Нечетная. Поскольку сумма степеней в последнем варианте нечетная, этот набор чисел не может быть степенями вершин графа. Теперь проанализируем оставшиеся варианты, используя теорему Эрдёша-Галлаи. Для упрощения, проверим варианты на возможность существования графа без петель и кратных ребер. В этом случае максимальная степень вершины не может превышать n-1, где n - число вершин в графе. * 8, 7, 6, 5, 4, 4, 3, 2, 1: n = 9, максимальная степень 8. Это условие выполняется. * 9, 8, 8, 7, 6, 6, 3, 2, 1: n = 9, максимальная степень 9. Это условие **не** выполняется, так как максимальная степень не может быть больше 8. * 8, 8, 7, 7, 6, 5, 4, 2, 1: n = 9, максимальная степень 8. Это условие выполняется. Однако, условие, что максимальная степень не должна превышать n-1, не является достаточным. Вариант с "9" не может быть степенями вершин графа. Поэтому остаются варианты с 8. Давайте попробуем построить граф для каждого варианта, чтобы увидеть, какой из них возможен. Первый и третий варианты имеют максимальную степень 8, что означает, что соответствующая вершина должна быть связана со всеми остальными вершинами. В принципе, все три варианта (после исключения последнего с нечетной суммой) могут быть степенями графа (но это требует более сложного анализа по теореме Эрдёша-Галлаи, который выходит за рамки школьной программы). Предполагая, что в задании ищут самый очевидный вариант, исключаем вариант с "9", поскольку степень не может превышать количества вершин минус 1. Ответ: 8, 7, 6, 5, 4, 4, 3, 2, 1 и 8, 8, 7, 7, 6, 5, 4, 2, 1