Нарисовать граф с 6 вершинами со степенями 2 2 5 5 3 3

Задача: построить граф на 6 вершинах со степенями 2, 2, 5, 5, 3, 3. 1) Проверка на реализацию (множество степеней графическое) - Сумма степеней должна быть четной: 2+2+5+5+3+3 = 20, чётно. Значит такая последовательность может быть графической. - Применим алгоритм Хавелья–Хака (G-H-правило): - Сортируем: 5, 5, 3, 3, 2, 2. - Возьмём первый элемент 5 и соединяем его с двумя следующими вершинами: уменьшаем их степени на 1. Получаем: 4, 2, 2, 1, 1. - Снова сортируем: 4, 2, 2, 1, 1. - Возьмём 4 и соединяем его с следующими четырьмя вершинами: уменьшаем их степени на 1. Получаем: 1, 1, 0, 0. - Сортируем: 1, 1, 0, 0. - Возьмём 1 и соединяем с одной следующей вершиной: получаем 0, 0, 0. - Все оставшиеся степени равны нулю → последовательность графическая. Значит граф с такими степенями существует. 2) Явное конструирование графа (один пример) Обозначим вершины так: A, B, C, D, E, F. - Пусть вершины A и B имеют степень 5 (максимальная для 6 вершин), остальные — C и D степеней 3, а E и F — степеней 2. - Построим следующий набор рёбер: - A соединяется с B, C, D, E, F (A имеет deg 5). - B соединяется с A, C, D, E, F (B имеет deg 5). - C соединяется с A, B и D (deg 3). - D соединяется с A, B и C (deg 3). - E соединяется с A и B (deg 2). - F соединяется с A и B (deg 2). 3) Проверка степеней - A: {B, C, D, E, F} — deg 5 - B: {A, C, D, E, F} — deg 5 - C: {A, B, D} — deg 3 - D: {A, B, C} — deg 3 - E: {A, B} — deg 2 - F: {A, B} — deg 2 Итоговая форма графа: ребра AB, AC, AD, AE, AF, BC, BD, BE, BF, CD 4) Как это выглядит на бумаге - Вершины A и B — «центры» графа, соединены между собой и со всеми остальными вершинами. - Вершины C и D — соединены с A и B и между собой. - Вершины E и F — соединены с A и B только. Это один из вариантов графа на 6 вершинах с заданными степенями 2, 2, 5, 5, 3, 3. По аналогии можно построить и другие графы, удовлетворяющие те же степени.