На первом рисунке имеется 4 точки в которые входят — выходят нечетное количество дорог: 2 вершины по 3 дороги и 2 вершины по 5 дорог. Дороги с 4 отмеченными вершинами Обобщая, рассмотренный выше частный случай можно сказать, что вершина с нечетным количеством дорог должна быть либо началом пути, либо его концом. И если таких вершин больше двух, то маршрут объезда всех дороги, по котором по каждой дороге можно проехать ровно один раз построить нельзя.
На втором рисунке также имеем 4 точки, в каждую из которых входит по 3 дороги. Значит по второй картинке также нельзя построить нужный маршрут. Количество дорог, которые выходят из точки называются степенью этой точки, а путь, который проходит через все ребра называется Эйлером путем. Это то, что изучаются в теории графов. Эйлеров путь имеет применение в некоторых областях математики, а также вычислительной биологии.
Дорогу можно пройти в двух случаях: 1) Если в каждом узле четное число дорожек. Тогда можно начать в любой точке и закончить в ней же. 2) Если в ДВУХ узлах нечетное число дорожек, а остальные четные. Тогда придется начать в одной нечетной точке и закончить в другой. 3) Если нечетных узлов больше двух, то пройти такую карту нельзя. На верхнем левом рисунке у нас 1) случай - две точки с 4 дорожками.. На нижнем левом 2) случай - две точки по 5 дорожек. Справа на обоих рисунках 3) случай. На верхнем 4 точки по 3 дорожки. На нижнем 2 точки по 3 и 2 точки по 5
Начинаем с точки 1 и следуем по стрелкам
На первом рисунке имеется 4 точки в которые входят — выходят нечетное количество дорог: 2 вершины по 3 дороги и 2 вершины по 5 дорог.
Дороги с 4 отмеченными вершинами Обобщая, рассмотренный выше частный случай можно сказать, что вершина с нечетным количеством дорог должна быть либо началом пути, либо его концом. И если таких вершин больше двух, то маршрут объезда всех дороги, по котором по каждой дороге можно проехать ровно один раз построить нельзя.
На втором рисунке также имеем 4 точки, в каждую из которых входит по 3 дороги. Значит по второй картинке также нельзя построить нужный маршрут.
Количество дорог, которые выходят из точки называются степенью этой точки, а путь, который проходит через все ребра называется Эйлером путем. Это то, что изучаются в теории графов. Эйлеров путь имеет применение в некоторых областях математики, а также вычислительной биологии.
Дорогу можно пройти в двух случаях:
1) Если в каждом узле четное число дорожек. Тогда можно начать в любой точке и закончить в ней же.
2) Если в ДВУХ узлах нечетное число дорожек, а остальные четные.
Тогда придется начать в одной нечетной точке и закончить в другой.
3) Если нечетных узлов больше двух, то пройти такую карту нельзя.
На верхнем левом рисунке у нас 1) случай - две точки с 4 дорожками..
На нижнем левом 2) случай - две точки по 5 дорожек.
Справа на обоих рисунках 3) случай.
На верхнем 4 точки по 3 дорожки. На нижнем 2 точки по 3 и 2 точки по 5