1. Какие из пяти показанных на рисунке графов являются: а) деревьями; б) цепями?

Задание 1. Графы

Давай разберёмся, какие из предложенных графов являются деревьями, а какие — цепями.

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

Рассмотрим каждый граф:

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

Ответ:

• а) Деревьями являются графы 1, 2, 3, 4, 5.
• б) Цепью является граф 2.