Дано:
Граф с 5 вершинами, степени которых равны 4, 1, 3, 2, 4.
Найти:
Пример графа с заданными степенями.
Решение:
1. Обозначим вершины как A, B, C, D, E.
2. Установим степени:
- A: 4
- B: 1
- C: 3
- D: 2
- E: 4
3. Начнем соединять вершины:
- Вершина B со степенью 1 может соединяться только с одной вершиной. Пусть это будет A. Таким образом:
- A соединяется с B (A - B).
- Теперь A, имея 3 оставшиеся рёбер (4 - 1), может соединяться с C, D и E:
- A соединяется с C (A - C).
- A соединяется с D (A - D).
- A соединяется с E (A - E).
Теперь у нас:
- A: соединения (B, C, D, E), степень 4.
- B: соединение (A), степень 1.
- C: соединение (A), степень 1 (необходимо добавить ещё 2 рёбер).
- D: соединение (A), степень 1 (необходимо добавить 1 рёбер).
- E: соединение (A), степень 1 (необходимо добавить 3 рёбер).
4. Добавим связи между оставшимися вершинами:
- Соединим C с D (C - D).
- Соединим C с E (C - E).
- Соединим D с E (D - E).
Теперь у нас есть следующие соединения:
- A - B
- A - C
- A - D
- A - E
- C - D
- C - E
- D - E
5. Проверим степени:
- A: 4 (связи с B, C, D, E)
- B: 1 (связь с A)
- C: 3 (связи с A, D, E)
- D: 2 (связи с A, C, E)
- E: 4 (связи с A, C, D)
Ответ:
Граф с 5 вершинами и степенями 4, 1, 3, 2, 4 может быть представлен соединениями: A - B, A - C, A - D, A - E, C - D, C - E, D - E.