EssayAI
Блог
Блог
Математика и алгоритмы

Дерево: свойства и число рёбер

8 ноября 2026Время чтения: 8 минут
#теория графов#дерево#вершины графа#рёбра графа#связность
Дерево: свойства и число рёбер

В дереве с шестью вершинами ровно пять рёбер. Это верно независимо от того, вытянута ли схема в цепочку или разветвляется в нескольких местах. Правило кажется простым, но его легко применить к неподходящему графу: для вывода важно, что граф связен и в нём нет циклов. Разберём, как устроено дерево, почему работает формула и как пользоваться её обратными признаками. На схеме ниже можно менять число вершин и наблюдать за числом рёбер в одном из возможных деревьев.

Что в теории графов называют деревом

Рассмотрим конечный неориентированный граф: вершины изображают точками, а рёбра соединяют пары вершин. Граф связен, если из каждой вершины можно добраться до любой другой по рёбрам. Цикл - замкнутый путь, который возвращается в исходную вершину и не повторяет остальные вершины. Дерево - это связный граф без циклов. Далее считаем графы простыми: петель и кратных рёбер нет, а число вершин положительно.

Одна вершина без рёбер тоже образует дерево: условие связности выполняется, а цикла нет. На рисунке направление ветвей не имеет значения. Корень выбирать необязательно: если его выделить, появятся понятия родителей и потомков, но число рёбер и свойства исходного неориентированного графа не изменятся. Подробнее о расстояниях от выбранного корня рассказано в статье про высоту и глубину дерева.

К одной вершине последовательно присоединяются новые вершины: каждая приносит ровно одно ребро, а при обратном ходе каждая убирается вместе с ним.

Такое построение сохраняет связность: новая вершина связана со старым графом. Цикла тоже не возникает, ведь у новой вершины только одно ребро. Обратный ход показывает удаление листьев. Это наглядная модель, а доказательство для любого дерева приведём ниже.

Формула числа рёбер

Обозначим число вершин через nn, а число рёбер через mm. Для любого конечного дерева при n≥1n\geq 1 верно:

m=n−1.m=n-1.

Например, если в дереве 6 вершин, то m=6−1=5m=6-1=5. Если рёбер 12, вершин на одно больше: n=12+1=13n=12+1=13. Формула не зависит от того, где находится корень и сколько ветвей выходит из конкретной вершины.

Дерево из шести вершин и пяти рёбер: 5 равно 6 минус 1
Дерево из шести вершин и пяти рёбер: 5 равно 6 минус 1

Не путайте эту формулу с правилом для полного графа: дерево использует ровно столько рёбер, сколько нужно для связности без циклов. Для одной вершины формула даёт ноль; это полезная проверка граничного случая.

Почему рёбер на одно меньше: доказательство

Докажем утверждение индукцией по числу вершин. При n=1n=1 рёбер нет, и равенство m=n−1m=n-1 выполнено. Теперь предположим, что оно верно для деревьев с n−1n-1 вершинами, и возьмём дерево с n>1n>1 вершинами.

В любом таком дереве есть лист - вершина степени один. Чтобы это увидеть, выберем максимально длинный простой путь. Его конец не может иметь соседа вне пути: тогда путь можно было бы продолжить. Другого соседа на самом пути, кроме предыдущей вершины, тоже нет: соответствующее ребро замкнуло бы цикл. Значит, конец пути имеет степень один.

Удалим лист и единственное его ребро. Оставшийся граф связен: путь между двумя оставшимися вершинами не мог проходить через лист внутри пути. Цикл после удаления появиться не может. Получилось дерево с n−1n-1 вершинами; по предположению индукции в нём n−2n-2 рёбер. Возвращая лист и его ребро, получаем (n−2)+1=n−1(n-2)+1=n-1. Доказательство одновременно объясняет обратный ход анимации.

Уникальный путь и другие признаки

Для двух разных вершин дерева существует ровно один простой путь. Связность гарантирует существование пути. Если бы между вершинами были два разных простых пути, их различающиеся участки образовали бы цикл. Поэтому в дереве нет запасного маршрута между концами ребра.

Отсюда следуют два полезных свойства. Удаление любого ребра разбивает дерево на две компоненты связности: иначе между его концами оставался бы другой путь. Такое ребро называют мостом. Если же добавить отсутствующее ребро между двумя существующими вершинами, оно вместе с единственным прежним путём между ними образует ровно один цикл. При одной вершине добавить такое ребро в простом графе невозможно, поэтому второе утверждение применяется, когда подходящая пара существует.

Эквивалентные признаки дерева позволяют выбрать удобную проверку. Для конечного простого графа с n≥1n\geq1 достаточно установить одно из условий:

  • граф связен и имеет n−1n-1 рёбер;
  • граф не содержит циклов и имеет n−1n-1 рёбер;
  • между каждой парой разных вершин существует единственный простой путь.

Например, связный граф с n−1n-1 рёбрами не может содержать цикл: удаление ребра цикла сохранило бы связность, но для связности nn вершин требуется хотя бы n−1n-1 рёбер. Второй признак можно получить из формулы леса ниже. Подробную формулировку и доказательства этих эквивалентностей приводит учебник дискретной математики.

Почему одной формулы недостаточно

Пусть граф состоит из треугольника и одной изолированной вершины. Всего n=4n=4 и m=3m=3, то есть m=n−1m=n-1. Но это не дерево: треугольник содержит цикл, а изолированная вершина не связана с остальными. Число рёбер здесь совпало с нужным случайно: цикл добавил лишнее ребро в одной компоненте, а разрыв связности компенсировал его в другой.

Поэтому проверка выглядит так: сначала посчитайте вершины и рёбра, затем проверьте связность или отсутствие циклов. Для связности можно начать с любой вершины и выполнить обход в ширину: если посещены все вершины, граф связен. При представлении списками смежности обход занимает O(n+m)O(n+m) времени. Наличие цикла также проверяют обходом в глубину, учитывая родительское ребро в неориентированном графе.

Лес и компоненты связности

Лес - граф без циклов, который может быть несвязным. Каждая его компонента связности является деревом, включая отдельную изолированную вершину. Если компонентов kk, а всего вершин nn, то число рёбер леса равно

m=n−k.m=n-k.

Действительно, в компоненте с nin_i вершинами находится ni−1n_i-1 ребро. Складывая по всем компонентам, получаем m=∑i(ni−1)=n−km=\sum_i(n_i-1)=n-k. Например, лес из двух деревьев с четырьмя и тремя вершинами содержит 3+2=53+2=5 рёбер: 7−2=57-2=5. При k=1k=1 формула превращается в правило для дерева. Она же показывает, почему ациклический граф с n−1n-1 рёбрами обязательно связен: тогда k=1k=1.

Как применять свойства в задачах

Допустим, сеть соединяет восемь пунктов семью линиями и известно, что из каждого пункта достижим любой другой. Число линий равно 8−18-1, а связность задана. Следовательно, сеть - дерево, и удаление любой линии нарушит связность. Перечислять все возможные циклы здесь не нужно.

Если в исходной связной сети линий больше, из неё можно выбрать остовное дерево: оно сохраняет все вершины и связность, оставляя ровно n−1n-1 рёбер. Когда у линий есть веса и нужно минимизировать их сумму, используют, например, алгоритм Прима. Не всякая сеть с n−1n-1 линиями сама является остовом: предварительно нужно убедиться, что она связна.

Если условие сообщает только количество вершин и рёбер, полезно сначала построить два мысленных примера. Цепочка показывает, как может выглядеть дерево с нужными числами. Треугольник с отдельной вершиной показывает, что те же числа иногда получаются у несвязного графа. Значит, для строгого ответа следует искать в условии дополнительное слово «связный» или указание на отсутствие циклов. Если его нет, корректный ответ должен объяснять неоднозначность, а не выбирать удобный рисунок. Такой приём особенно полезен, когда задача просит не просто вычислить число, а обосновать устройство всей сети.

Другой тип задачи использует степени вершин. В дереве с nn вершинами сумма степеней равна 2m=2(n−1)2m=2(n-1), поскольку каждое ребро учитывается у обоих концов. Если предложенный набор степеней имеет другую сумму, он не может описывать дерево. Совпадение суммы само по себе также не доказывает, что конкретный граф связен и ацикличен.

Частые ошибки

  • Применять m=n−1m=n-1 к любому графу как достаточный признак. Добавьте проверку связности или отсутствия циклов.
  • Считать, что корень обязателен. Корень нужен для иерархии, а определение дерева от него не зависит.
  • Забывать отдельные вершины. Изолированная вершина учитывается при подсчёте nn и является отдельной компонентой леса.
  • Путать степень и число потомков. В неукоренённом графе степень - число инцидентных рёбер; у некорневой вершины одно из них ведёт к родителю.

FAQ

Сколько листьев обязательно есть в дереве?

Как минимум два, если вершин больше одной: оба конца максимального простого пути являются листьями. У дерева из одной вершины степень ноль, поэтому при определении листа как вершины степени один листьев нет.

Может ли дерево содержать цикл после добавления ребра?

Да. Добавление отсутствующего ребра между двумя его вершинами создаёт ровно один цикл, а получившийся граф уже не дерево. Петли и кратные рёбра в рассматриваемой модели не допускаются.

Сколько рёбер у леса из десяти вершин и трёх компонент?

Семь: по формуле m=n−k=10−3m=n-k=10-3. Здесь важно, что граф действительно является лесом, то есть не содержит циклов.

Коротко

Дерево - связный граф без циклов. При n≥1n\geq1 в нём ровно n−1n-1 рёбер, каждая пара вершин соединена единственным простым путём, а каждое ребро является мостом. Для обратного вывода к равенству m=n−1m=n-1 нужно добавить связность либо отсутствие циклов; для леса с kk компонентами действует формула m=n−km=n-k.

Доверьте текст нейросети EssayAI

Открыть EssayAI

Бесплатно, на русском языке и без VPN

Читайте также

Лемма о рукопожатиях: формула, доказательство и примеры

Лемма о рукопожатиях: формула, доказательство и примеры

Лемма о рукопожатиях связывает сумму степеней вершин и число рёбер графа. Разбираем доказательство, нечётные степени, петли и типовые задачи на примерах.

8 ноября 20267 минут
Алгоритм Флойда-Уоршелла: кратчайшие пути в графе

Алгоритм Флойда-Уоршелла: кратчайшие пути в графе

Алгоритм Флойда-Уоршелла на примере: как получить матрицу кратчайших путей для всех пар вершин, восстановить маршрут и вовремя обнаружить отрицательный цикл.

8 ноября 20268 минут
Алгоритм Хирхольцера: как найти эйлеров путь

Алгоритм Хирхольцера: как найти эйлеров путь

Алгоритм Хирхольцера строит эйлеров путь или цикл в графе. Разбираем условия существования, работу стека, пример с двумя циклами и сложность алгоритма.

8 ноября 20268 минут
Формула Эйлера для планарных графов

Формула Эйлера для планарных графов

Формула Эйлера для планарных графов: как считать вершины, рёбра и грани, почему учитывается внешняя область и как доказать равенство для связного графа.

8 ноября 20268 минут
Максимальный поток: алгоритм Форда-Фалкерсона

Максимальный поток: алгоритм Форда-Фалкерсона

Максимальный поток алгоритмом Форда-Фалкерсона: разбираем остаточную сеть, обратные рёбра и дополняющие пути на примере, а результат проверяем разрезом.

8 ноября 20269 минут
Список смежности: представление графа с примерами

Список смежности: представление графа с примерами

Как построить список смежности графа по рёбрам и восстановить граф по спискам. Разбираем ориентированные и взвешенные графы, сложность операций и отличие от матрицы.

8 ноября 20268 минут