Информатика | 5 - 9 классы
В стране есть несколько городов, соединенных двусторонними дорогами.
Каждую дорогу можно за некоторое количество денег (оно указано на рисунке возле дороги) превратить в скоростную магистраль.
За какое минимальное количество денег можно добиться того, чтобы из любого города можно было попасть в любой другой, передвигаясь только по скоростным магистралям?
На рисунке - схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, К?
На рисунке - схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, К.
По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.
Сколько существует различных путей из города А в город К?
В стране есть 21 городов?
В стране есть 21 городов.
Некоторые пары городов соединены двусторонними дорогами.
Известно, что из любого города в любой другой можно добраться ровно одним способом (способом называется путь, состоящие из городов, никакие два города в нем не повторяются).
Сколько всего дорог в стране?
В стране есть 19 городов?
В стране есть 19 городов.
Некоторые пары городов соединены одной двусторонней дорогой.
Известно, что из любого города в любой другой можно добраться ровно двумя различными способами (способом называется путь, состоящий из городов ; никакие два города в нем не совпадают).
Сколько всего дорог в стране?
В одном царстве есть N городов, некоторые из которых соединены дорогами?
В одном царстве есть N городов, некоторые из которых соединены дорогами.
Царь решил провести инвентаризацию дорог в своем государстве.
Но, как оказалось, он не силен в математике, поэтому он просит вас сосчитать количество дорог.
ТОВАРИЩИ ПОМОГИИИТЕ?
ТОВАРИЩИ ПОМОГИИИТЕ!
На рисунке - схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З.
По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.
Сколько существует различных путей из города А в город З?
Пожалуйста, с объяснением?
Пожалуйста, с объяснением.
На рисунке - схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, И, К.
По каждой дороге можно двигаться только в одном направлении, указанным стрелкой.
Сколько существует путей из города А в город К?
Помогите с графами по ИКТ?
Помогите с графами по ИКТ.
2) На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З.
По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.
Сколько существует различных путей из города А в город З?
На рисунке - схема дорог связывающих города А Б В Г Д Е Ж И К М?
На рисунке - схема дорог связывающих города А Б В Г Д Е Ж И К М.
По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.
Сколько существует путей, ведущих из города А в город М и НЕ проходящих через город Г?
На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, И, К?
На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, И, К.
По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.
Сколько существует различных путей из города А в город К?
На рисунке — схема дорог, связывающих города A, B, C, D, E, F, G?
На рисунке — схема дорог, связывающих города A, B, C, D, E, F, G.
По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.
Сколько существует различных путей из города А в город G.
На этой странице находится ответ на вопрос В стране есть несколько городов, соединенных двусторонними дорогами?, из категории Информатика, соответствующий программе для 5 - 9 классов. Чтобы посмотреть другие ответы воспользуйтесь «умным поиском»: с помощью ключевых слов подберите похожие вопросы и ответы в категории Информатика. Ответ, полностью соответствующий критериям вашего поиска, можно найти с помощью простого интерфейса: нажмите кнопку вверху страницы и сформулируйте вопрос иначе. Обратите внимание на варианты ответов других пользователей, которые можно не только просмотреть, но и прокомментировать.
Для наглядности подписал условные города.
(Без никаких намёков, серьёзно.
Чисто ради наглядности).
Мысли есть такие : во - первых, картасодержит замкнутые маршруты - циклы, следовательно, может быть превращена в "дерево" методом отбрасывания части дорог.
При этом общая протяжённость модернизируемыхдорог будет сокращена, а сэкономленные денюжки можно будетраспилить.
Во - вторых, отбрасывание дорог (тем самым разрыв циклов) нужно сделать таким образом, чтобы исключаласьсамая длинная дорога.
Вроде логика понятна.
Итак, попробуем.
Идём слева направо.
Москва - Питер не имеет альтернатив, поэтому эту дорогу включаем в план модернизации.
Далее видим цикл Москва - Минск - Брест - Москва.
Какая из этих дорог самая длинная?
Минск - Брест (12) - тогда исключаем эту дорогу из плана, но при этом связность городов сохраняется.
Следующий цикл остаётся Москва - Брест - Киев - Харьков - Москва.
Отбросим Брест - Киев (14), как самую длинную.
Далее остаётся последний цикл Москва - Харьков - Киев - Донецк - Москва.
Здесь самая длинная дорога Киев - Донецк (12), исключаем её.
Больше циклов не остаётся, значитбольше исключать никакую дорогу нельзя, иначе нарушится связность городов.
Сколько исключили?
12 + 14 + 12.
Считаем оставшиеся : 2 + 9 + 4 + 2 + 8 + 7 = 32 - - такой ответ.
Вроде так получается, проверь за мной внимательно.