Повторение
Напомним, что такое цепь и цикл в графе.
Цепь – это простой путь, то есть путь, в котором вершины не повторяются.
Раз не повторяются вершины, то и ребра тоже не повторяются.
Цикл в графе — это замкнутый путь, у которого начало и конец — в одной вершине, а рёбра и промежуточные вершины не повторяются.
Дерево – это связный граф без циклов.
Цепь тоже является деревом, поскольку в цепи нет циклов. И даже граф, состоящий из одной-единственной вершины без рёбер, также можно рассматривать как простейшее дерево.
Диаметр дерева — количество рёбер в максимальной цепи, т. е. длина цепи, связывающей две наиболее удалённые вершины.
В дереве, изображённом на рисунке 2, наиболее удалёнными являются вершины L и D. А количество рёбер между ними равно 5. Значит, диаметр дерева на рисунке 2 равен 5.
Пример 1
На рисунке показана схема водоснабжения в небольшом посёлке. Трубы идут от водонапорной башни и ветвятся, пролегая вдоль улиц. Из больших труб отходят малые к домам. Граф водопровода – дерево. Здесь можно выделить начальную вершину – водонапорную башню.
Пример 2
Возьмем симметричную монету и подбросим ее 3 раза.
Чтобы изобразить этот случайный опыт, построим дерево.
От начальной вершины S нарисуем ветви вниз к вершинам, которые обозначим О (орел) и Р (решка) – это результаты первого броска.
От каждой из них идут еще два ребра вниз к вершинам О и Р, изображающим результаты второго броска.
Точно так же покажем результаты третьего броска.
Получилось дерево случайного эксперимента. В этом дереве восемь цепей, ведущих из начальной вершины S в концевые вершины:
SOOO, SOOP, SOPO, SOPP, SPOO, SPOP, SPPO, SPPP.
Каждая цепь изображает одно из восьми возможных элементарных событий в этом случайном опыте.
В примерах 1 и 2 понятно, какую вершину следует выбрать в качестве начальной, или корневой, вершины, из которой «растет» дерево. Вода по трубам течет из водопроводной башни. Это и есть начальная вершина на схеме водоснабжения.
Во втором примере начальная вершина изображает начальный момент, когда монету еще не бросили ни разу. Мы ее обозначили буквой S от слова start, имея ввиду начало случайного опыта.
Название «дерево» происходит оттого, что цепи «ветвятся», не образуя циклов. Единственная разница – в природе деревья обычно растут снизу вверх, а математические деревья мы рисуем так, как нам удобно.
Бывают бесконечные деревья, то есть деревья, в которых бесконечно много вершин и рёбер.
Пример 3
Предположим, что кто-то пытается послать СМС из леса, где связь очень плохая. Каждая отдельная попытка может оказаться неудачной, и в таком случае телефон предпримет следующую. Будем считать, что попыток может быть сколько угодно.
Такой случайный опыт можно изобразить с помощью бесконечного графа. Начинается граф в вершине S, каждая попытка может оказаться неудачной (вершина Н) или удачной (вершина У).
Упражнения
1. Какие из графов на рисунке являются деревьями?
2. План тропинок в парке представляет собой дерево. Ворота в парке обозначены вершиной S. Сколько цепей ведет из вершины S:
а) к кафе;
б) к пруду;
в) к саду камней?
Свойства деревьев
Поскольку дерево – связный граф, из любой его вершины можно пройти по рёбрам в любую другую вершину. Из-за отсутствия циклов это можно сделать единственным способом. Значит, верна следующая теорема.
Теорема: Любые две вершины в дереве соединены единственной цепью.
Свойство 1. Если из дерева удалить ребро, то граф перестанет быть связным.
Концевой (висячей) вершиной называется вершина, из которой выходит ровно одно ребро, то есть вершина степени 1.
В примере с водопроводом концевыми вершинами являются дома, к которым подведён водопровод, а в примере с монетой концевыми являются вершины - это результаты последнего броска монеты.
Кажется, что раз в дереве нет циклов, то у дерева обязательно должны быть концевые вершины.
Но есть два исключения.
1.Концевых вершин нет у деревьев без ребер.
2.Бывают бесконечные деревья.
Свойство 2. Если в дереве конечное число вершин и есть хотя бы одно ребро, то в таком дереве есть концевая вершина.
Свойство 3. В конечном дереве число ребер на 1 меньше числа вершин.
Домашнее задание
1. Сколько концевых вершин в деревьях?
2. Сколько концевых вершин в деревьях?
3. На рисунке изображён граф.
А. Является ли граф, изображённый на рисунке, деревом?
Б. Сколько рёбер у данного графа?
В. Сколько вершин у графа, изображённого на рисунке?
Г. Сколько концевых вершин у графа, изображённого на рисунке?
4. Количество вершин дерева равно 54. Какой наибольший диаметр может иметь это дерево?