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

Решение:

а) Является ли граф связным?

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

б) Укажите какой-нибудь цикл (не простой) графа.

Цикл — это путь, который начинается и заканчивается в одной и той же вершине, проходя через другие вершины.

Примеры циклов:

• 1 – 2 – 3 – 1
• 1 – 2 – 6 – 5 – 1
• 1 – 2 – 6 – 7 – 4 – 5 – 1

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

Степень вершины — это количество ребер, выходящих из нее.

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

Наименьшая степень вершины равна 2.

Ответ: а) Да, граф связный. б) 1-2-3-1. в) 2