Задача выполнима. Рассмотрим одну конкретную реализацию графа на 5 вершинах с последовательностью степеней 3, 3, 2, 1, 1 (то есть вершинам A,B,C,D,E соответствуют степеням 3,3,2,1,1).
1) Проверка графичности
- Сумма степеней = 3+3+2+1+1 = 10, значит число ребер = 5 (потому что в графе сумма степеней равна удвоенному числу ребер).
- Максимальная степень не превышает n-1 (=4) для n=5.
- По критерию Хавелла-Хатика последовательность 3,3,2,1,1 графичная (пример конструктивного разреза ниже).
2) Конструктивное множество ребер
Обозначим вершины A, B, C, D, E с требуемыми степенями: deg(A)=3, deg(B)=3, deg(C)=2, deg(D)=1, deg(E)=1.
Реализация ребер:
- AB, AC, AD
- BC
- BE
Проверка степеней:
- A: связан с B, C, D → deg(A)=3
- B: связан с A, C, E → deg(B)=3
- C: связан с A, B → deg(C)=2
- D: связан с A → deg(D)=1
- E: связан с B → deg(E)=1
3) Простая графическая иллюстрация (ASCII)
Можно изобразить так, чтобы увидеть связи:
A
/|\
B- C D
|
E
Здесь ребра соответствуют: AB, AC, AD, BC, BE. Это даёт вершинам A(3), B(3), C(2), D(1), E(1).
Дополнительно
- Это один из вариантов; существует множество графов с такой же степенью. Любой другой набор ребер, удовлетворяющий тем же самым степеням, тоже подходит.
- Если нужно, могу нарисовать более точную схему или дать adjacency-list и матрицу смежности.
