74. В звёздной системе Кастор шесть звёзд, названия которых Ак, Ук, Ок, Юк, Як и Ик. Между некоторыми из звёзд налажено космическое сообщение. Корабли осуществляют рейсы в обе стороны по следующим маршрутам: Ак - Ук, Юк - Як, Ак - Ок, Ак - Ик, Ик - Ок. Можно ли добраться: Нарисуйте граф и соедините вершины - звёзды рёбрами - маршрутами. а) от звезды Ук до звезды Юк; б) от звезды Ук до звезды Ик?

1. а) От звезды Ук до звезды Юк:

Чтобы добраться от Ук до Юк, нужно проверить, существует ли путь между ними. Мы знаем, что:

• Ак связана с Ук (Ак - Ук)
• Ак связана с Ок (Ак - Ок)
• Ак связана с Ик (Ак - Ик)
• Юк связана с Як (Юк - Як)
• Ик связана с Ок (Ик - Ок)

Путь от Ук до Юк:

• Ук → Ак
• Ак → Ок
• Ок → Ик

Чтобы добраться до Юк, нужно найти путь от Ик до Юк. Такого прямого пути нет. Значит, добраться от звезды Ук до звезды Юк невозможно.

2. б) От звезды Ук до звезды Ик:

Чтобы добраться от Ук до Ик, нужно проверить, существует ли путь между ними. Мы знаем, что:

• Ак связана с Ук (Ак - Ук)
• Ак связана с Ик (Ак - Ик)

Путь от Ук до Ик:

• Ук → Ак
• Ак → Ик

Таким образом, можно напрямую добраться от звезды Ук до звезды Ик.

Проверка за 10 секунд: Построй граф по маршрутам и визуально проверь наличие пути между звёздами.

Доп. профит: Если бы требовалось найти кратчайший путь, можно было бы использовать алгоритм поиска в ширину.