Рассмотри изображения графов и выполни задания.

Привет! Давай вместе посмотрим на изображения графов и решим задачу.

Видно пять графов. Нам нужно определить, какие из них являются деревьями, а какие содержат циклы.

Дерево в теории графов – это связный граф без циклов, то есть в дереве между любыми двумя вершинами существует ровно один простой путь.

Цикл – это путь, начинающийся и заканчивающийся в одной и той же вершине, и при этом посещает другие вершины лишь по одному разу.

Теперь посмотрим на каждый граф:

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

Итак, выбираем номера графов, которые являются деревьями: это графы №1 и №2.

Теперь выберем графы, содержащие циклы: это №3 и №5.