В стране 20 городов. Некоторые города соединены дорогой с двухсторонним движением. Для любого подмножества из пяти го... В стране 20 городов. Некоторые города соединены дорогой с двухсторонним движением. Для любого подмножества из пяти городов A выполняется, что из любого города из A можно добраться до любого другого города из A , перемещаясь лишь между городами из A . Какое наименьшее количество дорог может быть в стране?
В стране 20 городов. Некоторые города соединены дорогой с двухсторонним движением. Для любого подмножества из пяти го... В стране 20 городов. Некоторые города соединены дорогой с двухсторонним движением. Для любого подмножества из пяти городов A выполняется, что из любого города из A можно добраться до любого другого города из A , перемещаясь лишь между городами из A . Какое наименьшее количество дорог может быть в стране?
Не можешь разобраться в этой теме?
Обратись за помощью к экспертам
Гарантированные бесплатные доработки
Быстрое выполнение от 2 часов
Проверка работы на плагиат
Интересные статьи из справочника
Поможем написать учебную работу
Отвечай на вопросы, зарабатывай баллы и трать их на призы.
Подробнее
Подробнее
Для решения данной задачи можно воспользоваться теорией графов. По условию, мы знаем что для любого подмножества из пяти городов выполняется условие полной связности.
Из теории графов известно, что минимальное количество ребер графа, обеспечивающее полную связность для подграфа из n вершин, равно n - 1. Так как в данном случае у нас подмножество из 5 городов, то минимальное количество ребер в подграфе из 5 вершин будет равно 4.
Поскольку в каждом городе может быть не более 19 дорог (по одной к каждому из 19 других городов), то наименьшее количество дорог в стране для обеспечения условия задачи будет равно 20*4 = 80.
Итак, минимальное количество дорог в стране равно 80.