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

а) Цепь A–D–G–E–B соединяет A и B и содержит четыре ребра: AD, DG, GE, EB.

б) Число зависит от определения цепи: если требуется простой путь без повторения вершин, ответ — 0, поскольку в данном графе нет пути из A в B длины 5 с пятью различными рёбрами и без повторения вершин. Если разрешено повторять вершины, но запрещено повторять рёбра, такие цепи могут включать петлю при D; условие не уточняет принятое в задании определение, поэтому для однозначного подсчёта нужен этот критерий.

Ответ: а) A–D–G–E–B; б) при понимании цепи как простого пути — 0.