Деревья

Повторим

Цепь – это простой путь, то есть путь, в котором вершины не повторяются.

Раз не повторяются вершины, то и ребра тоже не повторяются.

Цикл в графе – это замкнутый путь, в котором не повторяются ребра и не повторяются промежуточные вершины.

Дерево – связный граф без циклов

Цепь тоже является деревом, поскольку в цепи нет циклов. И даже граф, состоящий из одной - единственной вершины без рёбер, также можно рассматривать как простейшее дерево

​

Пример 1

На рисунке показана схема водоснабжения в небольшом посёлке. Трубы идут от водонапорной башни и ветвятся, пролегая вдоль улиц. Из больших труб отходят малые к домам. Водопровод – это граф.

Такой граф называется де́рев͞ом.

Дерево вероятностей

Если в задаче описывается последовательность случайных опытов, и следующий опыт зависит от исхода предыдущего, для разделения возможных сценариев развития событий часто используют схему "дерево вероятностей"

Дерево вероятностей — это связный граф без

циклов.

Пример 2

Возьмем симметричную монету и подбросим ее 3 раза.

Чтобы изобразить этот случайный опыт, построим дерево.

От начальной вершины S нарисуем ветви вниз к вершинам, которые обозначим О (орел) и Р (решка) – это результаты первого броска.

От каждой из них идут еще два ребра вниз к вершинам О и Р, изображающим результаты второго броска.

Точно так же покажем результаты третьего броска.

Пример 2

Получилось дерево случайного эксперимента. В этом дереве восемь цепей, ведущих из начальной вершины S в концевые вершины:

SOOO, SOOP, SOPO, SOPP,

SPOO, SPOP, SPPO, SPPP.

Каждая цепь изображает одно из восьми возможных элементарных событий в этом случайном опыте

В примерах 1 и 2 понятно, какую вершину следует выбрать в качестве начальной, или корневой, вершины, из которой «растет» дерево. Вода по трубам течет из водопроводной башни. Это и есть начальная вершина на схеме водоснабжения.

Во втором примере начальная вершина изображает начальный момент, когда монету еще не бросили ни разу. Мы ее обозначили буквой S от слова start, имея ввиду начало случайного опыта.

Название «дерево» происходит оттого, что цепи «ветвятся», не образуя циклов. Единственная разница – в природе деревья обычно растут снизу вверх, а математические деревья мы рисуем так, как нам удобно.

Бывают бесконечные деревья, то есть деревья, в которых бесконечно много вершин и рёбер.

Пример 3

Предположим, что кто-то пытается послать СМС из леса, где связь очень плохая. Каждая отдельная попытка может оказаться неудачной, и в таком случае телефон предпримет следующую. Будем считать, что попыток может быть сколько угодно.

Такой случайный опыт можно изобразить с помощью бесконечного графа. Начинается граф в вершине S, каждая попытка может оказаться неудачной (вершина Н) или удачной (вершина У).

Закрепление:

1. Какие из графов на рисунке являются деревьями?

Закрепление:

2. План тропинок в парке представляет собой дерево. Ворота в парке обозначены вершиной S. Сколько цепей ведет из вершины S:

а) к кафе;

б) к пруду;

в) к саду камней?