09129da111c247359b341330b172b45c

1.

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

2.

Поскольку дерево – связный граф, из любой его вершины
можно пройти по рёбрам в любую другую вершину. Из-за
отсутствия циклов это можно сделать единственным
способом. Значит, верна следующая теорема.
A
B
Теорема.
Любые две вершины в дереве соединены
C
цепью.
Из этой теоремы следует полезное свойство.
D
Свойство 1.
Если
из
дерева
удалить
перестанет быть связным.
ребро,
то
граф
E
F

3.

Концевой (висячей) вершиной называется вершина, из
которой ровно одно ребро, то есть вершина степени 1.
Назовите
концевые
вершины
изображенного на рисунке.
дерева,
A
B
Ответ: A, B, E, F.
C
Свойство 2.
Если в дереве конечное число вершин и есть
хотя бы одно ребро, то в таком дереве есть
D
концевая вершина.
E
F

4.

Свойство 3.
В конечном дереве число рёбер на 1 меньше числа
вершин.
A
Сколько вершин у дерева, изображенного на
рисунке?
Сколько рёбер у дерева, изображенного на
рисунке?
B
C
Ответ: вершин 6, рёбер 5.
D
E
F

5.

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

6.

Дерево
случайного
эксперимента

7.

рАССМОТРИМ ПРИМЕР
В соревнованиях по шашкам участвует 6 человек: Кирилл,
Денис, Ольга, Сергей, Полина и Андрей. Соревнование
проводится по круговой системе – каждый из участников
играет с каждым из остальных один раз. К настоящему
моменту : Кирилл сыграл с Денисом, Сергеем и Андреем;
Денис, с Кириллом и еще с Сергеем; Ольга – с Сергеем,
Полиной, Андреем; Сергей – с Кириллом, Денисом и
Ольгой; Полина – с Ольгой, а Андрей – с Кириллом и
Ольгой. Сколько игр проведено к настоящему моменту и
сколько еще осталось?

8.

Д
К
О
А
Д
П
С
К
О
Прошло 7 игр.
Осталось 8 игр.
А
П
С

9.

Чичиков, погостив у Манилова, посетил по одному разу
Коробочку, Ноздрева, Собакевича, Плюшкина, Тентетникова,
Бетрищева, Петуха, Констанжогло и Кошкарева в указанном
порядке.
Имеется схема расположения
имений и соединяющих их дорог.
Установить, какое имение кому
принадлежит, если ни по одной
дороге Чичиков не проезжал более
одного раза. Начал свое путешествие
Чичиков
из
дома
Манилова,
обозначенного на схеме буквой А.

10.

Ответ: A – Манилов, B - Коробочка, C - Ноздрев, D Собакевич, E - Плюшкин, M - Тентетников, N - Бетрищев,
P - Петух, K - Констанжогло, O – Кошкарев.

11.

Задание
Придумайте способ нарисовать одним
росчерком (не отрывая карандаш от
бумаги
и
не
проводя
одну
линию
дважды):
а) ряд звёздочек
б) эмблему олимпийских игр
в) домики