Есть три страны, в каждой по 30 городов. Города связаны дорогой в том и только в том случае, когда они находятся в разных странах. Почтальон Андрей хочет проехать по нескольким дорогам на велосипеде (каждая следующая дорога выходит из того города, в который пришла предыдущая), так, чтобы ни на одной дороге не побывать дважды. Какое максимальное число дорог он может посетить?
253
260
Ответы на вопрос:
ответ:
588
Пошаговое объяснение:
Карта дорог представляет собой три двудольных графа.
число дорог равно 3*14*14 = 588.
существует путь, проходящий через все дороги.
Действительно, каждый отдельно взятый двудольный граф с четным числом вершин в каждой дольке можно обойти по следующему алгоритму (здесь 1,2,3,4 - вершины первого графа, a,b,c,d - вершины второго графа):
1a2b1c2d1e2f1g2h1i2j1k2l1m2n...
...3a4b3c4d3e4f3g4h3i4j3k4l3m4n...
...
Алгоритм обхода всех дорог может быть таким:
1) обходим первый двудольный граф полностью;
2) обходим второй граф весь, кроме последней дороги;
3) обходим третий граф полностью;
4) проходим последнюю дорогу второго графа.
1) 4х-1,3=10,8/4,32
4х-1=2,5
4х=2,5+1
4х=3,5
х=3,5/4
х=0,875
2) 2,7х=270
х=270/2,7
х=100
Популярно: Математика
-
Glenchittt101.02.2021 00:27
-
Adelina1200505.01.2023 16:30
-
koroleva185802.10.2021 21:40
-
МАМКУМАЛ200222.11.2022 11:52
-
nata321201.11.2020 10:32
-
shonchak19.12.2021 18:21
-
Vadimqq24.04.2023 11:07
-
Viktoria1231112.07.2020 01:04
-
supercrud27.01.2020 07:39
-
МаксЭндер22.10.2022 09:51