Маша путешественница

0 +1 -1
Антон Казанаев спросил 7 месяцев назад

Мария отправляется в путешествие. Она хочет объехать все дороги, проехав по каждой ровно один раз. Если это невозможно, то нажимай «Нельзя пройти».
Дороги


BI2804 ответил 7 месяцев назад

Как эта сделать?

2 ответ
0 +1 -1
admin Админ. ответил 7 месяцев назад

Если в какую либо точку идет 3 дороги, то 1 дорога — вход, 2 дорога — выход и остается ровно 1 дорога, которая либо войдет в нее и уже не выйдет, либо выйдет из точки и уже не вернется. Значит, если на картинке имеется точка с 3 входами — выходами, то она должна быть либо в начале, либо в конце пути.

Если точек с 3 вершинами больше двух, то объехать все дороги, проехав по каждой ровно один нельзя!

На представленном рисунке имеется 4 точки, в которые входят-выходят по 3 дороги

Дороги с 4 отмеченными вершинами

Значит в данном случае решения нет.
Ответ: нельзя пройти.

Рома Субботин ответил 7 месяцев назад

А вот такую сеть дорог можно пройти?

И вот такую?

0 +1 -1
admin Админ. ответил 7 месяцев назад

На первом рисунке имеется 4 точки в которые входят — выходят нечетное количество дорог: 2 вершины по 3 дороги и 2 вершины по 5 дорог.

Дороги с 4 отмеченными вершинамиОбобщая, рассмотренный выше частный случай можно сказать, что вершина с нечетным количеством дорог должна быть либо началом пути, либо его концом. И если таких вершин больше двух, то маршрут объезда всех дороги, по котором по каждой дороге можно проехать ровно один раз построить нельзя.

На втором рисунке также имеем 4 точки, в каждую из которых входит по 3 дороги. Значит по второй картинке также нельзя построить нужный маршрут.

Количество дорог, которые выходят из точки называются степенью этой точки, а путь, который проходит через все ребра называется Эйлером путем. Это то, что изучаются в теории графов. Эйлеров путь имеет применение в некоторых областях математики, а также вычислительной биологии.

Решение задачи «Маша путешественница» на видео