Реши

Для решения задач по теории графов давайте разберём каждую из них отдельно и подробно.

Задача №1

Найти степени вершин графа на рисунке 1.

Решение:

Степень вершины — это количество рёбер, которые к ней подходят.

• Вершина A:

  • К ней подходят 2 рёбра.
  • Степень: 2.

• Вершина B:

  • К ней подходят 2 рёбра.
  • Степень: 2.

• Вершина В:

  • К ней подходят 2 рёбра.
  • Степень: 2.

Каждая из вершин A, B и В имеет степень 2.

Задача №2

Сколько у каждого из графов (на рисунке 2) вершин степени 0, степени 1 и степени 2.

Решение:

Граф а):

• Вершина C:

  • К ней не подходит ни одного ребра.
  • Степень: 0.

• Вершина D:

  • К ней подходит 1 ребро.
  • Степень: 1.

• Вершина E:

  • К ней подходит 2 ребра.
  • Степень: 2.

В графе (а) 1 вершина степени 0, 1 вершина степени 1 и 1 вершина степени 2.

Граф б):

• Вершина F:

  • К ней подходит 1 ребро.
  • Степень: 1.

• Вершина G:

  • К ней подходит 1 ребро.
  • Степень: 1.

Здесь у нас нет вершин степени 0 и 2 вершины степени 1.

Задача №3

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

Решение:

Для создания графа с заданными степенями вершин можно построить следующую конфигурацию:

1. Вершина V1 — степень 1: соединена с V2.
2. Вершина V2 — степень 4: соединена с V1, V3, V4, и V5.
3. Вершина V3 — степень 2: соединена с V2 и V5.
4. Вершина V4 — степень 2: соединена с V2 и V5.
5. Вершина V5 — степень 3: соединена с V2, V3 и V4.

Теперь граф имеет 5 вершин со степенями 1, 2, 2, 3 и 4.