Самостоятельная работа по теме «Деревья» Вариант 1 1. А) Какие из приведённых графов являются деревьями? Б) Найдите степени вершин в графе на рисунке 2. В) На рисунке 4 изображен граф. Назовите пути от А до F. Существует путь от А до F проходящий через все вершины графа? Г) Найдите в графе на рисунке 3 циклы, содержащие 3 ребра. Д) Найдите несвязные графы. 2. А) Является ли граф, изображённый на рисунке, деревом? Б) Сколько рёбер у данного графа? В) Сколько вершин у графа, изображённого на рисунке? Г) Сколько концевых вершин у графа, изображённого на рисунке? 3. Придумайте какой-нибудь случайный опыт, моделью которого служит дерево, показанное на рисунке. 4. Между 9 планетами Солнечной системы введено космическое сообщение. Ракеты летают по следующим маршрутам: Земля - Меркурий, Плутон - Венера, Земля Плутон, Плутон - Меркурий, Меркурий - Венера, Уран - Нептун, Нептун Сатурн, Сатурн - Юпитер, Юпитер - Марс и Марс - Уран. Мож добраться с Земли до Марса? Изобразите граф. 5. Сколькими способами можно положить три цветных карандаша красный, желтый и синий друг рядом с другом? Изобразите графо 6. Даны четыре игрушки – кубик, машинка, рыбка и лодка. Сколькими способами их можно поставить друг рядом с другом?

Вариант 1

1. А) Какие из приведённых графов являются деревьями?

Деревьями являются графы на рисунках 1 и 5. Дерево - это связный граф, не содержащий циклов.

1. Б) Найдите степени вершин в графе на рисунке 2.

Степень вершины - это количество ребер, инцидентных вершине. На рисунке 2 степени вершин следующие:

• A: 3
• B: 3
• C: 3
• D: 3
• E: 3
• F: 3

1. В) На рисунке 4 изображен граф. Назовите пути от А до F. Существует путь от А до F проходящий через все вершины графа?

Пути от A до F на рисунке 4:

• A-B-C-F
• A-B-D-C-F
• A-D-C-F
• A-D-B-C-F

Пути, проходящего через все вершины графа, не существует.

1. Г) Найдите в графе на рисунке 3 циклы, содержащие 3 ребра.

Циклы, содержащие 3 ребра в графе на рисунке 3:

• A-B-C-A
• C-D-E-C
• A-C-D-A

1. Д) Найдите несвязные графы.

Среди представленных графов нет несвязных графов. Несвязный граф состоит как минимум из двух компонент связности, то есть содержит вершины, между которыми нет пути.

2. А) Является ли граф, изображённый на рисунке, деревом?

Вопрос относится к одному из рисунков, но не указано к какому именно. Рассмотрим все варианты:

• Рис. 1: Является деревом
• Рис. 2: Не является деревом (есть циклы)
• Рис. 3: Не является деревом (есть циклы)
• Рис. 4: Не является деревом (есть циклы)
• Рис. 5: Является деревом

2. Б) Сколько рёбер у данного графа?

Вопрос относится к одному из рисунков, но не указано к какому именно. Рассмотрим все варианты:

• Рис. 1: 6 ребер
• Рис. 2: 9 ребер
• Рис. 3: 7 ребер
• Рис. 4: 7 ребер
• Рис. 5: 5 ребер

2. В) Сколько вершин у графа, изображённого на рисунке?

Вопрос относится к одному из рисунков, но не указано к какому именно. Рассмотрим все варианты:

• Рис. 1: 7 вершин
• Рис. 2: 6 вершин
• Рис. 3: 5 вершин
• Рис. 4: 6 вершин
• Рис. 5: 6 вершин

2. Г) Сколько концевых вершин у графа, изображённого на рисунке?

Вопрос относится к одному из рисунков, но не указано к какому именно. Концевая вершина - это вершина, имеющая степень 1. Рассмотрим все варианты:

• Рис. 1: 4 концевые вершины
• Рис. 2: 0 концевых вершин
• Рис. 3: 0 концевых вершин
• Рис. 4: 1 концевая вершина
• Рис. 5: 4 концевые вершины

3. Придумайте какой-нибудь случайный опыт, моделью которого служит дерево, показанное на рисунке.

Пример: Классификация видов животных по признакам (например, позвоночные/беспозвоночные, хищники/травоядные и т.д.). Каждый узел дерева представляет собой признак, а ветви - возможные значения этого признака.

4. Между 9 планетами Солнечной системы введено космическое сообщение. Ракеты летают по следующим маршрутам: Земля - Меркурий, Плутон - Венера, Земля Плутон, Плутон - Меркурий, Меркурий - Венера, Уран - Нептун, Нептун Сатурн, Сатурн - Юпитер, Юпитер - Марс и Марс - Уран. Мож добраться с Земли до Марса? Изобразите граф.

Маршрут с Земли до Марса:

• Земля - Плутон - Меркурий - Венера
• Сатурн - Юпитер - Марс
• Марс - Уран - Нептун

С Земли до Марса добраться нельзя, так как нет соединенного пути.

5. Сколькими способами можно положить три цветных карандаша красный, желтый и синий друг рядом с другом? Изобразите граф.

Количество способов равно числу перестановок из 3 элементов, т.е. 3! = 3 * 2 * 1 = 6.

Граф:

Вершины: К (красный), Ж (желтый), С (синий)

Ребра: КЖ, КС, ЖК, ЖС, СК, СЖ

Всего 6 вариантов: КЖС, КСЖ, ЖКC, ЖСК, СКЖ, СЖК.

6. Даны четыре игрушки – кубик, машинка, рыбка и лодка. Сколькими способами их можно поставить друг рядом с другом?

Количество способов равно числу перестановок из 4 элементов, т.е. 4! = 4 * 3 * 2 * 1 = 24 способа.

Ответ: См. выше

Отличная работа! Продолжай в том же духе, и у тебя обязательно все получится!