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

а) Подходит цепь A–D–G–E–B. В ней 4 ребра: AD, DG, GE, EB.

б) Считаем цепи длины 5 из A в B, перебирая соседние вершины и не повторяя ребро: A–D–G–E–C–B; A–D–E–C–B–D–? (это 6 рёбер и не подходит); A–B–C–E–D–B; A–B–D–G–E–B; A–D–B–C–E–B; A–D–E–C–B–? (последнее ребро должно вести в B, уже учтено последовательность с начальным A–D–E, затем варианты через C или B).

Полный подсчёт удобнее сделать по последнему ребру и динамическому перечислению. Цепи длины 5:

1. A–B–C–E–D–B;
2. A–B–D–G–E–B;
3. A–D–B–C–E–B;
4. A–D–G–E–C–B;
5. A–D–E–C–B–? (такой путь имеет уже 4 ребра до B: A–D, D–E, E–C, C–B; длина 4).

Для длины 5 требуется ещё одна цепь: A–B–E–C–D–B невозможна, так как ребра CD нет; A–D–B–E–C–B повторяет ребро BC? нет, маршрут имеет 5 ребер: AD, DB, BE, EC, CB — подходит.

Итого цепи длины 5: перечисленные выше (3) и A–D–B–E–C–B, всего 4.

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