В некотором государстве есть 2n городов, между некоторыми из них есть авиалинии. Известно, что от любого города можно добраться до любого самолетом, сделав не более одной пересадки. Какое наименьшее число внутренних авиалиний между городами может быть в этом государстве?

задан 14 Май '17 22:32

Чтобы граф был связным, нужно как минимум 2n-1 ребро. Этого количества хватает, если один город соединить рейсами со всеми остальными. Это в случае, если каждая авиалиния предполагается двусторонней.

(14 Май '17 22:49) falcao
10|600 символов нужно символов осталось
Знаете, кто может ответить? Поделитесь вопросом в Twitter или ВКонтакте.

Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×3,696

задан
14 Май '17 22:32

показан
525 раз

обновлен
14 Май '17 22:49

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru