В1. Выполните задания по рисунку: а) Найдите путь (не простой) графа. б) Найдите цикл (не простой) графа. в) Найдите наименьшую степень графа.

1. Анализируем граф:

У нас есть граф с вершинами, пронумерованными от 1 до 7. Ребра соединяют следующие пары вершин:

• (1, 2)
• (1, 3)
• (1, 4)
• (1, 6)
• (2, 3)
• (2, 6)
• (3, 5)
• (4, 5)
• (4, 7)
• (5, 6)

а) Найдите путь (не простой) графа.

Простой путь не должен содержать повторяющихся вершин. Непростой путь может содержать повторяющиеся вершины.

Пример непростого пути: 1 → 2 → 3 → 1 → 4 → 5

б) Найдите цикл (не простой) графа.

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

Пример непростого цикла: 1 → 2 → 6 → 5 → 3 → 1

в) Найдите наименьшую степень графа.

Степень вершины – это количество ребер, исходящих из нее. Найдем степень каждой вершины:

• Степень вершины 1: 4 (ребра к 2, 3, 4, 6)
• Степень вершины 2: 3 (ребра к 1, 3, 6)
• Степень вершины 3: 3 (ребра к 1, 2, 5)
• Степень вершины 4: 3 (ребра к 1, 5, 7)
• Степень вершины 5: 3 (ребра к 3, 4, 6)
• Степень вершины 6: 3 (ребра к 1, 2, 5)
• Степень вершины 7: 1 (ребро к 4)

Наименьшая степень среди всех вершин – это степень вершины 7, которая равна 1.

Ответ:

а) Пример непростого пути: 1 → 2 → 3 → 1 → 4 → 5

б) Пример непростого цикла: 1 → 2 → 6 → 5 → 3 → 1

в) Наименьшая степень графа равна 1 (вершина 7).