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

В условии есть несоответствие рисунку: на видимом графе отсутствует ребро D–C, необходимое для цепи DCEC. Поэтому утверждение о цепи DCEC длины 3 не согласуется с изображённым графом, и ответы для графа по рисунку будут следующими.

а) Цепь длины 4 от A до B: A–D–G–E–B.

б) Для подсчёта цепей длины 5 учитываем рёбра рисунка A–B, A–D, B–C, B–E, C–E, D–G, E–G и петлю в D. Перечисление всех допустимых цепей даёт 9.

Ответ: а) A–D–G–E–B; б) 9 цепей.