Графы. Деревья_

1.

2.

Схема метро
ПРИМЕРЫ ГРАФОВ
Электросхема
Схема молекулы
химического вещества
Карта дорог

3.

Цепь – путь по вершинам и ребрам, включающий любое
ребро графа не более одного раза.
Цикл в графе – это путь, у которого начало и конец – в
одной вершине, а рёбра и промежуточные вершины не
повторяются
Если в связном графе нет циклов, то такой граф называют
деревом.
ДЕРЕВО - ЭТО СВЯЗНЫЙ ГРАФ БЕЗ ЦИКЛОВ
Деревья – самые простые графы, которые возникают
как самостоятельно, так и в других задачах.

4.

Вершины дерева называют
узлами.
Узлы, из которых не
выходят рёбра,
называют листьями
Главный узел –
корень дерева.
Его обычно изображают
наверху.

5.

ПРИМЕР ДЕРЕВА
На рисунке изображён граф, в котором можно из
каждой вершины добраться до каждой, но при этом в нём
нет циклов.
Из примера видно, что в дереве нельзя, передвигаясь
по рёбрам и не проходя по одному ребру два или более
раз, вернуться в исходную точку.

6.

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

7.

8. Свойства деревьев:

Свойство 1
Если в дереве n вершин, то: m=n−1
где:
•n — вершины
•m — рёбра
Объяснение:
«
У дерева всегда рёбер на один меньше, чем вершин.»
Пример:
5 вершин → 4 ребра
10 вершин → 9 рёбер

9.

Свойство 2
Между двумя вершинами существует только один
путь.
«В дереве невозможно выбрать
другую дорогу — путь только один.»
Свойство 3
Если добавить одно ребро → появится цикл
Если убрать одно ребро → граф распадётся

10. Что будет, если убрать корень дерева?

У нас получится одно или
несколько новых деревьев.
Какие ещё поддеревья есть в этом графе?

11.

12. Какие узлы — потомки узла Верх?

Какие узлы — потомки узла Верх?
Какой узел —
предок узла Верх?
Одежда
Футболки, рубашки

13.

Диаметр дерева – количество рёбер в
максимальной
цепи,
т.е.
длина
цепи,
связывающей две наиболее удалённые вершины.
B
А
M
Е
K
L
D
В дереве, изображённом на рисунке, наиболее
удалёнными являются вершины L и D.
А количество рёбер между ними равно 5. Значит, диаметр
дерева равен 5.

14.

В любом дереве ( в котором более одной
вершины) есть вершина, из которой выходит
ровно одно ребро. Такую вершину называют
концевой или висячей.
B
А
M
Е
K
L
В дереве, изображённом на
рисунке,
концевыми
будут
вершины К, L и D.
D
Деревья обладают важным свойством.
В ДЕРЕВЕ КОЛИЧЕСТВО ВЕРШИН НА 1 БОЛЬШЕ ЧИСЛА РЁБЕР.

15. Решение задачи: Собраться в путешествие, чтобы ничего не забыть.

16.

ПРИМЕР 2. Возьмём симметрическую монету и подбросим 3
раза. Чтобы изобразить этот случайный опыт, построим дерево.
От начальной вершины S нарисуем ветви вниз к вершинам,
которые обозначим О(орёл) и Р (решка) – это результаты первого
броска. От каждой из них идут ещё два ребра вниз к вершинам О
и Р, изображающие второго броска. Точно также покажем
результаты третьего броска ( см. рисунок)
Получилось дерево случайного
эксперимента. В этом дереве
восемь
цепей,
ведущих
из
начальной вершины S в концевые
вершины:
SOOO; SOOP; SOPO; SOPP; SPOO;
SPOP; SPPO; SPPP

17.

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

18.

19.

Задача 1.(У) Какие из графов, изображённые на
рисунке являются деревьями.

20.

Задача 2. Постройте какие-нибудь деревья с 3, 4, 5, 6 вершинами и
посчитайте число ребер в полученных графах.
Возможные варианты ответов:
3 вершины
2 ребра
4 вершины
3 ребра
5 вершин
4 ребра
6 вершин
5 рёбер
В ДЕРЕВЕ КОЛИЧЕСТВО ВЕРШИН НА 1 БОЛЬШЕ ЧИСЛА РЁБЕР.

21.

Задача 3. Нарисуйте в тетради какое-нибудь дерево, в котором 7
вершин, причём степень 1 имеют ровно:
a) 2 вершины;
б) 4 вершины;
в) 6 вершин.
а)
б)
в)

22.

Задача 4. План тропинок в парке представляет собой̆ дерево (см. рис.).
Ворота в парке обозначены вершиной S. Сколько цепей ведёт из
вершины S:
a) к кафе;
б) к пруду;
в) к саду камней̆?
Ответ:
а) к кафе ведёт 1 цепь;
б) к пруду ведёт 3 цепи;
в) к саду камней ведёт 1 цепь.

23.

Задача 5. Придумайте какой-нибудь случайный опыт, моделью
которого служит дерево, показанное на рисунке.
Пример 1: Игральный кубик
бросили 2 раза. Известно, что в
первый раз выпало 1 или 2 очка.
Пример 2: В столовой с котлетой
можно
взять
гарниры
(картофельное пюре, картофель
фри, гречневая каша, рис, фасоль,
тушёная
капуста)
и
салаты
(винегрет,
мимоза,
оливье,
греческий салат, селёдка под
шубой, «Цезарь»)

24.

25.

Вопрос 1. Что такое дерево?
ДЕРЕВО - ЭТО СВЯЗНЫЙ ГРАФ БЕЗ ЦИКЛОВ

26.

Вопрос 2. Бывают ли в дереве петли; цепи; циклы?
В дереве не бывает петель и циклов, но
может быть одна цепь, которая соединяет
две вершины.