Вершина A B C D E F G Степень 2. В графе, показанном на рисунке к заданию 1, цепь ACDG имеет длину 3. а) Найдите цепь длины 4, которая соединяет вершину В с вершиной А. б) Сколько в этом графе цепей длины 5, которые соединяют вершину А с вершиной В? 3. Можно ли соединить 7 городов дорогами так, чтобы из трёх городов выходило по пять дорог, а из оставшихся четырёх городов - по три дороги? Нарисуйте пример подходящего графа или объясните, почему это невозможно.

Задание 1.

Необходимо найти степени вершин графа, изображенного на рисунке.

Степень вершины - это количество ребер, инцидентных вершине.

• Вершина A: 3 ребра
• Вершина B: 2 ребра
• Вершина C: 3 ребра
• Вершина D: 3 ребра
• Вершина E: 3 ребра
• Вершина F: 0 ребер
• Вершина G: 2 ребра

Задание 2.

В графе, показанном на рисунке к заданию 1, цепь ACDG имеет длину 3.

а) Найдите цепь длины 4, которая соединяет вершину В с вершиной А.

• Цепь длины 4, соединяющая вершину B с вершиной A: BEGCA

б) Сколько в этом графе цепей длины 5, которые соединяют вершину А с вершиной В?

• Цепи длины 5, соединяющие вершину А с вершиной B:
• ACDGEB
• ACGEB (с использованием петли у E)

Задание 3.

Можно ли соединить 7 городов дорогами так, чтобы из трёх городов выходило по пять дорог, а из оставшихся четырёх городов - по три дороги? Нарисуйте пример подходящего графа или объясните, почему это невозможно.

Обозначим число городов как n, а число дорог, выходящих из i-того города, как dᵢ.

Сумма всех степеней вершин в графе должна быть равна удвоенному числу ребер (так как каждое ребро учитывается дважды).

В данном случае у нас 3 города с 5 дорогами и 4 города с 3 дорогами.

Сумма степеней: 3 ⋅ 5 + 4 ⋅ 3 = 15 + 12 = 27

Так как сумма степеней всех вершин должна быть четной, а у нас получилось 27 (нечетное число), то такой граф невозможен.