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

а) Используем рёбра AB, BE, ED, DG: цепь A–B–E–D–G содержит 4 ребра.

б) Перебирая цепи длины 5 от A до B по рёбрам данного графа, получаем две: A–B–E–D–B и A–D–B–E–B. Повторное прохождение ребра в цепи допустимо; вершины также могут повторяться.

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