Урок 23. Граф, вершина, ребро. Представление задачи с помощью графа. Дата: Граф Задание 1 Укажи стрелками на рисунке вершины, изолированные вершины, рёбра график Вершина Приведи примеры графов B F Изолированная веригина K Ребро Задание 2. На рисунке изображены графы. Сколько у каждого из них ребер, вершин, изолированных вершин? a) 6) Рисунок «а» Рисунок «б» Вершины Изолированные вершины Ребра Задание 3. В новом коттеджном посёлке 7 домиков. Они уже стоят, а дорожки ещё предстоит проложить. Есть три плана их прокладки. Нужно выбрать такой, при котором бульдозер сможет расчистить все дорожки, проходя по каждой по одному разу. При этом он должен вернуться в начальную точку.

Задание 1

В графе вершины - это точки, а ребра - это линии, соединяющие вершины. Изолированная вершина - это вершина, не соединенная ни с какими другими вершинами.

Примеры графов:

• Полный граф: каждая вершина соединена со всеми остальными.
• Дерево: граф без циклов.
• Список: вершины соединены в линию.

Задание 2

Рисунок «а»

• Вершины: 4
• Изолированные вершины: 0
• Ребра: 4

Рисунок «б»

• Вершины: 3
• Изолированные вершины: 0
• Ребра: 3

Задание 3

Чтобы бульдозер смог проехать по каждой дорожке ровно один раз и вернуться в начальную точку, граф должен быть эйлеровым. Эйлеров граф - это граф, в котором все вершины имеют четную степень (то есть, из каждой вершины выходит четное число ребер).

Нужно выбрать такой план прокладки дорожек, чтобы в графе, представляющем этот план, все вершины имели четную степень.

Проверь, чтобы все вершины имели четную степень.

Редфлаг: Если хоть одна вершина имеет нечетную степень, это плохой план.