Задание 7. Среди графов, изображенных на рисунке, найдите те, которые являются: а) цепью; б) простым циклом.

Решение:

Граф 1:

Вершины: A, B, C, D. Рёбра: (A, B), (B, C), (C, D). Это простой путь (цепь), так как нет циклов и все вершины и рёбра используются по одному разу.

Граф 2:

Вершины: I, J, K, L. Рёбра: (I, J), (J, K), (K, L), (L, I). Это простой цикл, так как все вершины соединены последовательно и замыкаются в кольцо.

Граф 3:

Вершины: K, L, M. Рёбра: (K, L), (L, M). Это простой путь (цепь).

Ответ:

а) Цепями являются графы 1 и 3.

б) Простым циклом является граф 2.