Вопрос:

Нарисуйте какой-либо граф, в котором 5 вершин со степенями 1, 2, 2, 3, 3. В некотором графе 6 вершин, степени которых равны: а) 2, 2, 3, 3, 4, 4; б) 0, 1, 2, 2, 3, 4. Сколько всего рёбер в этом графе?

Фотография

Ответ ассистента

1. Чтобы нарисовать граф с вершинами степеней 1, 2, 2, 3, 3, можно соединить их следующим образом: - Пусть вершины будут A, B, C, D, E. - Вершина A (степень 3): соединена с B, C, D. - Вершина B (степень 3): соединена с A, C, E. - Вершина C (степень 2): соединена с A, B. - Вершина D (степень 2): соединена с A, E. - Вершина E (степень 1): соединена с D. 2. Количество рёбер в графе равно половине суммы степеней всех его вершин (согласно лемме о рукопожатиях). а) Сумма степеней: $2 + 2 + 3 + 3 + 4 + 4 = 18$ Количество рёбер: $18 / 2 = 9$ **Ответ: 9** б) Сумма степеней: $0 + 1 + 2 + 2 + 3 + 4 = 12$ Количество рёбер: $12 / 2 = 6$ **Ответ: 6**

Похожие задачи

Посмотри похожие решения — вдруг одно из них подойдёт тебе

Другие решения

Что ещё задавали пользователи