Начертить граф с 6 вершинами со степенями1 1 4 4 2 2

Задача: построить простой граф на 6 вершинах с заданной степенью каждой вершины: 1, 1, 2, 2, 4, 4. 1) Проверка выполнимости (графичность последовательности) - Сумма степеней: 1+1+2+2+4+4 = 14. Это четное число, значит можно получить граф с 7 ребрами (14/2). - Максимальная степень 4 не превышает n-1 = 5, также допускается для простой графа. - Чтобы убедиться точно, применим алгоритм Хавелли–Хакки (Havel-Hakimi). 2) Применение алгоритма Хавелли–Хакки Начальная последовательность (упорядоченная по неубыванию): 4, 4, 2, 2, 1, 1. - Шаг 1: возьмем вершину A степенью 4 и соединим её с 4 вершинами с наибольшими степенями после неё: B, C, D, E. Добавляем ребра: A-B, A-C, A-D, A-E. Обновляем степени оставшихся вершин: B: 4 -> 3, C: 2 -> 1, D: 2 -> 1, E: 1 -> 0, F: 1 (остался без изменения). Новая последовательность (сортируем по убыванию): 3, 1, 1, 1, 0. - Шаг 2: возьмем вершину B степенью 3 и соединим её с тремя вершинами с наибольшими степенями среди оставшихся: C, D, F. Добавляем ребра: B-C, B-D, B-F. Обновляем степени: C:1 -> 0, D:1 -> 0, F:1 -> 0. Остальные вершины имеют степень 0. Все степени стали нулями, значит последовательность графически реализуема. 3) Конструируемый граф (одна из возможных реализаций) Назовём вершины A, B, C, D, E, F так, чтобы соответствовать шагам выше: - A имеет степень 4 - B имеет степень 4 - C имеет степень 2 - D имеет степень 2 - E имеет степень 1 - F имеет степень 1 Соединения (ребра): - A-B, A-C, A-D, A-E - B-C, B-D, B-F Проверка степеней: - deg(A) = 4 (связан с B, C, D, E) - deg(B) = 4 (связан с A, C, D, F) - deg(C) = 2 (с A и B) - deg(D) = 2 (с A и B) - deg(E) = 1 (с A) - deg(F) = 1 (с B) Итого: граф удовлетворяет заданной степени каждого вершины. 4) Как нарисовать это на бумаге - Разместите две вершины A и B вверху слева и справа. - Разместите C и D чуть ниже (между ними можно разместить центр резкое). - E поместите слева внизу, F – справа внизу. - Нарисуйте ребра: A–B, A–C, A–D, A–E, B–C, B–D, B–F. - Получится граф, у которого вершина A и B имеют степень 4, вершины C и D – по 2, E и F – по 1. Примечание - Это одна из возможных реализаций данного суммарного степенного ряда. Мо́гут быть и другие неравносильные по структуре графы, но они тоже будут иметь степени 4, 4, 2, 2, 1, 1. Если хотите, могу привести альтернативную конфигурацию или нарисовать схемы несколькими способами.