3. В новом коттеджном посёлке 7 домиков. Они уже стоят, а дорожки предстоит проложить. Есть три плана прокладки. Нужно выбрать такой, при котором бульдозер сможет расчистить все дорожки, проходя по каждой по одному разу. При этом он должен вернуться в начальную точку. Какой план необходимо выбрать? Перерисуй его в тетрадь.

Ответ: План 3

Решение:

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

• План 1: Не подходит, так как есть вершины со степенью 3 (нечётное число рёбер).
• План 2: Не подходит, так как есть вершины со степенью 3 (нечётное число рёбер).
• План 3: Подходит, так как все вершины имеют степень 2 или 4 (чётное число рёбер).

Таким образом, план 3 позволяет бульдозеру выполнить задачу.

Ответ: План 3