Давайте обсудим несколько простых свойств деревьев. Начнем с такого утверждения: если в дереве есть больше одной вершины, то есть хотя бы две вершины, то обязательно есть вершина степени один. Такая вершина в дереве называется листом. Давайте это докажем. Что мы знаем про деревья? Если в дереве n вершин, то в нем n минус одно ребро. И давайте еще вспомним соотношение между степенями вершин и числом ребер. Сумма степеней всех вершин в графе — это удвоенное число ребер. Это верно всегда, не только для деревьев, это верно для любых граф. Тогда из этих двух наблюдений получается, что сумма степеней всех вершин в дереве — это 2n минус два. Замечательно! С другой стороны, давайте посмотрим на отдельные вершины: в дереве нет вершин степени ноль; дерево — связный граф; если там больше одной вершины, то из каждой вершины должно выходить хотя бы одно ребро. Предположим от противного, что в дереве нет вершин также степени один, но тогда все вершины степени как минимум два, и тогда сумма степеней всех вершин не меньше 2n. У нас n вершин, у каждой степень минимум два, поэтому сумма степеней вершин будет не меньше 2n. Но с другой стороны, мы только что доказали, что сумма степеней всех вершин в дереве 2n минус два — это противоречие. Получается, что мы пришли к противоречию, значит, предположение наше неверно, значит, в дереве есть хотя бы одна вершина степени один. Хорошо, давайте перейдем к следующему утверждению: из всякого связного графа G можно удалить часть ребер так, что останется дерево. По сути, мы утверждаем, что в каждом связном графе содержится дерево, часть вершин можно удалить, останется дерево. Такое дерево называется остовным деревом графа G, и оно необязательно единственное. Есть пример: мы можем, например, удалить ребра AC и BE и останется дерево (видно, что не осталось циклов), а можем удалить другие ребра, можем удалить ребра BC и DE — также осталось дерево, так что остовное дерево не единственное. Это можно сделать несколькими способами, но нам надо доказать, что это всегда можно сделать хотя бы одним способом. Почему это утверждение верно? Заметим, что каждый связный граф можно обойти поиском в глубину или в ширину и оказывается, что такой обход дает остовное дерево. Давайте подробно это обсудим на примере поиска в глубину. Как мы это делали? Мы начинали с вершины A, запускали ее рассмотрение и запускали рекурсивно рассмотрение для ее соседей: мы находили первого соседа, запускали для него тоже изучение этой вершины, переходили в вершину B. Теперь для B мы тоже запускаем процедуру изучение этой вершины, также перебираем соседей, переходим к следующему соседу — это сосед C. Давайте отмечать ребра, по которым мы переходили между вершинами. Мы их будем выделять цветом. Дальше, вершина C — у нее не осталось нерассмотренных соседей, поэтому для нее процедура рассмотрения сразу заканчивается, и мы возвращаемся в вершину B. Для вершины B остались неразобранные соседи, мы переходим в вершину D и у нас добавляется помеченное ребро. Из вершины D нам тоже придется перейти, есть нерассмотренный сосед — это вершина E, мы добавляем это ребро. Теперь все заканчивается: все вершины уже рассматривались, поэтому для E процедура сразу заканчивается, для D, для B и для A. Но видно, что ребра, по которым мы переходили, образуют дерево. Действительно, мы каждый раз, в каждой вершине перебираем всех соседей, и если вершины уже посещали, то мы туда не переходим. Тем самым мы препятствуем тому, чтобы образовывались циклы, так что мы переходим в ребра, по которым мы проходим. Так что, когда мы смотрим на ребра, по которым мы ходили, то они образуют дерево. Но есть и другое объяснение. Объяснение существования остовного дерева можно сделать несколькими способами, и давайте сделаем следующее. Пускай в графе есть цикл. Что мы можем тогда сделать? Давайте просто удалим любое ребро из этого цикла, например, вот это. Что тогда произойдет? Оказывается, что граф останется связным. Действительно, если до удаления ребра был какой-то путь в графе между какими-то вершинами, то между теми же вершинами по-прежнему есть путь и в новом графе. Если путь старый не использовал ребро, которое мы удалили, тогда ничего не изменилось, просто тот же самый путь будет доводить нас из одной вершины в другую. Если удаленное ребро использовалось, то, просто дойдя по этому пути до одного из концов этого ребра, мы можем дойти до другого конца этого ребра, просто пройдя по циклу, и дальше продолжить наш путь. То есть в любом пути мы можем заменить удаленное ребро просто обходом по циклу, и путь останется. Поэтому если граф был связен до удаления ребра из цикла, то он останется связен и после. Таким образом, мы можем повторять эту процедуру пока в графе есть циклы, то есть пока в графе есть циклы мы можем продолжать удалять ребра. И в конце, что мы получим? Как только это закончится, получится, что у нас по-прежнему связный граф, потому что при каждом удалении G граф оставался связным. И получится, что он без циклов, потому что циклов не осталось, мы не можем продолжить. А это в точности дерево — связный граф без циклов.
