Фамилия Икся Салдесев Алмеркласс ПА Дата 16.03.26 Степень (валентность) вершины. Число рёбер и суммарная степень вершин. Цепь и цикл. Задание 1. На рисунке изображен граф. Определи степень каждой вершины Задание 2. Используя граф из задания 1. Выполни задания 1. Сколько всего ребер в графе? 2. Вычисли сумму степеней всех вершин. 3. Проверь, выполняется ли теорема о сумме степеней (Сумма степеней = 2 * Число ребер). Выполняется / Не выполняется Задание 3. В графе 5 вершин. Степени четырех вершин равны 1, 2, 3 и 4. Найди степень пятой вершины Задание 4. Для графа из задания 1. Приведи пример цепи. Приведи пример цикла Задание 5. Отметь, какие утверждения верны, а какие ложны Задание 6. Можно ли построить граф с 6 вершинами, степени которых равны: 1, 1, 2, 2, 3, 5? Объясни свой ответ

Ответ:

Задание 1

• Степень вершины A: 3
• Степень вершины B: 3
• Степень вершины C: 2
• Степень вершины D: 3
• Степень вершины E: 3
• Степень вершины F: 2

Задание 2

1. Количество ребер в графе: 6
2. Сумма степеней всех вершин: 16
3. Проверка теоремы о сумме степеней: 3 + 3 + 2 + 3 + 3 + 2 = 16. 2 * (количество ребер) = 2 * 6 = 12 ≠ 16. Теорема не выполняется.

Задание 3

\[1 + 2 + 3 + 4 + x = 2 \cdot \text{количество ребер}\]

Пусть x - степень пятой вершины. Сумма степеней всех вершин должна быть четной, чтобы существовал граф.

\[1 + 2 + 3 + 4 + x = 2k\]

\[10 + x = 2k\]

Чтобы сумма была четной, x должно быть четным числом. Минимальное четное число - 0, но степень вершины не может быть 0, так как в графе есть другие вершины.

По условию в графе 5 вершин, значит максимальная степень любой вершины 4.

Если x = 2, то \[1 + 2 + 3 + 4 + 2 = 12\]

Сумма степеней всех вершин: 1 + 2 + 3 + 4 + x = 12

Количество ребер: 12 / 2 = 6

Степень пятой вершины: 2

Задание 4

• Пример цепи, начинающейся в вершине A и заканчивающейся в вершине F: A-C-D-E-F
• Пример цикла, содержащего вершину B: B-F-E-B

Задание 5

• Граф, в котором все вершины имеют степень 2, всегда содержит цикл. - Верно.
• Если сумма степеней всех вершин графа нечетная, то в графе есть ошибка (неправильно посчитаны степени). - Верно.
• В графе может быть вершина, степень которой равна количеству вершин в графе. - Неверно.

Задание 6

Сумма степеней всех вершин: 1 + 1 + 2 + 2 + 3 + 5 = 14.

Количество вершин: 6.

В графе с 6 вершинами не может быть вершины со степенью 5, так как максимальная степень вершины в графе равна числу вершин минус 1.

Да, можно построить такой граф, так как сумма степеней четная.

Ответ: