Дано дерево G, в вершинах которого расставили неотрицательные числа с суммой 1, после чего для каждого ребра посчитали произведение чисел в его концах и сложили полученные числа для всех ребер. Найдите максимум рассмотренной суммы.

задан 3 Янв 4:38

10|600 символов нужно символов осталось
1

Будем считать, что дерево имеет по крайней мере две вершины. Рассмотрим вершину v, около которой написано максимальное из чисел. Предположим, что какие-то две вершины соединены ребром, среди которых нет v. Тогда временно убираем это ребро. Дерево распадается на две связные компоненты, одной из которых принадлежит v. Соединим v с концом стёртого ребра, принадлежащего другой компоненте. Снова получается дерево, в котором одно ребро изменилось. Число на одном из концов осталось прежним, а другое не уменьшилось.

В результате серии таких преобразований получится "звёздный" граф, где v соединена с остальными вершинами (степень v всё время растёт, и процесс оканчивается). Число a в вершине v домножается на сумму остальных, равную 1-a. Это даёт a(1-a)<=1/4. Такая оценка достигается, если взять любое ребро, написать 1/2 на его концах, а остальные вершины пометить нулями.

ссылка

отвечен 3 Янв 12:34

10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×1,233
×297
×166

задан
3 Янв 4:38

показан
69 раз

обновлен
3 Янв 12:34

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru