Задание 2. Решите задачу с помощью графа: Между 6 городами (А, В, С, D, E, F) есть прямые авиарейсы: А-В, А-С, B-D, C-D, D-E, E-F. Постройте дерево. Можно ли долететь из города А в город F? Если да, то каким маршрутом?

Решение:

Для решения задачи построим граф, где города — это вершины, а авиарейсы — рёбра.

Построение дерева:

Дерево — это связный граф без циклов. Из исходного графа, который может содержать циклы (например, A-B-D-C-A), нужно выбрать рёбра так, чтобы все вершины были соединены, и не было циклов. Для 6 вершин нужно 5 рёбер, чтобы получить дерево.

Пример дерева:

Можно ли долететь из города А в город F?

Да, можно долететь. В построенном дереве все города соединены.

Маршрут:

Например, из города А можно долететь до F таким маршрутом: A → B → D → E → F.

Ответ: Да, можно. Пример маршрута: A → B → D → E → F.