Свойства деревьев

Краткое пояснение:

Теорема: Любые две вершины в дереве соединены единственной цепью.

Доказательство от противного:

1. Предположение: Допустим, что между двумя вершинами (например, A и B) в дереве существует более одной цепи.
2. Следствие: Если есть две разные цепи, соединяющие A и B, то, идя по одной цепи от A до B, а затем возвращаясь по другой цепи от B до A, мы образуем цикл.
3. Противоречие: Однако, по определению, дерево не может содержать циклов.
4. Вывод: Наше первоначальное предположение неверно. Следовательно, между любыми двумя вершинами в дереве существует только одна единственная цепь.

Свойство 1: Если из дерева удалить ребро, то граф перестанет быть связным.

Доказательство:

1. Рассмотрим ребро: Пусть удаляемое ребро соединяет вершины X и Y.
2. Предположим обратное: Если после удаления ребра XY граф остался связным, то между вершинами X и Y всё ещё существует путь.
3. Следствие: Этот путь, состоящий из других рёбер, вместе с удалённым ребром XY, образует цикл (X → ... → Y → X).
4. Противоречие: Как мы знаем из теоремы, в дереве циклов быть не может.
5. Вывод: Следовательно, удаление любого ребра из дерева разрушает его связность.