Постройте Граф в котором Семь вершин степени которых равны соответственно: 1 2 2 2 4 4 5

Задача выполнима. Используем метод Хавель-Хакки (постепенно строим граф, снимая вершину с наибольшей степенью и уменьшая степени соседей). Исходная последовательность степеней (неупорядоченная): 1, 2, 2, 2, 4, 4, 5 Проверка: сумма степеней = 20 (четно), не превышает максимально возможную сумму для 7 вершин, последовательность графическая. Далее конкретное построение. Шаг 1. Возьмём вершину A с степенью 5 и соединим её с пятью вершинами с наибольшими степенями (B, C, D, E, F). - Ребра: A-B, A-C, A-D, A-E, A-F - Обновляем степени остальных вершин: B→3, C→3, D→1, E→1, F→1, G остаётся 1. - Оставшиеся вершины: B(3), C(3), D(1), E(1), F(1), G(1). Шаг 2. В оставшихся вершинах возьмём вершину B с степенью 3 и соединим её с тремя вершинами с наибольшими степенями: C, D, E. - Ребра: B-C, B-D, B-E - Обновляем степени: C→2, D→0, E→0. Вершина G остаётся 1. - Оставшиеся вершины: C(2), F(1), G(1), D(0), E(0). Шаг 3. В оставшихся вершинах возьмём вершину C с степенью 2 и соединим её с двумя вершинами с наибольшими степенями: F и G. - Ребра: C-F, C-G - Обновляем степени: F→0, G→0. Остальные вершины имеют нулевые степени. Получаем конкретное построение графа (вершины помечены A…G соответствуя шагам): - Ребра: A-B, A-C, A-D, A-E, A-F, B-C, B-D, B-E, C-F, C-G Эквивалентно, adj-списки: - A: B, C, D, E, F - B: A, C, D, E - C: A, B, F, G - D: A, B - E: A, B - F: A, C - G: C Проверка степеней: - deg(A) = 5 - deg(B) = 4 - deg(C) = 4 - deg(D) = 2 - deg(E) = 2 - deg(F) = 2 - deg(G) = 1 Итак, существует граф из семи вершин с задаваемыми степенями 1, 2, 2, 2, 4, 4, 5. Приведённое представление является одним из возможных решений.