Урок 21. Самостоятельная работа Вариант 1 1. Нарисуйте граф, где вершинами будут числа от 1 до 6, а рёбра будут идти от числа к делителям. Какова входящая степень у числа 1? Какова входящая степень у числа 3? 2. Напишите эйлеров путь для графа. 3. В некоторой стране 50 городов, из которых выходит по две дороги, и 60 городов, из которых выходит по три дороги. Дорога всегда соединяет два города. Сколько всего дорог в стране? 4. Рассмотрим граф, вершины которого соответствуют натуральным числам от 1 до 12. Две вершины в нашем графе будут соединены ребром тогда и только тогда, когда разность соответствующих чисел делится на 3. Изобразите описанный граф. Будет ли граф связным? Если нет, то сколько в нём компонент связности?

Question

Вопрос:

Урок 21. Самостоятельная работа Вариант 1 1. Нарисуйте граф, где вершинами будут числа от 1 до 6, а рёбра будут идти от числа к делителям. Какова входящая степень у числа 1? Какова входящая степень у числа 3? 2. Напишите эйлеров путь для графа. 3. В некоторой стране 50 городов, из которых выходит по две дороги, и 60 городов, из которых выходит по три дороги. Дорога всегда соединяет два города. Сколько всего дорог в стране? 4. Рассмотрим граф, вершины которого соответствуют натуральным числам от 1 до 12. Две вершины в нашем графе будут соединены ребром тогда и только тогда, когда разность соответствующих чисел делится на 3. Изобразите описанный граф. Будет ли граф связным? Если нет, то сколько в нём компонент связности?

Смотреть решения всех заданий с листа

Ответ:

ГДЗ по фото 📸

Accepted Answer

Решение варианта 1

1. Граф с вершинами от 1 до 6 и ребрами к делителям

Краткое пояснение: Рисуем граф, где вершины - числа от 1 до 6, а ребра идут от числа к его делителям. Считаем входящие степени вершин 1 и 3.

Для построения графа определим делители для каждого числа от 1 до 6:

1: нет делителей, кроме самого себя
2: 1
3: 1
4: 1, 2
5: 1
6: 1, 2, 3

Теперь нарисуем граф, где вершины - числа от 1 до 6, и ребра идут от числа к его делителям.

Входящая степень вершины - это количество ребер, входящих в эту вершину.

Входящая степень вершины 1: 5 (2 → 1, 3 → 1, 4 → 1, 5 → 1, 6 → 1)
Входящая степень вершины 3: 1 (6 → 3)

2. Эйлеров путь для графа

Краткое пояснение: Эйлеров путь - это путь, который проходит по каждому ребру графа ровно один раз.

Эйлеров путь для данного графа: 2-1-5-4-3-2

3. Задача про города и дороги

Краткое пояснение: Используем формулу для нахождения общего количества дорог, учитывая количество городов с двумя и тремя дорогами.

Пусть x - количество городов, из которых выходит по две дороги (50 городов), а y - количество городов, из которых выходит по три дороги (60 городов).

Тогда общее количество дорог можно найти по формуле:

\[\frac{2x + 3y}{2}\]

Подставим значения x и y:

\[\frac{2 \cdot 50 + 3 \cdot 60}{2} = \frac{100 + 180}{2} = \frac{280}{2} = 140\]

Всего в стране 140 дорог.

4. Граф с вершинами от 1 до 12, соединенными ребрами, если разность делится на 3

Краткое пояснение: Строим граф, где вершины - числа от 1 до 12. Соединяем вершины ребром, если разность чисел делится на 3. Проверяем связность графа и количество компонент связности.

Вершины графа: числа от 1 до 12.

Ребро между вершинами a и b существует, если |a - b| делится на 3.

Рассмотрим, какие вершины будут соединены:

1: 4, 7, 10
2: 5, 8, 11
3: 6, 9, 12
4: 1, 7, 10
5: 2, 8, 11
6: 3, 9, 12
7: 1, 4, 10
8: 2, 5, 11
9: 3, 6, 12
10: 1, 4, 7
11: 2, 5, 8
12: 3, 6, 9

Граф будет состоять из следующих компонент связности:

1, 4, 7, 10
2, 5, 8, 11
3, 6, 9, 12

Граф не является связным, так как существует несколько компонент связности. В графе 3 компоненты связности.

Проверка за 10 секунд:

Входящая степень 1: 5, входящая степень 3: 1
Эйлеров путь: 2-1-5-4-3-2
Всего дорог: 140
Граф не связный, 3 компоненты связности

Доп. профит: База

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