В
Все
М
Математика
О
ОБЖ
У
Українська мова
Х
Химия
Д
Другие предметы
Н
Немецкий язык
Б
Беларуская мова
М
Музыка
Э
Экономика
Ф
Физика
Б
Биология
О
Окружающий мир
У
Українська література
Р
Русский язык
Ф
Французский язык
П
Психология
О
Обществознание
А
Алгебра
М
МХК
Г
География
И
Информатика
П
Право
А
Английский язык
Г
Геометрия
Қ
Қазақ тiлi
Л
Литература
И
История
KapitanNEMO
KapitanNEMO
05.09.2022 01:55 •  Математика

Есть три страны, в каждой по 30 городов. Города связаны дорогой в том и только в том случае, когда они находятся в разных странах. Почтальон Андрей хочет проехать по нескольким дорогам на велосипеде (каждая следующая дорога выходит из того города, в который пришла предыдущая), так, чтобы ни на одной дороге не побывать дважды. Какое максимальное число дорог он может посетить?

Показать ответ
Ответ:
Crackstack18
Crackstack18
17.11.2020 22:30
ответ:

588

Пошаговое объяснение:

Карта дорог представляет собой три двудольных графа.

число дорог равно 3*14*14 = 588.

существует путь, проходящий через все дороги.

Действительно, каждый отдельно взятый двудольный граф с четным числом вершин в каждой дольке можно обойти по следующему алгоритму (здесь 1,2,3,4 - вершины первого графа, a,b,c,d - вершины второго графа):

1a2b1c2d1e2f1g2h1i2j1k2l1m2n...

...3a4b3c4d3e4f3g4h3i4j3k4l3m4n...

...

Алгоритм обхода всех дорог может быть таким:

1) обходим первый двудольный граф полностью;

2) обходим второй граф весь, кроме последней дороги;

3) обходим третий граф полностью;

4) проходим последнюю дорогу второго графа.

0,0(0 оценок)
Популярные вопросы: Математика
Полный доступ
Позволит учиться лучше и быстрее. Неограниченный доступ к базе и ответам от экспертов и ai-bota Оформи подписку
logo
Начни делиться знаниями
Вход Регистрация
Что ты хочешь узнать?
Спроси ai-бота