В некотором графе 5 вершин степени которых равны 9;6;2;16;1 сколько в этом графе рёбер

Давайте воспользоваться принципом рукопожатий: в любом графе сумма степеней вершин равна удвоенному числу рёбер. - Сумма данных степеней: 9 + 6 + 2 + 16 + 1 = 34. - Значит количество рёбер: |E| = 34 / 2 = 17. Важно отметить следующее: - В простом графе с 5 вершинами максимальная степень вершины не может превышать 4 (соединения с остальными 4 вершинами). Здесь встречаются степени 9, 16 и т.д., что невозможно для простого графа. - Поэтому такое распределение степеней возможно только в многографе (с параллельными ребрами). Пример реализации в мультграфе без петель: - Пусть вершины обозначим A, B, C, D, E, где D имеет степень 16. - Соединяем D с A двадцатью? Нет: чтобы достичь точной схемы, используем параллельные рёбра: - 9 параллельных рёбер между D и A (вносит A:9, D:9) - 6 параллельных рёбер между D и B (A:9, D:15; B:6, D:15+1) - 1 параллельное ребро между D и C (C:1, D:16) - 1 ребро между C и E (C:2, E:1) - Итог: A:9, B:6, C:2, D:16, E:1. Всего рёбер = 9 + 6 + 1 (D–C) + 1 (C–E) = 17. Итого: граф с такими степенями может существовать, но только как мультграф. В простом графе такой набор степеней не realizуем. Ответ на вопрос о количестве рёбер: 17.