Самостоятельная работа по теме «Дерево. Свойства дерева» (8 класс) Вариант 1 1. На рисунке показано дерево случайного опыта. Сколько элементарных событий в этом опыте благоприятствует событию А? 2. Антон гуляет по своему дачному посёлку. Он выходит из точки Ѕи на каждой развилке с равными шансами выбирает следующую дорожку. Схема дорожек показана на рисунке. а) Сколько дорожек приведёт Антона в рощу? б) Сколько дорожек не приведут Антона ни к школе, ни к библиотеке? 3. На рисунке изображён граф. Ответь на вопросы: а. является ли граф, изображённый на рисунке, деревом? б. сколько рёбер у данного графа? в. сколько вершин у графа, изображённого на рисунке? г. сколько концевых вершин у графа, изображённого на рисунке? 4. Количество вершин дерева равно 31. Какое наибольшее число рёбер может иметь это дерево? 5. В агрокомплексе «Цветочный» есть 140 грядок с тюльпанами. Каждые две грядки соединяет ровно одна дорожка. Определите количество дорожек, соединяющих грядки с тюльпанами. 6. Существует ли дерево, в котором: а. количество вершин 8, а рёбер 20; б. количество вершин 54, а рёбер 53; в. количество вершин 26, а рёбер 277 7. Постройте дерево, в котором 12 вершин, причем 3 вершины имеют степень 1, 2 вершины степени 2, 2 вершины степени 3

Привет! Разберём эту самостоятельную работу по теории графов и деревьев. Сейчас все решим!

Вариант 1

1. Дерево случайного опыта

На рисунке нужно посчитать, сколько элементарных событий благоприятствуют событию A. Судя по изображению (хотя оно и не очень четкое), есть 4 пути, ведущие к событию A.

Ответ: 4

Проверка за 10 секунд: Просто пересчитайте все ветки, ведущие к вершине A.

Доп. профит (База): В теории вероятностей дерево случайного опыта помогает визуализировать возможные исходы и их вероятности.

2. Прогулка Антона

а) Считаем количество дорожек, которые приведут Антона в рощу. Из точки S в рощу ведут 2 дорожки.

б) Считаем количество дорожек, которые не приведут Антона ни к школе, ни к библиотеке. Это дорожки, ведущие в рощу и на детскую площадку. Всего таких дорожек 3.

Ответ: а) 2, б) 3

Проверка за 10 секунд: Визуально проследите пути от S до каждого пункта назначения.

Доп. профит (Читерский прием): В задачах на графы всегда полезно начинать с визуального анализа и подсчета путей.

3. Анализ графа

а) Является ли граф деревом? Нет, граф не является деревом, так как в нём есть циклы (например, можно пройти по кругу).

б) Считаем количество рёбер у данного графа. На рисунке 7 рёбер.

в) Считаем количество вершин у графа, изображённого на рисунке. На рисунке 6 вершин.

г) Считаем количество концевых вершин у графа, изображённого на рисунке. Концевые вершины - это вершины степени 1. На рисунке 3 концевые вершины.

Ответ: а) Нет, б) 7, в) 6, г) 3

Проверка за 10 секунд: Быстро проверьте наличие циклов и пересчитайте вершины и рёбра.

Доп. профит (Уровень Эксперт): Граф является деревом, если он связный и не содержит циклов.

4. Рёбра дерева

Количество вершин дерева равно 31. Какое наибольшее число рёбер может иметь это дерево? В дереве число рёбер всегда на 1 меньше числа вершин. Значит, число рёбер = 31 - 1 = 30.

Ответ: 30

Проверка за 10 секунд: Запомните, что в дереве всегда V = E + 1, где V - вершины, E - рёбра.

Доп. профит (База): В дереве между любыми двумя вершинами существует ровно один путь.

5. Грядки с тюльпанами

В агрокомплексе «Цветочный» есть 140 грядок с тюльпанами. Каждые две грядки соединяет ровно одна дорожка. Определите количество дорожек, соединяющих грядки с тюльпанами. Это задача на полный граф, где каждая вершина соединена со всеми остальными. Количество рёбер (дорожек) в полном графе с n вершинами вычисляется по формуле: E = n * (n - 1) / 2. В нашем случае n = 140. E = 140 * (140 - 1) / 2 = 140 * 139 / 2 = 70 * 139 = 9730.

Ответ: 9730

Проверка за 10 секунд: Используйте формулу n * (n - 1) / 2 для полных графов.

Доп. профит (Уровень Эксперт): Полный граф - это граф, где каждая вершина соединена со всеми остальными.

6. Существование дерева

а) Количество вершин 8, а рёбер 20. Не существует, так как в дереве с 8 вершинами должно быть 7 рёбер.

б) Количество вершин 54, а рёбер 53. Существует, так как выполняется условие: рёбер = вершины - 1.

в) Количество вершин 26, а рёбер 27. Не существует, так как в дереве с 26 вершинами должно быть 25 рёбер.

Ответ: а) Нет, б) Да, в) Нет

Проверка за 10 секунд: Сравните количество рёбер и вершин: E = V - 1.

Редфлаг: Если количество рёбер не соответствует количеству вершин минус один, то такого дерева не существует.

7. Построение дерева

Постройте дерево, в котором 12 вершин, причем 3 вершины имеют степень 1, 2 вершины степени 2, 2 вершины степени 3.

Для построения такого дерева, можно начать с 2 вершин степени 3, соединить их. Потом добавить 2 вершины степени 2, и закончить 3 вершинами степени 1.

Ответ: Описание построения выше.

Проверка за 10 секунд: Проверьте, чтобы сумма степеней всех вершин была равна удвоенному числу рёбер.

Доп. профит (База): Сумма степеней всех вершин в графе всегда чётная.