124 Нарисуйте какой-либо граф, в котором 5 вершин со степенями 1, 2, 2, 3, 3.

Задание 124

Нам нужно нарисовать граф с 5 вершинами, у которых степени будут такими: одна вершина со степенью 1, две вершины со степенью 2, и две вершины со степенью 3. Попробуем построить такой граф.

Пусть вершины будут А, Б, В, Г, Д.

1. Начнём с вершины с наибольшими степенями. Пусть у вершины А степень 3, и у вершины Б степень 3.

2. Нарисуем ребро между А и Б. Теперь у каждой из них степень 1. Нужно добавить ещё по 2 ребра к каждой.

3. Добавим вершину В со степенью 2 и вершину Г со степенью 2.

4. Добавим ребро от А к В. Теперь у А степень 2, у В степень 1.

5. Добавим ребро от А к Г. Теперь у А степень 3 (ура!), у Г степень 1.

6. Добавим ребро от Б к В. Теперь у Б степень 2, у В степень 2 (ура!).

7. Добавим ребро от Б к Д. Теперь у Б степень 3 (ура!), у Д степень 1.

8. У нас остались вершины В (степень 2) и Г (степень 2) и Д (степень 1). Нам нужны степени 1, 2, 2, 3, 3. У нас сейчас: А-3, Б-3, В-2, Г-1, Д-1. Нам нужно, чтобы было 1, 2, 2, 3, 3. Значит, нужно изменить степени Г и Д.

Давайте попробуем иначе.

Представим вершины как точки. У нас есть степени: 1, 2, 2, 3, 3.

1. Нарисуем две вершины (назовем их 3 и 4) со степенью 3. Соединим их ребром. Теперь у каждой степень 1. Нам нужно добавить по 2 ребра.

2. Нарисуем вершину 1 со степенью 1, вершину 2 со степенью 2, вершину 5 со степенью 2.

3. Соединим вершину 3 с вершиной 1. У вершины 3 степень стала 2, у вершины 1 — степень 1 (готово!).

4. Соединим вершину 3 с вершиной 2. У вершины 3 степень стала 3 (готово!), у вершины 2 — степень 1.

5. Соединим вершину 4 с вершиной 5. У вершины 4 степень стала 2, у вершины 5 — степень 1.

6. Соединим вершину 4 с вершиной 2. У вершины 4 степень стала 3 (готово!), у вершины 2 — степень 2 (готово!).

7. Осталась вершина 5 со степенью 1. Нам нужно, чтобы было две вершины со степенью 2.

Пример построения:

Возьмём 5 точек. Обозначим их цифрами: 1, 2, 3, 4, 5.

• Соединим 1 и 2. (1: степень 1, 2: степень 1)
• Соединим 2 и 3. (2: степень 2, 3: степень 1)
• Соединим 3 и 4. (3: степень 2, 4: степень 1)
• Соединим 4 и 5. (4: степень 2, 5: степень 1)
• Соединим 3 и 5. (3: степень 3, 5: степень 2)
• Соединим 4 и 5. (4: степень 3, 5: степень 3)

Получили степени: 1 (у вершины 1), 2 (у вершины 2), 3 (у вершины 3), 3 (у вершины 4), 2 (у вершины 5).

Это соответствует требуемым степеням: 1, 2, 2, 3, 3.

Ответ: представлен граф выше.