Решение задачи: Максимальное количество ребер в графе с 45 вершинами

Дано: Граф без петель и кратных ребер. Количество вершин: \( n = 45 \). Условие: вершины одинаковой степени не соединены ребром. Найти: наибольшее количество ребер \( E \). Решение: 1. Пусть \( d_i \) — степень \( i \)-й вершины. В графе с 45 вершинами возможные значения степеней лежат в диапазоне от 0 до 44. Однако, если в графе есть вершина степени 0, то не может быть вершины степени 44 (так как она должна быть соединена со всеми остальными). Таким образом, в графе может быть максимум 44 различных значения степеней. 2. Разобьем вершины на группы по их степеням. Пусть \( V_k \) — множество вершин, имеющих степень \( k \). По условию задачи, вершины из одного множества \( V_k \) не могут быть соединены между собой. Это означает, что каждое множество \( V_k \) является независимым. 3. Чтобы максимизировать количество ребер, нам нужно, чтобы вершины имели как можно большие степени. Рассмотрим случай, когда в каждой группе \( V_k \) ровно по одной вершине. Тогда у нас будет 45 различных степеней. Но мы знаем, что различных степеней может быть не более 44 (от 0 до 43 или от 1 до 44). Значит, как минимум две вершины должны иметь одинаковую степень. 4. Пусть \( k \) — значение степени, которое повторяется у двух вершин. Чтобы общее количество ребер было максимальным, выгодно использовать максимально возможные степени: 44, 43, 42 и так далее. 5. Рассмотрим структуру графа. Условие "вершины одинаковой степени не соединены" накладывает ограничение: если в группе \( V_k \) находится \( m_k \) вершин, то они могут быть соединены только с вершинами других степеней. Сумма всех степеней равна \( 2E \): \[ 2E = \sum_{i=1}^{45} d_i \] 6. Для достижения максимума предположим, что степени вершин — это числа от 1 до 44, и одна степень повторяется. Пусть набор степеней будет: \( 1, 2, 3, \dots, 44, x \). Заметим, что если вершина имеет степень \( k \), она не может быть соединена с другими \( m_k - 1 \) вершинами той же степени. Значит, \( k \le 45 - m_k \). Если \( m_k = 2 \) (одна степень повторяется дважды), то \( k \le 45 - 2 = 43 \). То есть повторяющаяся степень не может быть 44. 7. Максимальная сумма степеней достигается, если мы возьмем степени \( 1, 2, 3, \dots, 43, 44 \) и добавим еще одну вершину со степенью 22 (середина ряда для баланса). Однако, есть более точный предел. В графе, где вершины одной степени не смежны, количество ребер не может превышать количества ребер в полном многодольном графе. 8. Оптимальная конфигурация для такой задачи достигается, когда степени распределены максимально плотно. Сумма степеней будет максимальной при наборе: \( 1, 2, \dots, 22, 22, 23, \dots, 44 \). Вычислим сумму \( S \): \[ S = \left( \sum_{i=1}^{44} i \right) + 22 \] Используем формулу суммы арифметической прогрессии: \[ \sum_{i=1}^{44} i = \frac{1 + 44}{2} \cdot 44 = 45 \cdot 22 = 990 \] \[ S = 990 + 22 = 1012 \] 9. Количество ребер \( E \): \[ E = \frac{S}{2} = \frac{1012}{2} = 506 \] Проверка условия: при таком распределении степеней граф существует (это следует из теоремы Эрдёша-Галлаи или построения через полные многодольные графы). Ответ: 506.