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

Решение:

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

Граф называется связным, если между любыми двумя его вершинами существует хотя бы один путь. В данном графе из любой вершины можно добраться до любой другой. Например, из вершины 2 можно попасть в 1, а из 1 — в 3, 4, 5. Следовательно, граф связный.

Ответ: Да, граф связный.

б) Укажите какую-нибудь цепь графа.

Цепь — это последовательность вершин, соединенных ребрами. Например:

1 → 3 → 4

Другие примеры цепей:

• 2 → 1 → 5
• 3 → 1 → 2 → 5

Ответ: 1 → 3 → 4 (или любая другая допустимая цепь).

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

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

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

Сумма степеней всех вершин:

\( 3 + 1 + 2 + 1 + 1 = 8 \)

По теореме о сумме степеней, эта сумма равна удвоенному числу ребер. В графе 4 ребра (1-2, 1-3, 1-5, 3-4). \( 4 \times 2 = 8 \).

Ответ: 8.