Формула для дерева
Формула для дерева связывает число его вершин и рёбер: в любом дереве рёбер ровно на одно меньше, чем вершин. Если в дереве \(n\) вершин, то рёбер \(n-1\).
Формула
Здесь \(n\) — число вершин, а \(m\) — число рёбер. Поэтому по числу вершин можно сразу найти число рёбер: \(m=n-1\). Если известно число рёбер, число вершин равно \(n=m+1\).
Дерево связно, поэтому между его вершинами существуют пути. При построении дерева каждое новое добавленное ребро соединяет новую вершину с уже построенной частью графа. Чтобы присоединить \(n\) вершин, сначала нужна одна вершина без ребра, а для каждой из остальных \(n-1\) вершин — по одному ребру. Дополнительное ребро создало бы цикл в графе, а без какого-либо из этих рёбер граф перестал бы быть связным.
В дереве 12 вершин. По формуле получаем \(m=12-1=11\). Значит, в нём 11 рёбер. Если, наоборот, дано дерево с 20 рёбрами, то его число вершин равно \(20+1=21\).
Формула \(m=n-1\) относится именно к дереву, то есть к связному графу без циклов. Для произвольного графа она обычно неверна: в нём могут быть циклы, несколько компонент связности или лишние рёбра. Например, связный граф с 5 вершинами и 6 рёбрами не является деревом.
Сколько рёбер в дереве с 17 вершинами?
Главное
- В дереве с \(n\) вершинами ровно \(n-1\) рёбер.
- Формула: \(m=n-1\); обратно, \(n=m+1\).
- Равенство работает для связного графа без циклов, то есть для дерева.