Свойства дерева: единственность пути

1.

Свойства дерева: единственность
пути, существование висячей
вершины, связь между числом
вершин и числом рёбер

2.

Задание 1

3.

Задание 1
Распределите утверждения на две группы: верно,
неверно.
a) Графом называется множество точек, некоторые из
которых могут быть соединены линиями.
b) Две вершины, которые являются соседними,
называются смежными вершинами.
c) Два ребра, у которых две общие вершины,
называются смежными ребрами.
d) Вершина, из которой не выходит ни одно ребро,
называется изолированной.
e) Путь называется цепью, если в нём не
повторяются вершины.
f) Простым циклом в графе называется цепь, у
которой начало и конец совпадают.

4.

Задание 1
g) Путем в графе от вершины А до вершины F называется
последовательность ребер графа и его вершин, такие,
что каждые два последовательных ребра имеют общую
вершину, и никакое ребро не встречается более двух
раз.
h) Циклом называется граф, который является цепью и у
него не совпадают начало и конец.
i) Граф называется связным, если для любой его
вершины найдется путь, связывающий ее с любой
другой вершиной этого графа.
j) Количество вершин в пути называется длиной этого
пути.
k) Граф, состоящий из двух изолированных вершин,
также является деревом.
l) Деревом называется всякий связный граф, не
имеющий циклов.

5.

Задание 2
Заполните табличку. Выберите обязательные
пункты для каждого определения из 1
столбика.
Ребро не
встречается два
раза
Путь
Цепь
Цикл
Простой цикл
Вершины не
повторяются
Начало и конец
совпадают

6.

Задание 3
На рисунке изображен граф.
Назовите по 2 в каждом пункте а-г:
а) Путь;
б) Цепь;
в) Цикл;
г) Простой цикл.

7.

Задание 4
Выберите
деревьями.
графы,
которые
а)
в)
б)
г)
являются

8.

Задание 4
Выберите
деревьями.
графы,
которые
д)
ж)
е)
з)
являются

9.

Степенью (валентностью или порядком)
вершины называется количество ребер,
исходящих из этой вершины.
Вершина называется четной, если из нее
выходит четное количество ребер.
Вершина называется нечетной, если из нее
выходит нечетное количество ребер.

10.

Задание 5
Определите степень каждой вершины графа,
изображенного на рисунке.

11.

Задание 6
На рисунке изображен граф. Сколько его
вершин имеют степень равную:
а) 1;
б) 3;
в) 5.

12.

Задание 7
На рисунке изображен граф. Сколько его
вершин имеют:
а) четную степень; б) нечетную степень.

13.

Задание 8
На рисунке изображен граф.
а) Определите наибольшую степень вершины графа.
б) Определите наименьшую степень вершины графа.
в) Сколько вершин имеют наибольшую степень?
г) Сколько вершин имеют наименьшую степень?

14.

Теорема 1
Между
любыми
двумя
вершинами дерева существует
единственный путь, который
их соединяет.

15.

Вершина графа, из которой выходит только
одно ребро, называется висячей.
Например, вершины B, D и E являются
висячими.

16.

Теорема 2
В любом дереве (в котором
более одной вершины) есть
вершина, из которой выходит
ровно
одно
ребро,
т.е.
вершина является висячей.

17.

Теорема 3
В дереве количество вершин на 1
больше количества рёбер, то есть
! = # + 1.
! – количество вершин, #
количество рёбер.
–

18.

Задание 9
Запишите все висячие вершины для графов в
пунктах а-г.
а)
в)
б)
г)

19.

Задание 10
Найдите количество
которые имеют:
a) 5 вершин;
b) 8 вершин;
c) L вершин;
d) K − 1 вершин.
рёбер
в
деревьях,

20.

Задание 11
Найдите количество вершин в деревьях,
которые имеют:
a) 5 рёбер;
b) 8 рёбер;
c) L рёбер;
d) K − 1 рёбер.

21.

Задание 12
Изобразите все деревья с 6
вершинами. Объясните, почему
других деревьев нет.

22.

Задание 12. Ответ

23.

Задание 13
Докажите, что в дереве (в котором больше
одной вершины) найдутся хотя бы две
висячие вершины.
Задание 14
Волейбольная
сетка
имеет
вид
прямоугольника 10 на 95 клеточек. Какое
наибольшее число раз можно разрезать
составляющие сетку верёвочки так, чтобы
сетка не распалась на кусочки?

24.

Задание 15
Изобразите граф, у которого:
а) 6 вершин и их степени равны 1, 1, 1, 1, 3, 3.
б) 5 вершин и их степени равны 3, 3, 3, 3, 4.
в) 7 вершин и их степени равны 0, 1, 3, 3, 3, 4,
4.
Сравните полученные в классе результаты.

25.

Задание 16
На рисунке изображен граф. Назовите по 2 в
каждом пункте а-г:
• Путь;
• Цепь;
• Цикл;
• Простой цикл.

26.

Задание 17
На рисунке изображен граф. Найдите путь из
вершины А в вершину В.

27.

Задание 18
На рисунке изображен граф. Найдите цепь из
вершины С в вершину В.

28.

Задание 19
На рисунке изображен граф. Найдите простой
цикл, содержащий в себе точку А.

29.

Задание 20
На рисунке изображен граф. Перечислите его
вершины и ребра. Назовите две пары
смежных вершин и две пары смежных ребер.

30.

Задание 21
На рисунке изображен граф. Какова
наибольшая длина его простого цикла?

31.

Задание 22
На рисунке изображена сетка, по которой
бегают муравьи. Сколько есть кратчайших
путей, чтобы добраться из пункта К в пункт
Q?