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

Для решения вашей задачи, давайте разберем ее шаг за шагом. Мы построим граф, используя данные о рейсах между городами, и проверим наличие цикла. ### Шаг 1: Определение городов и рейсов Исходя из предоставленного текста, у нас есть следующие рейсы: 1. Гранатовый → Салатовый 2. Гранатовый → Золотой 3. Гранатовый → Кварцевый 4. Золотой → Бирюзовый 5. Кварцевый → Бронзовый ### Шаг 2: Построение графа Мы будем использовать ориентированный граф, где: - Вертиками являются города. - Рёбра (или направленные связи) представляют собой рейсы между городами. На основе наших рейсов мы получим следующий набор направленных рёбер: - Гранатовый → Салатовый - Гранатовый → Золотой - Гранатовый → Кварцевый - Золотой → Бирюзовый - Кварцевый → Бронзовый Теперь мы можем изобразить граф. Каждая вершина (город) из которой выходят рёбра: ``` Гранатовый / | \ Салатовый Золотой | Бирюзовый Кварцевый | Бронзовый ``` ### Шаг 3: Проверка на наличие цикла Для проверки наличия цикла в графе можно использовать несколько методов, включая алгоритм поиска в глубину (DFS) или проверку об обратных рёбрах после проведения топологической сортировки. Однако, в этом случае, мы можем заметить самую простую ситуацию: 1. **Гранатовый** направлен в 3 других города, и из них не возвращается обратно к Гранатовому. 2. **Салатовый**, **Золотой**, **Кварцевый** и **Бронзовый** также не имеют обратных рёбер, которые могли бы вернуть нас к городу, из которого началось движение. Пройдя по всем рёбрам, мы не нашли ни одного места, где можно бы было вернуться к исходной вершине. ### Шаг 4: Вывод Так как ни одно из рёбер не создает возможности вернуться к какой-либо из вершин, в построенном графе **нет цикла**. Таким образом, ответ на заданный вопрос — **Цикл в графе отсутствует**.