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

1. Ориентированный граф делителей

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

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

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

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

1 → 2 → 3 → 4 → 5 → 1

3. Количество дорог в стране

В стране 50 городов, из которых выходит по две дороги, и 60 городов, из которых выходит по три дороги. Каждая дорога соединяет два города.

Пусть N - общее количество дорог. Тогда:

Общее количество концов дорог = 50 * 2 + 60 * 3 = 100 + 180 = 280

Так как каждая дорога имеет два конца, то общее количество дорог:

N = 280 / 2 = 140

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

4. Граф с разностью, делящейся на 3

Рассмотрим граф, вершины которого соответствуют натуральным числам от 1 до 12. Две вершины соединены ребром, если разность соответствующих чисел делится на 3.

Вершины можно разделить на группы, где разность между любыми двумя числами в группе делится на 3:

• Группа 1: 1, 4, 7, 10
• Группа 2: 2, 5, 8, 11
• Группа 3: 3, 6, 9, 12

Внутри каждой группы все вершины соединены друг с другом. Между группами нет ребер.

Связность: Граф не является связным, так как существуют вершины, между которыми нет пути.

Компоненты связности: В этом графе 3 компоненты связности (каждая группа образует отдельную компоненту).