Укажите графы, которые являются цепью.

Решение:

Цепь в теории графов — это последовательность вершин, в которой каждые две соседние вершины соединены ребром. При этом вершины в цепи не должны повторяться.

Рассмотрим предложенные графы:

• Первый граф: Состоит из вершин A, B, C, D. Ребра соединяют: A-B, B-C, C-D. Это последовательность вершин, соединенных ребрами, без повторений. Это цепь.
• Второй граф: Состоит из вершин E, F, G, H. Ребра образуют замкнутый цикл (квадрат). В цепи вершины не должны повторяться, и цепь не должна замыкаться. Это не цепь.
• Третий граф: Состоит из вершин N, C, P, R, O. Вершина C соединена с N, P и R. Это не цепь, так как степень вершины C равна 3 (более двух ребер). Цепь предполагает, что только крайние вершины имеют степень 1, а все остальные — степень 2.
• Четвертый граф: Состоит из вершин I, J, K, L, M. Ребра соединяют: I-K, J-K, K-L, L-M. Вершина K имеет степень 3. Это не цепь.

Ответ: Первый граф является цепью.