Тридевятое царство расположено на шести островах, соединенных мостами. Его карта выглядит как два квадрата с общей стороной, где вершины квадратов — острова, а стороны — мосты. Сколькими способами можно разрушить некоторые мосты так, чтобы по оставшимся можно было добраться от любого острова до любого?

задан 30 Сен '18 15:18

10|600 символов нужно символов осталось
0

В графе 6 вершин и 7 рёбер. Чтобы граф на n вершинах был связным, число рёбер должно быть не меньше n-1 (доказывается по индукции). Значит, в данном случае можно удалить не более двух мостов. Один мост можно удалить 7 способами. Остаётся связный подграф. Два моста в принципе можно удалить 7*6/2=21 способом. Но при этом нельзя оставлять изолированную вершину, то есть 4 способа пропадают. Остаются 17, которые подходят. Итого будет 24.

ссылка

отвечен 30 Сен '18 15:38

10|600 символов нужно символов осталось
Ваш ответ

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

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

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

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

отмечен:

×1,484
×644

задан
30 Сен '18 15:18

показан
690 раз

обновлен
30 Сен '18 15:38

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

по почте:

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

по RSS:

Ответы

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

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