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

а) Подходит цепь A–D–G–E–B: она соединяет A и B и содержит 4 ребра.

б) Цепь не повторяет рёбра. Учитывая петлю при D и две различные дуги между C и E, получаются три цепи длины 5:

1. A–D–D–G–E–B (ребро D–D — петля);
2. A–D–G–E–C–B;
3. A–D–G–E–C–B, где на участке E–C используется другая из двух параллельных дуг.

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