-
Курсы
-
Другое
Найден 101 материал по теме
Предпросмотр материала:
Дерево. Свойства дерева: единственность пути, существование висячей вершины, связь между числом вершин и числом рёбер.
Подготовила:
учитель математики
МБОУ Г.ГОРЛОВКИ «ШКОЛА № 42»
Рыбина М.В.
Повторим понятия
Графом называется конечное множество точек, некоторые из которых соединены линиями. При этом точки называются вершинами графа, а линии — рёбрами.
Рёбра можно изобразить дугами или отрезками. Каждое ребро соединяют две вершины. Вершина не обязательно должна быть соединена с другими вершинами.
Если из вершины не выходит ни одно ребро, то её называют изолированной.
Повторим понятия
Если в графе любые две вершины соединены путём, то такой граф называется связным.
Путём в графе от вершины А до вершины B назовём такую последовательность рёбер графа, в которой каждые два соседних ребра имеют общую вершину.
Например, из А в В существует два пути:
АD – DB и АС – СD – DB
Длина пути — это количество рёбер в этом пути.
Длина пути АD – DB равна 2, а длина пути АС – СD – DB равна 3.
Граф, у которого каждая вершина соединена ребром с любой другой вершиной, называется полным.
Чтобы найти количество рёбер в полном графе, у которого n - вершин, нужно воспользоваться формулой: 𝑛(𝑛−1) 2
Цикл в графе — это путь, у которого начало и конец — в одной вершине, а рёбра и промежуточные вершины не повторяются.
Дерево — это связный граф без циклов.
На рисунке изображён граф, в котором можно из каждой вершины добраться до каждой, но при этом в нём нет циклов.
Из примера видно, что в дереве нельзя, передвигаясь по рёбрам и не проходя по одному ребру два или более раз, вернуться в исходную вершину.
Граф, в котором только одна вершина без рёбер, можно рассматривать как простейшее дерево.
Диаметр дерева — количество рёбер в максимальной цепи, т. е. длина цепи, связывающей две наиболее удалённые вершины.
В дереве, изображённом на рисунке наиболее удалёнными являются вершины L и D. А количество рёбер между ними равно 5. Значит, диаметр дерева на рисунке равен 5.
В любом дереве (в котором более одной вершины) есть вершина, из которой выходит ровно одно ребро. Такую вершину называют концевой или висячей.
На нашем рисунке это вершины L, K, D.
Пример 1
Возьмем симметричную монету и подбросим её три раза. Чтобы изобразить этот опыт, построим дерево
S
О
Р
О
О
Р
Р
О
О
О
О
Р
Р
Р
Р
Название «дерево» и происходит оттого, что цепи «ветвятся», не образуя циклов. Разница только в том. Что в природе деревья растут снизу вверх. А математические деревья мы рисуем как нам удобно.
Рассмотрим пример водоснабжения в небольшом поселке. Трубы идут от водонапорной башни и ветвятся, пролегая вдоль улиц. Из больших труб проходят малые к домам. Вершина нашего так называемого дерева – водонапорная башня.
Бывают бесконечные деревья, то есть деревья, в которых бесконечно много вершин и ребер.
Пример 2
Одноклассники Андрей, Борис, Вадим, Григорий, Дмитрий и Евгений устроили турнир по настольному теннису и решили играть каждый с каждым. Турнир еще не закончен. Ребра графа показывают, кто с кем сыграл к этому моменту.
Больше всех партий сыграли Евгений и Григорий – по три партии. Андрей. Борис и Дмитрий сыграли по две партии. Вадим пока не сыграл ни одной партии.
Степень вершины в графе – это количество исходящих из неё ребер.
Можно сказать, что степень вершины В равна 0, степени вершин А, Б, Д равны 2, а степени вершин Г и Е равны 3.
Проверь себя!
да
4
5
3
Вершина графа, имеющая нечётную степень, называется нечетной, а чётную степень – чётной.
Нечётная степень
Чётная степень
Так как у каждого ребра два конца, то сумма степеней всех вершин в два раза больше числа ребер, то есть четное число.
Теорема у сумме степеней вершин. В любом графе сумма степеней всех вершин является четным числом.
В любом графе количество вершин нечетной степени четно.
Свойства деревьев
Теорема. Любые две вершины в дереве соединены единственной цепью.
Свойство 1. Если из дерева удалить ребро. То граф перестанет быть связным.
У концевой (висячей) вершины степень равна 1.
Свойство 2. Если в дереве конечное число вершин и есть хотя бы одно ребро, то в таком дереве есть концевая вершина.
Свойство 3. В конечном дереве число ребер на 1 меньше числа вершин.
Проверь себя!
нет
да
нет
Задание 1
Какие из графов являются деревьями?
ОТВЕТ: а, б, в – деревья; г – не дерево (не связный граф), д – не дерево (граф имеет цикл)
Задание 2
Нарисуйте в тетради какое-нибудь дерево, в котором 7 вершин, причём степень 1 имеют ровно:
a) 2 вершины; б) 4 вершины; в) 6 вершин.
Задание 3
В дереве 100 вершин. Какое в нём может быть:
а) наибольшее число концевых вершин;
б) наименьшее число концевых вершин?
ОТВЕТ: 99
ОТВЕТ: 2
Задание 4
План тропинок в парке представляет собой дерево. Ворота обозначены вершиной S. Сколько цепей ведет из вершины S к:
А) усадьбе;
Б) детской площадке;
В) кафе;
Г) пруду;
Д) фонтану;
Е) памятнику;
Ж) саду камней.
Задание 5
Сколько концевых вершин на дереве?
ОТВЕТ: 8
ОТВЕТ: 12
ОТВЕТ: 2
Задание 6
На рисунке показано дерево. Рассмотрите цепи, соединяющие начальную вершину S с концевыми. Сколько таких цепей имеют длину 2; длину 3; длину 4?
А
К
М
О
Б
С
Р
Е
Т
Задание 7
Сколько вершин в дереве, в котором:
14 рёбер;
б) 27 рёбер;
в) 31 ребро
ОТВЕТ: 15
ОТВЕТ: 28
ОТВЕТ: 32
Задание 8
Будет ли связным граф, который получится из дерева, если из него удалить:
ребро, связывающее две неконцевые вершины;
б) концевую вершину вместе с выходящим из неё ребром?
ОТВЕТ: не будет согласно свойству 1
ОТВЕТ: будет
Домашнее задание:
В дереве 4 вершины. Сколько концевых вершин в нем может быть? Приведите примеры дерева для каждого возможного значения.
На рисунке показано дерево. Рассмотрите цепи, соединяющие начальную вершину S с концевыми. Сколько таких цепей имеют длину 2; длину 3; длину 4?
Сколько рёбер в дереве, в котором:
a) 87 вершин; б) 487 вершин; в) 317 вершин
Изобразите какое-нибудь дерево, в котором:
a) 8 вершин, 5 из них концевые;
б) 10 вершин, 6 из них концевые.
5. Изобразите какое-нибудь дерево, в котором:
a) 4 вершины степени 3 и 6 вершин степени 1;
б) 2 вершины степени 4, 2 вершины степени 3 и 8 вершин степени 1.
Использованные источники:
https://www.yaklass.ru/p/veroyatnost-i-statistika/7-klass/teoriia-grafov-7271003/tcepi-i-tcikl-puti-v-grafe-7276192/re-3ae2a5c5-5835-4b64-a9e1-e24e8be59997
https://www.yaklass.ru/p/veroyatnost-i-statistika/8-klass/vvedenie-v-teoriiu-grafov-7310238/derevo-svoistva-dereva-7303500/re-7b216e40-0fc0-4ead-b9ea-22e0c0017ad8
Файл будет скачан в формате:
Настоящий материал опубликован пользователем Рыбина Марина Васильевна. Инфоурок является информационным посредником и предоставляет пользователям возможность размещать на сайте методические материалы. Всю ответственность за опубликованные материалы, содержащиеся в них сведения, а также за соблюдение авторских прав несут пользователи, загрузившие материал на сайт.
Если Вы считаете, что материал нарушает авторские права либо по каким-то другим причинам должен быть удален с сайта, Вы можете оставить жалобу на материал.
В каталоге 6 352 курса по разным направлениям
