Дано: дерево D с диаметром d, где d = 4k или d = 4k + 1, k = 1, 2, 3, ...
Найти: показать, что можно заменить одно ребро дерева D другим, чтобы получить дерево D' с диаметром 2k + 1.
Решение:
1. Определим длину диаметра дерева D как максимальное расстояние между любыми двумя его вершинами.
2. Предположим, что d = 4k. В этом случае найдём две конечные вершины A и B, которые определяют диаметр. Дерево имеет путь длины 4k между A и B.
3. Внутри этого пути можно выбрать две вершины C и D, находящиеся на расстоянии 2k от A и 2k от B соответственно.
4. Теперь заменим ребро, соединяющее C и D, на новое ребро, соединяющее A и B. После замены получается новое дерево D', в котором диаметр будет уменьшен.
5. Рассмотрим новый путь от A до B через C и D. Так как C и D соединены, расстояние между A и B станет 2k + 1.
6. Аналогично, если d = 4k + 1, можно провести тот же аргумент. Найдём C и D на расстоянии 2k от A и B и заменим соответствующее ребро.
7. В обоих случаях, после замены ребра, новое дерево D' будет иметь диаметр 2k + 1.
Ответ: можно получить дерево диаметром 2k + 1, заменив одно ребро дерева D.