Карта дорог представляет собой три двудольных графа.
число дорог равно 3*14*14 = 588.
существует путь, проходящий через все дороги.
Действительно, каждый отдельно взятый двудольный граф с четным числом вершин в каждой дольке можно обойти по следующему алгоритму (здесь 1,2,3,4 - вершины первого графа, a,b,c,d - вершины второго графа):
1a2b1c2d1e2f1g2h1i2j1k2l1m2n...
...3a4b3c4d3e4f3g4h3i4j3k4l3m4n...
...
Алгоритм обхода всех дорог может быть таким:
1) обходим первый двудольный граф полностью;
2) обходим второй граф весь, кроме последней дороги;
588
Пошаговое объяснение:
Карта дорог представляет собой три двудольных графа.
число дорог равно 3*14*14 = 588.
существует путь, проходящий через все дороги.
Действительно, каждый отдельно взятый двудольный граф с четным числом вершин в каждой дольке можно обойти по следующему алгоритму (здесь 1,2,3,4 - вершины первого графа, a,b,c,d - вершины второго графа):
1a2b1c2d1e2f1g2h1i2j1k2l1m2n...
...3a4b3c4d3e4f3g4h3i4j3k4l3m4n...
...
Алгоритм обхода всех дорог может быть таким:
1) обходим первый двудольный граф полностью;
2) обходим второй граф весь, кроме последней дороги;
3) обходим третий граф полностью;
4) проходим последнюю дорогу второго графа.
1)55277+1371=56648 приближенно 57000
55277 приближенно 55300
1371 приближенно 1400
55300+1400=57000
приближенный результат 56648<57000
2) 442393+55438=497831 приближенно 500000
442393 приближенно 440000
55438 приближенно 60000
440000+60000=500000
приближенный результат 497831<500000
3) 238493+21023=259516 приближенно 260000
238493 приближенно 240000
21023 приближенно 20000
240000+20000=260000
приближенный результат 259516<260000
4) 65087+41701=106788 приближенно 107000
65087 приближенно 65000
41701 приближенно 42000
65000+42000=107000
приближенный результат 106788<107000
5)742993+15038=758031 приближенно 758000
742993 приближенно 743000
15038 приближенно 15000
743000+15000=758000
приближенный результат 758000<758031
Пошаговое объяснение: