ДЗ Эйлеров путь_8c10ed38... Домашнее задание. Эйлеровы графы. Определение. Путь, содержащий все ребра графа, называется эйлеровым путем. 1. Нарисуйте фигуры, изображенные на рисунке, не отрывая карандаша от бумаги и не проводя никакую линию дважды. 2. В стране имеется несколько городов, некоторые из которых соединены дорогами, причем из города Шарамбарам выходит ровно и дорог. Известный путешественник выехал из одного из городов и объехал всю страну, проехав по каждой дороге ровно один раз. Закончился ли его путь в Шарамбараме, если 1. он начал путь в городе Шарамбарам и и чётно; 2. он начал путь в городе Шарамбарам и и нечётно; 3. он начал путь в другом городе и и чётно; 4. он начал путь в другом городе и и нечётно? 3. Город представляет из себя квадрат 3 на 3, в котором каждая сторона квартала-квадратика участок улицы длиной 300 метров. Какой наименьший путь придётся проделать катку, чтобы заасфальтировать улицы?

Задание 1

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

• Первая фигура: Эту фигуру можно нарисовать одним росчерком, не отрывая карандаша.
• Вторая фигура: Эту фигуру также можно нарисовать одним росчерком, не отрывая карандаша.

Задание 2

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

• Случай 1: Если он начал путь в городе Шарамбарам и n чётно, то его путь закончится в Шарамбараме.
• Случай 2: Если он начал путь в городе Шарамбарам и n нечётно, то его путь не закончится в Шарамбараме.
• Случай 3: Если он начал путь в другом городе и n чётно, то его путь не закончится в Шарамбараме.
• Случай 4: Если он начал путь в другом городе и n нечётно, то его путь может закончиться в Шарамбараме.

Задание 3

Город представляет собой квадрат 3 на 3, где каждая сторона квартала-квадратика имеет длину 300 метров. Нужно определить наименьший путь, который придётся проделать катку, чтобы заасфальтировать улицы.

Рассмотрим структуру города: 3 ряда и 3 столбца квадратов. Длина каждой стороны квадрата 300 метров. Всего в городе 6 горизонтальных и 6 вертикальных участков улиц.

Общая длина улиц, которые нужно заасфальтировать, составляет: \[ (6 + 6) \cdot 300 = 12 \cdot 300 = 3600 \text{ метров} \]

Чтобы найти наименьший путь, нужно пройтись по каждой улице хотя бы один раз. Поскольку город представляет собой квадратную сетку, то можно просто пройтись по всем улицам последовательно.

Наименьший путь, который нужно проделать катку, равен суммарной длине всех улиц: 3600 метров.