Question

В таблице представлены рейсы авиакомпании «Полёт № (1)» страны Цветной. По данным в таблице построй граф, в котором вершины — это города, и рёбра соединяют города, только если между ними есть авиарейс. Есть ли в построенном графе цикл?
 Город отправления
   
Город прибытия
Красный    Алый
Красный    Салатовый
Салатовый    Индиго
Индиго    Бордовый
Индиго    Красный

Answer 1

Дано:
Граф авиарейсов между городами: Красный - Алый, Красный - Салатовый, Салатовый - Индиго, Индиго - Бордовый, Индиго - Красный.

Найти:
Есть ли в построенном графе цикл?

Решение:
Для проверки наличия цикла в графе можно использовать обход в глубину (DFS) или ширину (BFS). Однако, так как граф небольшой, можно визуально определить наличие циклов.

Построим граф, где вершины - это города, а рёбра соединяют города, между которыми есть авиарейс. После этого проверим, есть ли в полученном графе циклы.

Ответ:
Построив граф, мы видим, что в нем присутствует цикл: Красный - Салатовый - Индиго - Красный.