СДЕЛАЙТЕ СВОИ УРОКИ ЕЩЁ ЭФФЕКТИВНЕЕ, А ЖИЗНЬ СВОБОДНЕЕ

Благодаря готовым учебным материалам для работы в классе и дистанционно

Скидки до 50 % на комплекты
только до

Готовые ключевые этапы урока всегда будут у вас под рукой

Организационный момент

Проверка знаний

Объяснение материала

Закрепление изученного

Итоги урока

Урок 21. по предмету "Вероятность и статистика" в 8-м классе по теме "Свойства дерева"

Категория: Прочее

Нажмите, чтобы узнать подробности

Просмотр содержимого документа
«Урок 21. по предмету "Вероятность и статистика" в 8-м классе по теме "Свойства дерева"»

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

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

Вспомним! Что такое дерево Дерево — это связный граф без циклов. Три главных свойства, которые мы сегодня доказываем и применяем: Между любыми двумя вершинами существует единственный путь . В любом дереве есть хотя бы одна висячая вершина (вершина степени 1). В дереве с n вершинами ровно n −1 рёбер. Как пользоваться формулой. Если граф — дерево, Е — количество ребер, V - количество вершин, то E = V −1 (рёбер на одно меньше, чем вершин). Эта формула работает и «в обратную сторону»: она помогает проверить, является ли граф деревом.

Вспомним! Что такое дерево

Дерево — это связный граф без циклов. Три главных свойства, которые мы сегодня доказываем и применяем:

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

В любом дереве есть хотя бы одна висячая вершина (вершина степени 1).

В дереве с n вершинами ровно n −1 рёбер.

Как пользоваться формулой. Если граф — дерево, Е — количество ребер, V - количество вершин, то E = V −1 (рёбер на одно меньше, чем вершин).

Эта формула работает и «в обратную сторону»: она помогает проверить, является ли граф деревом.

Свойство 1: единственность пути Между любыми двумя вершинами дерева существует ровно один путь. Доказательство:  1. Путь существует. Дерево — связный граф по определению, а связность и означает, что между любыми двумя вершинами есть хотя бы один путь.  2. Путь только один. Предположим противное: между вершинами A и B есть два разных пути P 1  и P 2 . Тогда, пройдя из A в B по пути P 1  и вернувшись из B в A по пути P 2 ​ , мы получим замкнутый маршрут. Если два пути действительно различны, где-то они расходятся и сходятся снова — а это значит, что в графе образуется цикл . Но в дереве циклов нет — противоречие. Значит, путь единственный.  Пример: если бы между двумя сёлами в дереве (без петель на дорогах) вели две разные дороги, то, выехав по одной и вернувшись по другой, мы сделали бы «круг» — а кругов в дереве не бывает.

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

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

Доказательство:

1. Путь существует. Дерево — связный граф по определению, а связность и означает, что между любыми двумя вершинами есть хотя бы один путь.

2. Путь только один. Предположим противное: между вершинами A и B есть два разных пути P 1 и P 2 . Тогда, пройдя из A в B по пути P 1 и вернувшись из B в A по пути P 2 ​ , мы получим замкнутый маршрут. Если два пути действительно различны, где-то они расходятся и сходятся снова — а это значит, что в графе образуется цикл .

Но в дереве циклов нет — противоречие. Значит, путь единственный.

Пример: если бы между двумя сёлами в дереве (без петель на дорогах) вели две разные дороги, то, выехав по одной и вернувшись по другой, мы сделали бы «круг» — а кругов в дереве не бывает.

Пример: В этом графе между вершинами 1 и 4 два пути: 1—2—4 и 1—3—4 . Пути два → их замыкание даёт цикл 1—2—4—3—1 → граф не дерево .

Пример:

В этом графе между вершинами 1 и 4 два пути:

1—2—4 и 1—3—4 .

Пути два → их замыкание даёт цикл

1—2—4—3—1 → граф не дерево .

Свойство 2: существование висячей вершины В любом дереве есть хотя бы одна вершина степени 1 (висячая вершина). Вспомним! Степенью вершины называется количество ребер, из нее выходящих. Следовательно висячая вершина это вершина, из которой выходит ровно одно ребро. На рисунке вершины Г, Д, Е и Ж - висячие

Свойство 2: существование висячей вершины

В любом дереве есть хотя бы одна вершина степени 1 (висячая вершина).

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

На рисунке вершины Г, Д, Е и Ж - висячие

Доказательство (метод «иди и не возвращайся») Возьмём любую вершину дерева и начнём из неё идти по рёбрам, не поворачивая назад (не возвращаясь в вершину, из которой только что пришли). Вершин в дереве конечное число, значит, рано или поздно мы не сможем идти дальше. Остановиться мы можем только в такой вершине, из которой выходит одно ребро — то, по которому мы пришли (если бы выходили и другие рёбра, мы бы пошли дальше по одному из них; повернуть назад нам не разрешают правила движения). Вершина, из которой выходит ровно одно ребро, — это и есть висячая вершина. Пример: Допустим мы выходим из вершины 1: А—Б—Г. Дальше пути нет. Вершина Г  — висячая

Доказательство (метод «иди и не возвращайся»)

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

Вершин в дереве конечное число, значит, рано или поздно мы не сможем идти дальше.

Остановиться мы можем только в такой вершине, из которой выходит одно ребро — то, по которому мы пришли (если бы выходили и другие рёбра, мы бы пошли дальше по одному из них; повернуть назад нам не разрешают правила движения).

Вершина, из которой выходит ровно одно ребро, — это и есть висячая вершина.

Пример: Допустим мы выходим из вершины 1: А—Б—Г. Дальше пути нет.

Вершина Г — висячая

Почему нельзя застрять где-то ещё?  Если в текущей вершине степень 2 или больше, значит, кроме ребра «откуда пришли», есть ещё хотя бы одно ребро «вперёд» — по нему и идём. Застрять можно только там, где рёбер, кроме «обратного», нет — то есть при степени 1. А цикла при этом не образуется, потому что мы в дереве и, не возвращаясь назад, просто не можем прийти в вершину повторно (иначе возник бы цикл). Пример: В вершине А степень равна 2, значит, можно идти дальше. Дальше можно выбрать вершины Б или В, степень каждой из которых равна 3 и можно идти дальше. Из вершины Б можно пойти в вершины Г или Д, а из вершины В в вершины Е или Ж, у каждой из которых степень равна 1. То есть в вершинах Г, Д, Е и Ж будет остановка, они висячие.

Почему нельзя застрять где-то ещё?

Если в текущей вершине степень 2 или больше, значит, кроме ребра «откуда пришли», есть ещё хотя бы одно ребро «вперёд» — по нему и идём. Застрять можно только там, где рёбер, кроме «обратного», нет — то есть при степени 1.

А цикла при этом не образуется, потому что мы в дереве и, не возвращаясь назад, просто не можем прийти в вершину повторно (иначе возник бы цикл).

Пример: В вершине А степень равна 2, значит, можно идти дальше.

Дальше можно выбрать вершины Б или В, степень каждой из которых равна 3 и можно идти дальше. Из вершины Б можно пойти в вершины Г или Д, а из вершины В в вершины Е или Ж, у каждой из которых степень равна 1.

То есть в вершинах Г, Д, Е и Ж будет остановка, они висячие.

Свойство 3: число рёбер E на 1 меньше числа вершин V: E=V-1   В дереве с n вершинами ровно n −1 ребро. Пример: На рисунке дерево с 7 вершинами (А, Б, В, Г, Д, Е, Ж) и 6 ребрами (А-Б, А-В, Б-Г, Б-Д, В-Е, В-Ж).

Свойство 3: число рёбер E на 1 меньше числа вершин V: E=V-1

В дереве с n вершинами ровно n −1 ребро.

Пример: На рисунке дерево с 7 вершинами (А, Б, В, Г, Д, Е, Ж) и 6 ребрами (А-Б, А-В, Б-Г, Б-Д, В-Е, В-Ж).

Доказательство методом математической индукции (база и шаг) База. Дерево из одной вершины: n =1 , рёбер 0. Формула E = n −1=0 верна. Возьмём дерево с n вершинами. По свойству 2 в нём есть висячая вершина X (степени 1). Шаг. Пусть для всех деревьев с числом вершин меньше n формула верна.

Доказательство методом математической индукции (база и шаг)

База. Дерево из одной вершины: n =1 , рёбер 0. Формула E = n −1=0 верна.

Возьмём дерево с n вершинами.

По свойству 2 в нём есть висячая вершина X (степени 1).

Шаг. Пусть для всех деревьев с числом вершин меньше n формула верна.

Доказательство формулы: Отрежем её: удалим вершину X и единственное выходящее из неё ребро. Граф остался связным (мы удалили «лист дерева», через который ничего не проходило) и по-прежнему без циклов — значит, это снова дерево. В новом дереве n −1 вершина и E −1 рёбер. По предположению индукции: E −1=( n −1)−1. Отсюда E = n −1 . Интуиция: каждое новое ребро дерева «приносит» ровно одну новую вершину. Начали с одной вершины — построили цепочку: +1 ребро — +1 вершина. Поэтому рёбер всегда на одно меньше, чем вершин.

Доказательство формулы:

Отрежем её: удалим вершину X и единственное выходящее из неё ребро. Граф остался связным (мы удалили «лист дерева», через который ничего не проходило) и по-прежнему без циклов — значит, это снова дерево.

В новом дереве n −1 вершина и E −1 рёбер. По предположению индукции: E −1=( n −1)−1. Отсюда E = n −1 .

Интуиция: каждое новое ребро дерева «приносит» ровно одну новую вершину. Начали с одной вершины — построили цепочку: +1 ребро — +1 вершина. Поэтому рёбер всегда на одно меньше, чем вершин.

Применение: проверка, является ли граф деревом Граф является деревом тогда и только тогда, когда выполнены два условия сразу : Граф связный (из любой вершины можно пройти в любую другую). Рёбер ровно на одно меньше числа вершин: E = V −1 . Дополнительная быстрая проверка:  у дерева нет циклов, а значит, оно обязано иметь висячую вершину (свойство 2). Если у графа E = V −1 , но он не связный — он состоит из нескольких «кусков»-деревьев (лес), или где-то обязательно есть цикл. Пример: На рисунке у графа 7 вершин и 6 ребер, но он несвязный: тогда у него есть цикл: В − Е − Ж

Применение: проверка, является ли граф деревом

Граф является деревом тогда и только тогда, когда выполнены два условия сразу :

  • Граф связный (из любой вершины можно пройти в любую другую).
  • Рёбер ровно на одно меньше числа вершин: E = V −1 .

Дополнительная быстрая проверка:

  • у дерева нет циклов, а значит, оно обязано иметь висячую вершину (свойство 2).
  • Если у графа E = V −1 , но он не связный — он состоит из нескольких «кусков»-деревьев (лес), или где-то обязательно есть цикл.

Пример: На рисунке у графа 7 вершин и 6 ребер, но он несвязный: тогда у него есть цикл: В − Е − Ж

Задача 1 (проверка по формуле) В графе 10 вершин и 9 рёбер, граф связный. Является ли он деревом? Решение. Проверяем: E =9 , V −1=10−1=9 . Формула выполнена, граф связный → это дерево. Ответ: да.

Задача 1 (проверка по формуле)

В графе 10 вершин и 9 рёбер, граф связный.

Является ли он деревом?

Решение. Проверяем:

E =9 ,

V −1=10−1=9 .

Формула выполнена, граф связный → это дерево.

Ответ: да.

Задача 2 (ловушка) В графе 8 вершин и 7 рёбер. Является ли он деревом? Решение. Формула E = V −1 выполнена, но про связность мы ничего не знаем. Контрпример: не связный граф из двух частей — цикл «треугольник» (3 вершины, 3 ребра) и дерево из 5 вершин (4 ребра). Всего 8 вершин и 3+4=7 рёбер, но граф несвязный и, значит, он содержит цикл — деревом он не является. Ответ: нет, обязательно нужно ещё проверить связность.

Задача 2 (ловушка)

В графе 8 вершин и 7 рёбер. Является ли он деревом?

Решение. Формула E = V −1 выполнена, но про связность мы ничего не знаем.

Контрпример: не связный граф из двух частей — цикл «треугольник» (3 вершины, 3 ребра) и дерево из 5 вершин (4 ребра). Всего 8 вершин и 3+4=7 рёбер, но граф несвязный и, значит, он содержит цикл — деревом он не является.

Ответ: нет, обязательно нужно ещё проверить связность.

Задача 3 (подсчёт) В графе, который является деревом, 15 вершин. Сколько у него рёбер? Решение.  E =15−1=14 . Ответ: 14 рёбер.

Задача 3 (подсчёт)

В графе, который является деревом, 15 вершин.

Сколько у него рёбер?

Решение.

E =15−1=14 .

Ответ: 14 рёбер.

Задача 4 (обратная) У дерева 12 рёбер. Сколько у него вершин? Решение.  V = E +1=13 . Ответ: 13 вершин.

Задача 4 (обратная)

У дерева 12 рёбер. Сколько у него вершин?

Решение.

V = E +1=13 .

Ответ: 13 вершин.

Задача 5 (на висячие вершины) Существует ли дерево, у которого 6 вершин, одна из которых степени 3, одна степени 2, остальные вершины висячие? Решение: Пусть висячих вершин равно х, каждая степени 1. По свойству 3 у дерева 5 рёбер. Сумма степеней всех вершин равна удвоенному числу рёбер: 3+2+х⋅1=2⋅5=10, Тогда х=10-5=5. Получается, что у дерева 5 висячих вершин, одна вершина степени 3, одна вершина степени 2. 5+1+1=7, то есть у дерева с такими условиями должно быть 7 вершин, а унас по условию задачи их 6: 7≠6, Ответ: Нет, такого дерева не существует

Задача 5 (на висячие вершины)

Существует ли дерево, у которого 6 вершин, одна из которых степени 3, одна степени 2, остальные вершины висячие?

Решение: Пусть висячих вершин равно х, каждая степени 1.

По свойству 3 у дерева 5 рёбер.

Сумма степеней всех вершин равна удвоенному числу рёбер: 3+2+х⋅1=2⋅5=10,

Тогда х=10-5=5.

Получается, что у дерева 5 висячих вершин, одна вершина степени 3, одна вершина степени 2.

5+1+1=7, то есть у дерева с такими условиями должно быть 7 вершин, а унас по условию задачи их 6: 7≠6,

Ответ: Нет, такого дерева не существует

Типичные ошибки «Формула E = V −1 гарантирует дерево».  Нет! Она работает только вместе со связностью (см. задачу 2). «Висячая вершина — это вершина степени 0».  Нет: висячая вершина — степени 1 . Вершина степени 0 — изолированная, в дереве с числом вершин больше 1 изолированных вершин быть не может (граф связный). Забывают удвоение суммы степеней. Сумма степеней всех вершин любого графа равна удвоенному числу рёбер: ∑ deg( v )=2 E . Это удобный инструмент для задач типа 5. Путают «есть путь» с «есть неколько путей». В генеалогическом древе между предком и потомком ровно одна «цепочка родства» — это и есть следствие свойства 1.

Типичные ошибки

«Формула E = V −1 гарантирует дерево».

Нет! Она работает только вместе со связностью (см. задачу 2).

«Висячая вершина — это вершина степени 0».

Нет: висячая вершина — степени 1 . Вершина степени 0 — изолированная, в дереве с числом вершин больше 1 изолированных вершин быть не может (граф связный).

Забывают удвоение суммы степеней. Сумма степеней всех вершин любого графа равна удвоенному числу рёбер:

∑ deg( v )=2 E . Это удобный инструмент для задач типа 5.

Путают «есть путь» с «есть неколько путей». В генеалогическом древе между предком и потомком ровно одна «цепочка родства» — это и есть следствие свойства 1.

Решите самостоятельно В дереве 20 вершин. Сколько рёбер? Граф связный, у него 25 рёбер и 26 вершин. Является ли он деревом? В дереве 8 вершин: одна вершина степени 4, одна степени 3. Сколько висячих вершин может быть в этом графе? Может ли в дереве быть ровно 2 вершины степени 3 и ни одной висячей? Ответ обоснуйте

Решите самостоятельно

  • В дереве 20 вершин. Сколько рёбер?
  • Граф связный, у него 25 рёбер и 26 вершин. Является ли он деревом?
  • В дереве 8 вершин: одна вершина степени 4, одна степени 3. Сколько висячих вершин может быть в этом графе?
  • Может ли в дереве быть ровно 2 вершины степени 3 и ни одной висячей? Ответ обоснуйте
Вопросы для рефлексии Почему два разных пути между одними и теми же вершинами означают наличие цикла? Где в доказательстве свойства 3 используется свойство 2 (висячая вершина)? Какие два условия нужно проверить, чтобы убедиться, что граф — дерево?

Вопросы для рефлексии

  • Почему два разных пути между одними и теми же вершинами означают наличие цикла?
  • Где в доказательстве свойства 3 используется свойство 2 (висячая вершина)?
  • Какие два условия нужно проверить, чтобы убедиться, что граф — дерево?