Математический факультетИнформация для студентовЭлектронная библиотека
Карта сайтаКарта сайта
Недавние измененияНедавние изменения
ПоискПоиск
  
Вы посетилиВы посетили
История страницыИстория страницы
  
Вход/выходВход


Содержание

146

Конкурсная задача ММ146 (4 балла)

При каких D существуют графы диаметра D, у которых сумма квадратов степеней вершин равна D2?

Решение

Сумма степеней вершин, а следовательно и сумма квадратов степеней вершин, любого графа - четна. Поэтому для нечетных D решений нет. При D = 2 наименьшее значение суммы квадратов степеней вершин достигается у двухзвенной цепочки и равно 6. Поэтому D = 2 тоже не годится. Не подходит и D = 4. У цепи длины 4 сумма квадратов степеней вершин - 14. Но добавление любой вершины (любых вершин) без изменения диаметра увеличивает минимум на 1+(32-22)=6. Покажем, что для всех четных D ≥ 6 нужные графы имеются. Возьмем цепь длины D и будем добавлять к вершинам отличным от концевых висячие вершины: к одной - D-6; к одной - 2; к D/2-3 - по одной. Сумма степеней вершин полученного графа составит (D-4)2+42+(D/2-3)·32+D/2·22 + (2+D-6+2+D/2-3)·1 = D2.

Обсуждение

Существует много различных способов построения подходящих графов для четных D ≥ 6. Вариант приведенный в решении предложен Кириллом Веденским и Анатолием Казмерчуком. Еще один универсальный метод предложен Виктором Филимоненковым: к одной из внутренних вершин вершин цепи длины D прицепим 2 висячие вершины, а к другой - D/2-3 трехвзенных цикла. Другие подходы (в том числе и авторский) либо содержат исключения для малых значений D, либо варьируются, например, в зависимости от D mod 4.

Уже не в первый раз (хотя я и не смог найти в архиве, когда был первый раз) некоторые марафонцы загадочным образом ухитряются найти диаметр графа, не являющегося связным. Насколько я в курсе (а я, полагаю, в курсе), диаметр (как и расстояние, через которое он вводится) определяется только для связного графа.

Награды

За правильное решение задачи ММ146 Анатолий Казмерчук, Виктор Филимоненков, Алексей Волошин, Сергей Половинкин, Дмитрий Пашуткин, Кирилл Веденский и Андрей Халявин получают по 4 призовых балла. Александр Ларин получает 2 призовых балла.

Эстетическая оценка - 4.6 балла

Разбор задачи ММ146 подготовил Владимир Лецко


 

 


Страница: [[marathon:problem_146]]

marathon/problem_146.txt · Последние изменения: 2012/01/25 08:44 (внешнее изменение)
Powered by DokuWiki  ·  УКЦ ВГПУ 2006