Постройте граф, в котором 6 вершин, степени которых равны соответственно: 2, 2, 2, 3, 3, 4.

Решение:

Для построения графа с заданными степенями вершин воспользуемся алгоритмом, например, алгоритмом Хавела-Хакими или просто построим граф, удовлетворяющий условиям.

Степени вершин: 4, 3, 3, 2, 2, 2 (упорядочим по убыванию для удобства).

Построение графа:

1. Возьмем вершину A со степенью 4. Соединим ее с четырьмя другими вершинами: B, C, D, E.

* Текущие степени: A(4), B(1), C(1), D(1), E(1), F(0).

2. Возьмем вершину B со степенью 3. Она уже связана с A. Соединим ее с двумя оставшимися вершинами, у которых степень еще не равна 3: C и F.

* Текущие степени: A(4), B(3), C(2), D(1), E(1), F(1).

3. Возьмем вершину C со степенью 3. Она связана с A и B. Соединим ее с оставшейся вершиной, степень которой еще не равна 2: D.

* Текущие степени: A(4), B(3), C(3), D(2), E(1), F(1).

4. Возьмем вершину D со степенью 2. Она связана с A и C. Ее степень уже равна 2. Проверяем оставшиеся вершины.

5. Возьмем вершину E со степенью 2. Она связана с A. Соединим ее с вершиной F.

* Текущие степени: A(4), B(3), C(3), D(2), E(2), F(2).

6. Возьмем вершину F со степенью 2. Она связана с B и E. Ее степень уже равна 2.

Итоговые степени: A(4), B(3), C(3), D(2), E(2), F(2). Это соответствует заданным степеням 2, 2, 2, 3, 3, 4.

Визуальное представление графа:

Примечание: Существует множество вариантов построения графа с заданными степенями вершин. Приведен один из возможных.