2. В графе, показанном на рисунке к заданию 1, цепь DGEC имеет длину 3.

Решение:

а) Найдем цепь длины 4, которая соединяет вершину А с вершиной В.

Цепь — это последовательность вершин, где каждая следующая вершина соединена ребром с предыдущей, и все вершины в цепи различны. Длина цепи — количество рёбер в ней.

Проанализируем возможные пути из A в B:

• A → B (длина 1)
• A → D → B (длина 2)
• A → B → C → E → D → F (Это путь, а не цепь, так как вершина D встречается дважды. Ищем именно цепь.)
• A → D → E → C → B (длина 4). Это цепь, так как все вершины различны.

Ответ: A-D-E-C-B

б) Сколько в этом графе цепей длины 5, которые соединяют вершину А с вершиной В?

Перечислим все возможные цепи длины 5 из A в B:

1. A → D → E → G → C → B (длина 5)
2. A → B → C → E → D → F (это путь, а не цепь, так как F не ведет к B)
3. A → D → F (это путь, но короче 5)
4. A → B → D → E → G → C (это путь, но не заканчивается в B)
5. A → D → E → C → G → F (это путь, но не заканчивается в B)
6. A → D → B (это путь, но короче 5)
7. A → B → C → E → G (это путь, но не заканчивается в B)

Рассмотрим все возможные пути из A в B длиной 5:

• A → D → E → G → C → B

Других вариантов цепей длины 5 из A в B не существует, так как при попытке построения более длинной цепи либо вершины повторяются, либо путь упирается в тупик (вершину, из которой невозможно продолжить путь без повторения вершин).

Ответ: 1