Графы и деревья

1. Граф

• Граф – это совокупность узлов (вершин) и соединяющих их ребер
(дуг)

2. Виды графов

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

3.

4.

5. ДЕРЕВЬЯ

• ДЕРЕВО (частный случай графа) – связный граф
без циклов
Цепи «ветвятся», не образуя циклов

6.

7.

8. Из леса, где плохая связь пытаются послать смс (Н-неудачно, У-удачно)

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

9.

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

10. На рисунке изображен граф с пятью вершинами

Степень вершины А=1
Степень вершины Б=2
Степень вершины В=3
Степень вершины Г=2
Степень вершины Д=0

11.

Также степени можно определить по таблице
В таблице приведены данные о дорогах между населенными пунктами
Найдем степени для каждого пункта

12. Свойства дерева

• Любые две вершины в дереве соединены единственной
цепь;
• Если из дерева удалить ребро, то граф перестанет быть
связным;
• Концевой (висячей) вершиной называется вершина, из
которой выходит ровно одно ребро, то есть вершина
степени 1;
• В конечном дереве число рёбер на 1 меньше числа
вершин.

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

кафе;
б) к пруду;
в) к саду камней?

14. Сколько концевых вершин в дереве на рисунке?

15. На рисунке показано дерево. Рассмотрите цепи, соединяющие начальную вершину S с концевыми. Сколько таких цепей имеют длину 2;

длину 3; длину 4?

16. Симметричную монету подбросили 3 раза

17. На рисунке справа схема дорог N-го района изображена в виде графа, в таблице содержатся сведения о дорогах между населенными

пунктами (звездочка
означает, что дорога между соответствующими городами есть).
Так как таблицу и схему рисовали независимо друг от друга, то нумерация
населённых пунктов в таблице никак не связана с буквенными обозначениями
на графе.
Определите номера населенных пунктов A и G в таблице.
В ответе запишите числа в порядке возрастания без разделителей.

18.

На рисунке справа схема дорог N-го района изображена в виде графа,
в таблице содержатся сведения о длинах этих дорог (в километрах)
Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых
пунктов в таблице никак не связана с буквенными обозначениями на графе.
Определите, какова длина дороги из пункта В в пункт Е.
В ответе запишите целое число – так, как оно указано в таблице.

19. ДОМАШНЕЕ ЗАДАНИЕ

• Решить задачи и ответить на вопросы со слайдов
№5, 9, 10, 11, 13, 14
• Выучить определения
• Подготовиться к работе