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

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