Семинар ДООМ 116

                  Одним росчерком пера.

Вы , наверное , знаете, что есть такой город Калининград, раньше он назывался Кенигсберг. Через город протекает река Преголя. Она делится на два рукава и огибает остров. В 18 веке в городе было 7 мостов расположенных так, как показано на рисунке 1.

Рассказывают , что однажды житель города спросил у своего знакомого , сможет ли он пройти по всем мостам так, что бы на каждом из них побывать только один раз и вернуться к тому мосту, откуда началась прогулка. Многие горожане заинтересовались этой задачей, однако придумать решение никто не смог. Этот вопрос привлёк внимание ученых разных стран. Разрешить проблему удалось известному математику Леонардо Эйлер. Причем, он не только решил эту конкретную задачу , но придумал общий метод решения подобных задач.

Решая задачу про кенигсберские мосты , Элер установил в частности, свойства графа:

1) Если все вершины графа четные , то можно одним росчерком (те. Не отрывая карандаша от бумаги и не проводя дважды по одной линии) начертить граф. При этом движение можно начать в любой вершине и окончить в той же вершине.

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

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