Презентация по теме "Деревья" Вероятность и статистика, 8 класс

Деревья

Вероятность и статистика

8 класс

Повторим

Напомним, что такое цепь и цикл в графе.

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

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

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

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

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

Пример 1

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

Пример 2

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

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

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

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

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

Пример 2

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

SOOO, SOOP, SOPO, SOPP,

SPOO, SPOP, SPPO, SPPP.

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

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

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

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

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

Пример 3

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

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

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

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

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

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

а) к кафе;

б) к пруду;

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

Свойства деревьев

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

Теорема: Любые две вершины в дереве соединены единственной цепью.

Свойства деревьев

Свойство 1. Если из дерева удалить ребро, то граф перестанет быть связным.

Свойства деревьев

Концевой (висячей) вершиной называется вершина, из которой выходит ровно одно ребро, то есть вершина степени 1 .

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

Кажется, что раз в дереве нет циклов, то у дерева обязательно должны быть концевые вершины.

Но есть два исключения.

Свойства деревьев

• Концевых вершин нет у деревьев без ребер.
• Бывают бесконечные деревья.

Свойство 2 . Если в дереве конечное число вершин и есть хотя бы одно ребро, то в таком дереве есть концевая вершина.

Свойство 3. В конечном дереве число ребер на 1 меньше числа вершин.

Задача

Сколько концевых вершин в деревьях?

Домашнее задание:

§§46, 47 на стр. 4-7 (часть 2).

Выполнить письменно № 2, №6, №12