Теория:
О графах мы уже говорили в прошлом учебном году. Вспомним несколько важных понятий.
Графом называется конечное множество точек, некоторые из которых соединены линиями. При этом точки называются вершинами графа, а линии — рёбрами.
Если в графе любые две вершины соединены путём, то такой граф называется связным.
Цикл в графе — это путь, у которого начало и конец — в одной вершине, а рёбра и промежуточные вершины не повторяются.
Изучим ещё один вид графов — деревья.
Дерево — это связный граф без циклов.
Деревья — самые простые графы, которые часто возникают как самостоятельно, так и в других задачах.
Пример:
Рис. \(1\). Пример дерева
На рисунке \(1\) изображён граф, в котором можно из каждой вершины добраться до каждой, но при этом в нём нет циклов.
Из примера видно, что в дереве нельзя, передвигаясь по рёбрам и не проходя по одному ребру два или более раз, вернуться в исходную вершину.
Граф, в котором только одна вершина без рёбер, можно рассматривать как простейшее дерево.
Диаметр дерева — количество рёбер в максимальной цепи, т. е. длина цепи, связывающей две наиболее удалённые вершины.
Пример:
Рис. \(2\). Дерево
В дереве, изображённом на рисунке \(2\), наиболее удалёнными являются вершины \(L\) и \(D\). А количество рёбер между ними равно \(5\). Значит, диаметр дерева на рисунке \(2\) равен \(5\).
В любом дереве (в котором более одной вершины) есть вершина, из которой выходит ровно одно ребро. Такую вершину называют концевой или висячей.
Пример:
в дереве на рисунке \(2\) концевыми будут вершины \(L\), \(K\), \(D\).
Деревья обладают важным свойством.
В дереве количество вершин на \(1\) больше числа рёбер.
Доказательство.
1. Если рёбер в дереве нет и оно состоит из одной вершины.
То количество рёбер согласно свойству на \(1\) меньше числа вершин и равно
\(1-1=0\).
2. Если количество рёбер в графе равно \(x\) ().
В таком дереве есть концевая вершина. Удалим её вместе с входящим в неё ребром. Снова получим дерево.
Продолжим удалять концевые вершины вместе с входящими рёбрами, пока не останется одна вершина.
В итоге мы удалили все \(x\) рёбер и \(x\) концевых вершин. Осталась одна вершина и ни одного ребра. Значит, вершин в исходном графе было на \(1\) больше, чем рёбер.
Что и требовалось доказать.
Об остальных свойствах дерева мы поговорим уже в следующей теме.