Построить граф в котором 5 вершин со степенями 1,2,2,2,3

Задача: построить граф с 5 вершинами such that степени вершин равны 1, 2, 2, 2, 3.

1. Проверка существования

• Сумма степеней должна быть удвоенным числом ребер: 1+2+2+2+3 = 10, значит граф содержит 5 ребер.
• Последовательность степеней 3,2,2,2,1 выполнима по алгоритму Халела–Хака (она графическая), поэтому такой граф существует.

2. Построение графа (пошагово)

• Пусть вершины обозначены как A, B, C, D, E с целевыми степенями: deg(A)=3, deg(B)=2, deg(C)=2, deg(D)=2, deg(E)=1.

Шаг 1. Соединяем вершину A с ближайшими к ней по степеням B, C и D.

• Добавляем ребра: A–B, A–C, A–D.
• Обновляем остаточные степени: deg(B)=1, deg(C)=1, deg(D)=1, deg(E)=1.

Шаг 2. Осталось 4 вершины с остаточными степенями 1,1,1,1. Соединяем их попарно, чтобы удовлетворить всем остаткам.

• Добавляем ребра: B–E и C–D.
• Остаточные степени теперь нулевые: deg(A)=3, deg(B)=2, deg(C)=2, deg(D)=2, deg(E)=1.

3. Итоговые ребра и проверки

• Ребра: A–B, A–C, A–D, B–E, C–D.

• Степени вершин:

  • deg(A) = 3 (соединён с B, C, D)
  • deg(B) = 2 (с A и E)
  • deg(C) = 2 (с A и D)
  • deg(D) = 2 (с A и C)
  • deg(E) = 1 (с B)

• Всего ребер: 5, что совпадает с ранее вычисленной необходимостью.

• Граф связанный: да — есть пути от любой вершины к любой через A и B.

4. Примечание

• Можно увидеть и другой формат графа, но данное решение удовлетворяет всем условиям.
• Метод Хавель-Хака (первый шаг с A, затем обработка оставшихся вершин) подтверждает, что последовательность 3,2,2,2,1 графическая и реальна.

Если нужно, могу привести ASCII-эскиз графа или записать матрицу смежности.