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

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

Разбираемся: Нам нужно найти путь из вершины A в вершину B, который состоит из 4 рёбер.

Один из возможных вариантов:

A - D - E - C - B

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

Разбираемся: Теперь ищем путь из A в B, состоящий из 5 рёбер.

Один из возможных вариантов:

A - D - A - D - E - B

Другой вариант:

A - F - G - E - C - B

И третий вариант:

A - D - E - G - F - A

Ответ:3 цепи длины 5 соединяют вершину А с вершиной В.

Доп. профит: Редфлаг: Будь внимателен, чтобы не посчитать один и тот же путь дважды, если он просто проходит через одни и те же вершины в разном порядке!