Реши
- Выполните задания по рисунку:
а) Найдите цикл (не простой) графа.
Цикл в графе — это путь, который начинается и заканчивается в одной и той же вершине. Не простой цикл может проходить через вершины более одного раза. На графе можно найти цикл следующим образом:
Например, цикл: 1 → 2 → 3 → 4 → 5 → 1. Здесь, начиная с вершины 1, мы возвращаемся обратно к ней через указанные вершины.
б) Найдите путь (не простой) графа.
Не простой путь — это цепочка вершин, в которой вершины или рёбра могут повторяться. Пример такого пути: 1 → 2 → 5 → 4 → 3 → 2. Здесь мы можем повторять посещение некоторых вершин, таких как вершину 2.
в) Найдите наименьшую степень графа.
Степень вершины — это количество рёбер, входящих в неё или исходящих из неё. Проверим степени всех вершин:
- Вершина 1: степень 2 (рёбра 1-2 и 1-5).
- Вершина 2: степень 3 (рёбра 2-1, 2-3, и 2-5).
- Вершина 3: степень 2 (рёбра 3-2 и 3-4).
- Вершина 4: степень 2 (рёбра 4-3 и 4-5).
- Вершина 5: степень 3 (рёбра 5-1, 5-2, и 5-4).
Наименьшая степень — 2 у вершин 1, 3 и 4.
- У Лины есть 9 пятиручек игрушек-монстров. Может ли она соединить их за руки так, чтобы свободных рук не осталось? Ответ обоснуйте.
Каждый монстр имеет по 5 рук. Если у нас 9 монстров, суммарное количество рук будет \( 9 \times 5 = 45 \).
Чтобы покрыть все руки парным соединением (по 2 руки), число рук должно быть чётным. Поиск: 45 — нечётное число, следовательно, у Лины не получится соединить всех монстров попарно так, чтобы не осталось свободных рук. Всегда останется одна не соединённая рука.
