начертить граф с 6 вершинами со степенями1 1 4 4 2 2
Задача: построить простой граф на 6 вершинах с заданной степенью каждой вершины: 1, 1, 2, 2, 4, 4.
- Проверка выполнимости (графичность последовательности)
- Сумма степеней: 1+1+2+2+4+4 = 14. Это четное число, значит можно получить граф с 7 ребрами (14/2).
- Максимальная степень 4 не превышает n-1 = 5, также допускается для простой графа.
- Чтобы убедиться точно, применим алгоритм Хавелли–Хакки (Havel-Hakimi).
- Применение алгоритма Хавелли–Хакки Начальная последовательность (упорядоченная по неубыванию): 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. Все степени стали нулями, значит последовательность графически реализуема.
- Конструируемый граф (одна из возможных реализаций) Назовём вершины 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)
Итого: граф удовлетворяет заданной степени каждого вершины.
- Как нарисовать это на бумаге
- Разместите две вершины 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. Если хотите, могу привести альтернативную конфигурацию или нарисовать схемы несколькими способами.
