Question

В старину между азиатскими городами были охраняемые караванные пути: Дамаск – Багдад, Анкара –Дамаск, Стамбул – Тегеран, Самарканд – Иерусалим, Стамбул – Багдад, Каир – Иерусалим, Стамбул – Анкара, Дубай – Каир, Самарканд – Каир, Иерусалим – Дубай, Дамаск – Тегеран. До каких городов можно было безопасно добраться из Стамбула пользуясь только этими путями? Все пути двусторонние. Дамаск Самарканд Тегеран Иерусалим Дубай Багдад Каир Анкара

Answer 1

Ответ:

Дамаск

Тегеран

Багдад

Анкара

Объяснение:

Построим граф по предложенному списку дорог. Дороги будут ребрами, а города вершинами.

Как видим некоторые в некоторые города (вершины) нельзя попасть, потому что они находятся в другом компоненте связности графа. И нет дороги соединяющей эти два компонента.

Значит выбираем только те города (вершины), которые лежат в одном компоненте связности со Стамбулом.

Answer 2

Из Стамбула, пользуясь только указанными путями, можно было безопасно добраться до следующих городов:

1. Дамаск
2. Самарканд
3. Тегеран
4. Иерусалим
5. Дубай
6. Багдад
7. Каир
8. Анкара

Эти города являлись частями охраняемых караванных путей и можно было безопасно путешествовать между ними из Стамбула.