1.1. Выпишите номера графов, которые являются: а) цепями; б) циклами; в) не-связными графами.

Решение:

Проанализируем каждый граф:

• Граф 1: Представляет собой линию, соединяющую три вершины, и две отдельные вершины. Это не-связный граф.
• Граф 2: Имеет три вершины, соединенные между собой, и одну отдельную вершину. Это не-связный граф.
• Граф 3: Состоит из трех вершин, соединенных в треугольник, и двух отдельных вершин. Это не-связный граф.
• Граф 4: Представляет собой замкнутый контур из четырех вершин. Это цикл.

Теперь классифицируем по категориям:

• а) Цепи: Графы, в которых есть путь, проходящий через каждую вершину ровно один раз. Ни один из представленных графов не является цепью в строгом смысле (Эйлеров путь или Гамильтонов путь, если не указано иное). Однако, если под 'цепями' подразумеваются пути, то граф 1 может быть интерпретирован как часть пути.
• б) Циклы: Графы, где есть путь, начинающийся и заканчивающийся в одной вершине, проходящий через остальные вершины ровно один раз (Гамильтонов цикл) или все рёбра ровно один раз (Эйлеров цикл). В данном случае, граф 4 является простым циклом.
• в) Не-связные графы: Графы, состоящие из двух или более компонент связности. Графы 1, 2, 3 являются не-связными, так как содержат изолированные вершины.

Ответ:

• а) Цепи: Нет (если не считать граф 1 как путь).
• б) Циклы: 4
• в) Не-связные графы: 1, 2, 3