Семинар ДООМ.Из истории создания графов.
Участник:Хайруллина Гульнара Равильевна
Хайруллина Гульнара Равильевна_ID_132.ИСТОРИЯ ВОЗНИКНОВЕНИЯ ТЕОРИИ ГРАФОВ.
Родоначальником теории графов принято считать математика Леонарда Эйлера (1707-1783). Историю возникновения этой теории можно проследить по переписке великого ученого. Вот перевод латинского текста, который взят из письма Эйлера к итальянскому математику и инженеру Маринони, отправленного из Петербурга 13 марта 1736 года:
"Некогда мне была предложена задача об острове,
расположенном в городе Кенигсберге и окруженном рекой, через
которую перекинуто семь мостов. Спрашивается, может ли кто-
нибудь непрерывно обойти их, проходя только однажды через каждый
мост. И тут же мне было сообщено, что никто еще до сих пор не
мог это проделать, но никто и не доказал, что это невозможно.
Вопрос этот, хотя и банальный, показался мне, однако, достойным
внимания тем, что для его решения недостаточны ни геометрия, ни
алгебра, ни комбинаторное искусство… После долгих размышлений я
нашел легкое правило, основанное на вполне убедительном
доказательстве, с помощью которого можно во всех задачах такого
рода тотчас же определить, может ли быть совершен такой обход
через какое угодно число и как угодно расположенных мостов или
не может. Кенигсбергские же мосты расположены так, что их можно
представить на следующем рисунке [рис.1], на котором A
обозначает остров, а B, C и D – части континента, отделенные
друг от друга рукавами реки. Семь мостов обозначены буквами a,
b, c, d, e, f, g ".
По поводу обнаруженного им способа решать задачи подобного рода Эйлер писал:
"Это решение по своему характеру, по-видимому, имеет мало
отношения к математике, и мне непонятно, почему следует скорее
от математика ожидать этого решения, нежели от какого-нибудь
другого человека, ибо это решение подкрепляется одним только
рассуждением, и нет необходимости привлекать для нахождения
этого решения какие-либо законы, свойственные математике. Итак,
я не знаю, каким образом получается, что вопросы, имеющие совсем
мало отношения к математике, скорее разрешается математиками,
чем другими".
Так можно ли обойти Кенигсбергские мосты, проходя только один раз через каждый из этих мостов? Чтобы найти ответ, продолжим письмо Эйлера к Маринони:
"Вопрос состоит в том, чтобы определить, можно ли обойти
все эти семь мостов, проходя через каждый только однажды, или
нельзя. Мое правило приводит к следующему решению этого вопроса.
Прежде всего, нужно смотреть, сколько есть участков, разделенных
водой, – таких, у которых нет другого перехода с одного на
другой, кроме как через мост. В данном примере таких участков
четыре – A, B, C, D. Далее нужно различать, является ли число
мостов, ведущих к этим отдельным участкам, четным или нечетным.
Так, в нашем случае к участку A ведут пять мостов, а к остальным
– по три моста, т. е. Число мостов, ведущих к отдельным
участкам, нечетно, а этого одного уже достаточно для решения
задачи. Когда это определено, применяем следующее правило: если
бы число мостов, ведущих к каждому отдельному участку, было
четным, то тогда обход, о котором идет речь, был бы возможен, и
в то же время можно было бы начать этот обход с любого участка.
Если же из этих чисел два были бы нечетные, ибо только одно быть
нечетным не может, то и тогда мог бы совершиться переход, как
это предписано, но только начало обхода непременно должно быть
взято от одного из тех двух участков, к которым ведет нечетное
число мостов. Если бы, наконец, было больше двух участков, к
которым ведет нечетное число мостов, то тогда такое движение
вообще невозможно… если можно было привести здесь другие, более
серьезные задачи, этот метод мог бы принести еще большую пользу
и им не следовало бы пренебрегать".
Обоснование вышеприведенного правила можно найти в письме Л. Эйлера к своему другу Элеру от 3 апреля того же года. Мы перескажем ниже отрывок из этого письма. Математик писал, что переход возможен, если на участке разветвления реки имеется не более двух областей, в которые ведет нечетное число мостов. Для того,чтобы проще представить себе это, будем стирать нарисунке уже пройденные мосты. Легко проверить, что если мы начнем двигаться в соответствии с правилами Эйлера, пересечем один мост и сотрем его, то на рисунке будет изображен участок, где опять имеется не более двух областей,в которые ведет нечетное число мостов, а при наличии областей с нечетным числом мостов мы будем располагаться в одной из них. Продолжая двигаться так далее, пройдем через все мосты по одному разу.
История с мостами города Кенигсберга имеет современное продолжение. Откроем, например, школьный учебник по математике под редакцией Н.Я. Виленкина для шестого класса. В нем на странице 98 в рубрике развития внимательности и сообразительности мы найдем задачу, имеющую непосредственное отношение к той, которую когда-то решал Эйлер.
Задача № 569.
На озере находится семь островов, которые соединены между собой так, как показано на рисунке 1.2. На какой остров должен доставить путешественников катер, чтобы они могли пройти по каждому мосту и только один раз? Почему нельзя доставить путешественников на остров A?
Решение: Поскольку эта задача подобна задаче о Кенигсбергских мостах,то при ее решении мы также воспользуемся правилом Эйлера. В результате получим следующий ответ: катер должен доставить путешественников на остров E или F, чтобы они смогли пройти по каждому мосту один раз. Из того же правила Эйлера следует невозможность требуемого обхода, если он начнется с острова A.
В заключение отметим, что задача о Кенигсбергских мостах и подобные ей задачи вместе с совокупностью методов их исследования составляют очень важный в практическом отношении раздел математики, называемый теорией графов. Первая работа о графах принадлежала Л. Эйлеру и появилась в 1736 году. В дальнейшем над графами работали Кениг (1774-1833), Гамильтон (1805- 1865), из современных математиков – К. Берж, О. Оре, А. Зыков.
