1. Определить в графе (на рисунке) три цепи из вершины Е в вершину В

Решение:

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

Рассмотрим граф на рисунке. Вершины: A, B, C, E, M, O, P.

• Цепь 1: E → M → A → B
• Цепь 2: E → O → B
• Цепь 3: E → O → C → P → B

Ответ: E-M-A-B, E-O-B, E-O-C-P-B.