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

Обозначим вершины буквами: А, Б, В, Г, Д, Е.

Степени: 1, 1, 2, 2, 3, 3.

1. Создадим пару вершин со степенью 3. Пусть это будут А и Б. Соединим их ребром. У них теперь степень 1.

2. Создадим две вершины со степенью 2. Пусть это будут В и Г.

3. Создадим две вершины со степенью 1. Пусть это будут Д и Е.

4. Теперь нужно соединить вершины так, чтобы получить нужные степени.

* Соединим А с В. (А: степень 2, В: степень 1)

* Соединим А с Г. (А: степень 3, Г: степень 1)

* Соединим Б с В. (Б: степень 2, В: степень 2)

* Соединим Б с Д. (Б: степень 3, Д: степень 1)

* Остались вершины Е (степень 1). У нас есть: А-3, Б-3, В-2, Г-1, Д-1. Нам нужны: 1, 1, 2, 2, 3, 3.

* Нужно, чтобы степени В и Г стали 2, а Д и Е — 1. У нас В-2, Г-1, Д-1, Е-0. Нужно повысить степень Г и понизить степень В.

Давайте попробуем иначе, ориентируясь на степени:

Граф 1:

Вершины: 1, 2, 3, 4, 5, 6.

Степени: 3, 3, 2, 2, 1, 1.

1. Соединим 1 и 2 (степени 1, 1). Это будут наши вершины со степенью 1.

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

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

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

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

6. Соединим 3 и 6 (3: степень 3, 6: степень 1).

Получили степени: 1:3, 2:3, 3:3, 4:1, 5:1, 6:1. Это не то.

Снова попробуем:

Пусть вершины А, Б имеют степень 3, В, Г — степень 2, Д, Е — степень 1.

Граф 1:

Соединим А и Б. (А:1, Б:1)
Соединим А и В. (А:2, В:1)
Соединим А и Г. (А:3, Г:1)
Соединим Б и В. (Б:2, В:2)
Соединим Б и Д. (Б:3, Д:1)
Соединим Г и Е. (Г:2, Е:1)

Степени: А-3, Б-3, В-2, Г-2, Д-1, Е-1. Получилось! 6 вершин, степени 1, 1, 2, 2, 3, 3.

Граф 1: Степени вершин: А-3, Б-3, В-2, Г-2, Д-1, Е-1.

Попробуем построить другой граф с теми же степенями.

Вершины: 1, 2, 3, 4, 5, 6.

Степени: 3, 3, 2, 2, 1, 1.

1. Сделаем так, чтобы вершины со степенью 1 были связаны с вершинами, имеющими степень 3.

2. Соединим 1 и 4 (1:1, 4:1).

3. Соединим 2 и 5 (2:1, 5:1).

4. Теперь нужно, чтобы 1 и 2 имели степень 3, а 3 и 4 — степень 2.

5. Соединим 1 и 3 (1:2, 3:1).

6. Соединим 1 и 6 (1:3, 6:1).

7. Соединим 2 и 3 (2:2, 3:2).

8. Соединим 2 и 6 (2:3, 6:2).

Степени: 1-3, 2-3, 3-2, 4-1, 5-1, 6-2. Получили 1, 1, 2, 2, 3, 3. Это тоже подходит!

Граф 2: Степени вершин: 1-3, 2-3, 3-2, 4-1, 5-1, 6-2.

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

Поделись с друзьями