Задача Задача №3590659
А
А
нарисовать граф с 6 вершинами со степенями 2 2 5 5 3 3
Задача: построить граф на 6 вершинах со степенями 2, 2, 5, 5, 3, 3.
- Проверка на реализацию (множество степеней графическое)
- Сумма степеней должна быть четной: 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.
- Все оставшиеся степени равны нулю → последовательность графическая. Значит граф с такими степенями существует.
- Явное конструирование графа (один пример) Обозначим вершины так: 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).
- Проверка степеней
- 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
- Как это выглядит на бумаге
- Вершины A и B — «центры» графа, соединены между собой и со всеми остальными вершинами.
- Вершины C и D — соединены с A и B и между собой.
- Вершины E и F — соединены с A и B только.
Это один из вариантов графа на 6 вершинах с заданными степенями 2, 2, 5, 5, 3, 3. По аналогии можно построить и другие графы, удовлетворяющие те же степени.
