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

Задача: построить простой неориентированный граф, у которого степени вершин равны 2, 2, 1, 3. 1) Проверка, что последовательность графична - В отсортированном порядке по невозрастанию: 3, 2, 2, 1. - Сумма степеней: 3 + 2 + 2 + 1 = 8 — чётная, значит графичность потенциально возможна. - Применим алгоритм Хавелла–Хакки (по шагам): - Убираем наибольшую степень 3 и "соединяем" её с следующими трёх вершинами (сдецаем на 1 их степени): остаются 2-ые вершины с степенями 2, 2, 1 -> после вычитания: 1, 1, 0. - Теперь имеем последовательность 1, 1, 0. Берём максимальную 1 и соединяем её с следующей вершиной степенью 1: вычитаем 1 у неё и у текущей вершины. Получаем 0, 0, 0. - Все оставшиеся степени нули — последовательность графична. Итог: такая графическая реализация существует. 2) Построение графа (пошагово) Обозначим вершины так, чтобы каждая имела нужную степень: - Пусть вершины A, B — имеют степени 2, D имеет степень 3, C имеет степень 1. - Запишем в порядке неубывания/неубывающего для удобства: D(3), A(2), B(2), C(1). Шаг 1. Соединяем вершину D (степень 3) с тремя следующими вершинами по порядку: A, B, C. - Добавляем рёбра: D–A, D–B, D–C. - Обновляем степени: A становится 1, B становится 1, C становится 0, D уже использована. Состояние после шага 1: A(1), B(1), C(0). Шаг 2. Выбираем вершину с наибольшей степенью среди оставшихся: A(1) (или B(1)). - Соединяем A с другой вершиной с положительной степенью, то есть с B. - Добавляем ребро A–B. - Обновляем степени: A становится 0, B становится 0. C остаётся 0. Теперь все вершины имеют степень 0 (последовательность выполнена). 3) Итоговая конфигурация графа Граф (вершины A, B, C, D) имеет следующие рёбра: - D–A - D–B - D–C - A–B Проверка степеней: - deg(D) = 3 (D соединён с A, B, C) - deg(A) = 2 (A соединён с D и B) - deg(B) = 2 (B соединён с D и A) - deg(C) = 1 (C соединён с D) Это соответствует заданной последовательности степеней 2, 2, 1, 3 (в любом порядке вершин). Дополнитель notes: - Порядок вершин в исходной последовательности не обязателен; для построения можно начать с вершины степени 3 и затем идти по убыванию степеней. - Это единственный стандартный способ построения одного примера такого графа; существует и другие изоморфные реализации, если менять маркировку вершин.