Решение самостоятельной работы по теме «Деревья», Вариант 2

Хорошо, давайте разберем каждое задание по порядку. Самостоятельная работа по теме «Деревья» Вариант 2 1. А) Какие из приведённых графов являются деревьями? Б) Найдите степени вершин в графе на рисунке 2. В) На рисунке 4 изображен граф. Назовите путь от А до F. Существует путь от А до F проходящий через все вершины графа? Г) Найдите в графе на рисунке 3 циклы, содержащие 3 ребра. Д) Найдите несвязные графы. Решение: А) Граф является деревом, если он связный и не содержит циклов. * Рис. 1: Связный, не содержит циклов. Это дерево. * Рис. 2: Содержит циклы (например, A-B-C-D-A). Это не дерево. * Рис. 3: Содержит циклы (например, A-B-C-D-A). Это не дерево. * Рис. 4: Содержит циклы (например, A-B-C-A). Это не дерево. * Рис. 5: Связный, не содержит циклов. Это дерево. Ответ: Деревьями являются графы на рисунках 1 и 5. Б) Степени вершин в графе на рисунке 2: * Вершина A: соединена с B, D. Степень = 2. * Вершина B: соединена с A, C. Степень = 2. * Вершина C: соединена с B, D. Степень = 2. * Вершина D: соединена с A, C. Степень = 2. Ответ: Степени вершин: A=2, B=2, C=2, D=2. В) На рисунке 4 изображен граф. Назовите путь от А до F. Существует путь от А до F проходящий через все вершины графа? * Путь от А до F: A-B-F или A-C-F. * Вершины графа на рисунке 4: A, B, C, D, F, K. * Попробуем найти путь, проходящий через все вершины: * A-B-C-D-K-F (не проходит через все вершины, K не связана с F) * A-C-B-D-K-F (не проходит через все вершины) * A-B-D-C-F (не проходит через все вершины) * A-C-D-B-F (не проходит через все вершины) * Граф на рисунке 4 не является гамильтоновым, то есть не существует простого пути, проходящего через все вершины. Ответ: Путь от А до F: A-B-F или A-C-F. Нет, не существует пути от А до F, проходящего через все вершины графа. Г) Найдите в графе на рисунке 3 циклы, содержащие 3 ребра. * Граф на рисунке 3 имеет вершины A, B, C, D, E. * Цикл из 3 ребер (треугольник): * A-B-D-A * B-C-D-B Ответ: Циклы, содержащие 3 ребра: A-B-D-A и B-C-D-B. Д) Найдите несвязные графы. * Несвязный граф состоит из нескольких компонент связности. * Все графы на рисунках 1, 2, 3, 4, 5 являются связными. Ответ: Среди представленных графов нет несвязных. 2. А) Является ли граф, изображённый на рисунке, деревом? Б) Сколько рёбер у данного графа? В) Сколько вершин у графа, изображённого на рисунке? Г) Сколько концевых вершин у графа, изображённого на рисунке? Решение: Рассмотрим граф, изображенный под заданием 1.Д. (верхний из двух графов). А) Граф связный и не содержит циклов. Ответ: Да, является деревом. Б) Посчитаем рёбра: * Верхняя левая часть: 3 ребра. * Центральная часть: 2 ребра. * Правая часть: 1 ребро. * Всего: \(3 + 2 + 1 = 6\) ребер. Ответ: 6 рёбер. В) Посчитаем вершины: * Верхняя левая часть: 4 вершины. * Центральная часть: 2 вершины (уже посчитаны). * Правая часть: 2 вершины. * Всего: 7 вершин. Ответ: 7 вершин. Г) Концевые вершины (листья) – это вершины степени 1. * В левой части: 2 вершины степени 1. * В правой части: 1 вершина степени 1. * Всего: \(2 + 1 = 3\) концевые вершины. Ответ: 3 концевые вершины. 3. Придумайте какой-нибудь случайный опыт, моделью которого служит дерево, показанное на рисунке. Решение: Рассмотрим дерево, изображенное под заданием 2.Г. (нижний из двух графов). Это дерево с одной корневой вершиной и множеством ветвей, каждая из которых имеет несколько листьев. Пример случайного опыта: Представьте, что вы выбираете блюдо в ресторане. * Корневая вершина – это выбор категории блюда (например, "Основное блюдо"). * Первый уровень ветвей – это подкатегории (например, "Мясные блюда", "Рыбные блюда", "Вегетарианские блюда"). * Второй уровень ветвей – это конкретные блюда в каждой подкатегории (например, для "Мясных блюд" – "Стейк", "Котлеты", "Гуляш"). * Листья – это различные варианты приготовления или гарнира к каждому блюду (например, для "Стейка" – "С кровью", "Средней прожарки", "Хорошо прожаренный", или "С картофелем", "С рисом", "С овощами"). Каждый путь от корня до листа представляет собой один из возможных вариантов выбора блюда с его характеристиками. Ответ: Выбор блюда в ресторане. Корневая вершина – выбор категории блюда. Ветви – подкатегории и конкретные блюда. Листья – варианты приготовления или гарнира. 4. Между 9 планетами Солнечной системы введено космическое сообщение. Ракеты летают по следующим маршрутам: Земля-Меркурий, Плутон-Венера, Земля-Плутон, Плутон-Меркурий, Меркурий-Венера, Уран-Нептун, Нептун-Сатурн, Сатурн-Юпитер, Юпитер-Марс и Марс-Уран. Можно ли добраться с Земли до Марса? Изобразите граф. Решение: Сначала перечислим все планеты (вершины графа): Земля, Меркурий, Плутон, Венера, Уран, Нептун, Сатурн, Юпитер, Марс. Всего 9 планет. Теперь построим граф по заданным маршрутам (рёбрам): * Земля - Меркурий * Плутон - Венера * Земля - Плутон * Плутон - Меркурий * Меркурий - Венера * Уран - Нептун * Нептун - Сатурн * Сатурн - Юпитер * Юпитер - Марс * Марс - Уран Изобразим граф: (Представьте, что это рисунок графа, где кружочки - планеты, а линии - маршруты) Земля --- Меркурий --- Венера --- Плутон --- Земля | / | / | / | / | / | / | / | / | / | / |/ Плутон Уран --- Нептун --- Сатурн --- Юпитер --- Марс --- Уран Теперь проверим, можно ли добраться с Земли до Марса. Рассмотрим компоненты связности: * Первая компонента: Земля, Меркурий, Плутон, Венера. * Земля связана с Меркурием и Плутоном. * Меркурий связан с Землей, Плутоном и Венерой. * Плутон связан с Землей, Меркурием и Венерой. * Венера связана с Плутоном и Меркурием. * Вторая компонента: Уран, Нептун, Сатурн, Юпитер, Марс. * Уран связан с Нептуном и Марсом. * Нептун связан с Ураном и Сатурном. * Сатурн связан с Нептуном и Юпитером. * Юпитер связан с Сатурном и Марсом. * Марс связан с Юпитером и Ураном. Эти две компоненты связности не соединены между собой. Земля находится в первой компоненте, а Марс – во второй. Ответ: Нет, нельзя добраться с Земли до Марса, так как эти планеты находятся в разных несвязных частях графа. (Для школьника можно нарисовать граф, например, так: Вершины: З, М, П, В, У, Н, С, Ю, Р (Марс) Ребра: З-М П-В З-П П-М М-В У-Н Н-С С-Ю Ю-Р Р-У Видно, что {З, М, П, В} образуют одну связную часть, а {У, Н, С, Ю, Р} – другую. Между этими частями нет ребер.) 5. Сколько трёхзначных чисел можно составить из цифр 2, 6, 8 при условии, что цифры в записи повторяться не будут? Изобразите граф. Решение: У нас есть 3 цифры: 2, 6, 8. Мы хотим составить трёхзначные числа, где цифры не повторяются. Это задача на перестановки. Количество перестановок из \(n\) элементов равно \(n!\). В нашем случае \(n = 3\). Количество чисел = \(3! = 3 \times 2 \times 1 = 6\). Перечислим все возможные числа: * 268 * 286 * 628 * 682 * 826 * 862 Изобразим граф (можно использовать дерево решений): * Корень – начало выбора. * Первый уровень – выбор первой цифры (2, 6, 8). * Второй уровень – выбор второй цифры (из оставшихся двух). * Третий уровень – выбор третьей цифры (оставшаяся одна). (Представьте, что это дерево, где от корня идут 3 ветви, от каждой из них по 2, и от каждой из них по 1) Начало / | \ 2 6 8 / \ / \ / \ 6 8 2 8 2 6 | | | | | | 8 6 8 2 6 2 Каждый путь от корня до листа представляет собой одно трёхзначное число. Ответ: Можно составить 6 трёхзначных чисел. Граф изображен выше. 6. На острове Ро-ко-ко живет племя, которое использует только три буквы – А, Б, В. В словах они могут повторяться не более двух раз каждая. Сколько различных слов у жителей этого острова, если все их слова трехбуквенные? Решение: У нас есть 3 буквы: А, Б, В. Слова трехбуквенные. Каждая буква может повторяться не более двух раз. Рассмотрим возможные комбинации букв в трехбуквенном слове: Случай 1: Все буквы разные. Это перестановки из 3 букв: АБВ, АВБ, БАВ, БВА, ВАБ, ВБА. Количество: \(3! = 6\). (Здесь каждая буква встречается 1 раз, что удовлетворяет условию "не более двух раз") Случай 2: Две буквы одинаковые, одна другая. Выбираем букву, которая будет повторяться (3 варианта: А, Б, В). Выбираем позицию для другой буквы (3 варианта). Выбираем другую букву (2 варианта). Например, если повторяется А: ААБ, АБА, БАА. Если повторяется Б: ББА, БАБ, АББ. Если повторяется В: ВВА, ВАВ, АВВ. Формула для перестановок с повторениями: У нас есть 3 позиции. Выбираем букву, которая будет повторяться 2 раза (например, А). Остается 1 позиция для другой буквы. Выбираем другую букву (например, Б). Теперь у нас есть буквы А, А, Б. Количество перестановок: \(\frac{3!}{2!1!} = \frac{6}{2} = 3\). Таких пар букв (ААБ, ББВ, ВВА) у нас 3 (выбор повторяющейся буквы) * 2 (выбор другой буквы) = 6 комбинаций букв. Например: * ААБ: ААБ, АБА, БАА (3 слова) * ААВ: ААВ, АВА, ВАА (3 слова) * ББА: ББА, БАБ, АББ (3 слова) * ББВ: ББВ, БВБ, ВББ (3 слова) * ВВА: ВВА, ВАВ, АВВ (3 слова) * ВВБ: ВВБ, ВБВ, БВВ (3 слова) Всего: \(6 \times 3 = 18\) слов. Случай 3: Все три буквы одинаковые. Например, ААА, БББ, ВВВ. Количество: 3 слова. (Здесь каждая буква встречается 3 раза, что *не* удовлетворяет условию "не более двух раз"). Значит, этот случай исключается. Итого, общее количество слов: Слова с разными буквами: 6 Слова с двумя одинаковыми буквами: 18 Слова с тремя одинаковыми буквами: 0 (так как каждая буква может повторяться не более двух раз) Общее количество слов = \(6 + 18 = 24\). Ответ: Всего 24 различных слова.