Постройте Граф в котором Семь вершин степени которых равны соответственно: 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. Приведённое представление является одним из возможных решений.