|
|
 |
Условие
Дано дерево с n вершинами, n ≥ 2. В его вершинах расставлены числа x1, x2, xn, а на каждом ребре записано произведение чисел, стоящих в концах этого ребра. Обозначим через S сумму чисел на всех рёбрах. Докажите, что
Решение 1
Рассмотрим ребро l, соединяющее вершины с числами xi и xj. Обозначим через ki(l) число вершин, из которых нельзя пройти в вершину xi при удалении ребра l.
Ясно, что 1 ≤ ki(l), kj(l) ≤ n – 1, ki(l) + kj(l) = n. Кроме того, для каждого i сумма равна n – 1 (сумма берётся по всем рёбрам l, выходящим из xi), так как из вершины xi можно пройти по рёбрам дерева в каждую из оставшихся n – 1 вершин единственным несамопересекающимся путем.
Согласно неравенству Коши для данного ребра l получим
Последнее неравенство верно, так как ki(l)kj(l) = ¼ ((ki(l) + kj(l))² – (ki(l) – kj(l))² ≥ ¼ (n² – ((n – 1) – 1)²) = n – 1.
Сложив неравенства (*) по всем рёбрам, получим требуемое неравенство.
Решение 2
Будем проводить операции, не изменяющие чисел в вершинах и не
уменьшающие сумму S чисел на рёбрах. Достаточно доказать неравенство по окончании этих операций.
Вначале заменим числа в вершинах на их модули, то есть далее считаем, что x1, x2, ..., xn ≥ 0.
Выберем наибольшее из чисел xi, пусть это число x1. Если нашлась вершина с числом xi, i ≠ 1, из которой выходит ровно одно ребро l, ведущее в вершину xj, j ≠ 1, то произведём
перестройку: удалим ребро l и соединим ребром вершины с числами
xi и x1. Полученный граф остаётся деревом, так как количество рёбер не изменилось и по-прежнему из каждой вершины можно пройти по рёбрам в любую другую. После перестройки сумма S изменяется на xix1 – xixj ≥ 0. Производим перестройки, пока
это возможно. Поскольку при каждой перестройке число рёбер, выходящих из вершины с числом x1, увеличивается, через конечное число шагов мы придём к ситуации, когда невозможно сделать перестройку. Это означает, что вершина с числом x1 соединена ребром с каждой из оставшихся n – 1 вершин.
Таким образом, для конечной ситуации S = x1x2 + x1x3 + ... + x1xn. При этом неравенство верно, поскольку
