Замысловатые маршруты и правила Эйлера

Кенигсбергские мосты А, В, С, D – части континента, отделённые друг от друга а, b, с, d, e, f, g – мосты А, В, С, D – узлы(вершины) а, b, с, d, e, f, g – ветви(ребра ) Чётный узел-узел, в котором сходится чётное число ветвей; нечётный узел-узел, в котором сходится нечётное число ветвей.

Правила уникурсального обхода Если возможен обход всей сети одним маршрутом, то она называется уникурсалъной сетью, а маршрут уникурсальным обходом. Правила Эйлера: 1. Сеть, не имеющая нечетных узлов, допускает замкнутый уникурсальный обход с началом в любой точке сети. 2. Сеть, имеющая два и только два нечетных узла, обходится уникурсально, если начать движение с одного нечетного узла и закончить его в другом. 3. Сеть, имеющая больше двух нечетных узлов, нельзя полностью обойти одним маршрутом.

Задача 1 Можно ли начертить данные фигуры одним росчерком, не проводя более одного раза по одной и той же линии и почему? Ответ: а, б.

Задача 2 В одном из залов Дома занимательной науки в Санкт-Петербурге посетителям показывали схему мостов города Требовалось обойти все 17 мостов, соединяющих острова и берега Невы, на которых расположен Санкт-Петербург, Обойти надо так, чтобы каждый мост был пройден один раз. Докажите, что требуемый уникурсальный обход всех мостов Санкт-Петербурга того времени возможен, но не может быть замкнутым, т.е. оканчиваться в пункте, от которого начинался. Однако на своей копии рисунка вы сможете разработать и замкнутый обход, если позволите себе пройти дважды по каким-то двум мостам.

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

Задача 3 На рис. представлен эскиз одного из портретов Эйлера. Художник воспроизвел его одним росчерком пера (только волосы нарисованы отдельно). Где на рисунке расположены начало и конец уникурсального контура? Повторите движение пера художника (волосы и пунктирные линии на рисунке не включаются в маршрут обхода).

Задача 4 На встрече группы хорошо и не очень хорошо знакомых состоялось много приветственных рукопожатий. Некоторые из нас пожали четное число рук, другие нечетное. Например, я обменялся тремя рукопожатиями, а мой друг, математик, девятью. Когда я сказал своему другу, что обменявшихся нечетным числом рукопожатий, кроме меня и его, было еще 5 человек, он ответил: Ошибаешься. Число людей, пожавших нечетное число рук, непременно должно быть четным. Прав ли он? Решение. Да, прав. Задачу можно интерпретировать с сетью с числом узлов, равным числу людей, обменявшихся рукопожатием, а каждое рукопожатие рассматривать как ветвь, соединяющую 2 узла. Необходимо доказать, что в любой сети число узлов чётно. Пусть сеть имеет r ветвей, у к-ых всего 2r концов. Пусть а 1 –число узлов, от к-ых отходит 1 ветвь, a 2 - число узлов, от к-ых отходит 2 ветви, аналогично получаем числа: a 3,a 4,…,a n,… Тогда,a 1 узлов содержит a 1 концов,a 2 узлов - 2a 2 концов, a 3 узлов – 3a 3 концов и т.д.Всего концов будет: a 1 +2a 2 +3a 3 +…+na n +…=2r Значит, a 1 +3a 3 +5a 5 +… чётно, а потому a 1 +a 3 +a 5 +…чётно, что и требовалось доказать.

Задача 5 Чтобы обойти сеть, показанную на рисунке, достаточно двух отдель- ных маршрутов. Укажите оба уникурсаль- ных обхода и придумайте доказательство более общему утверждению: сеть, имеющую ровно 2n нечетных узла, можно полностью обойти по п отдельным маршрутам.

Ответ: Первый маршрут может быть, например, по ветви АС. Если эту ветвь исключить из сети, то узлы А и С становятся чётными и в сети остаются только два чётных угла: В и D. Значит, обход этой сети возможен с началом, например, в В и концом в D. Это второй маршрут.

Доказательство: Начнём обход из нечётного узлаи продолжим его до тех пор, пока не достигнем узла,из которого уже нет выхода. Тогда этот второй узел обязательно нечётный: из чётного узла всегда есть выход, а проходя нечётный узел, мы используем первый из сходящихся в нём концов для входа,а второй для выхода; когда же мы заканчиваем маршрут в нечётном узле, захватывается только один конец. сли изъять из сети пройденный маршрут, останется сеть с 2n 2 нечетными узлами. Следовательно, если осуществить п аналогичных отдельных обходов, то останется одна или более сетей, все узлы которых четны. Но каждая из этих сетей имеет общий узел с одним из пройденных маршрутов и, следовательно, может быть включена в соответствующий маршрут. Таким образом, для полного обхода всей сети понадобится ровно п отдельных маршрутов. Отсюда следует, что если число нечетных узлов больше двух, то сеть нельзя обойти полностью одним маршрутом.Таким образом, мы попутно доказали справедливость правила 3 Эйлера.

Задача 6 Сколько (минимально) потребуется отдельных уникурсальных маршрутов, чтобы обойти полностью шахматную доску по всем прямым, образующим на ней 64 клетки? Ответ: 64 поля шахматной доски образованы сетью, имеющих 28 нечётных узлов.По теореме (сеть, име-ющую 2n нечётных узлов, можно пол- ностью обойти по n отдельным маршру- там), потребуются 14 отдельных маршрутов.