Историю возникновения теории

ИСТОРИЯ ВОЗНИКНОВЕНИЯ  ТЕОРИИ ГРАФОВ.

 Родоначальником теории графов  принято считать математика Леонарда  Эйлера (1707-1783). Историю возникновения  этой теории можно проследить  по переписке великого ученого.  Вот перевод латинского текста, который взят из письма Эйлера  к итальянскому математику и  инженеру Маринони, отправленного из Петербурга 13 марта 1736 года :

"Некогда мне была предложена  задача об острове, расположенном  в городе Кенигсберге и окруженном  рекой, через которую перекинуто  семь мостов. Спрашивается, может  ли кто-нибудь непрерывно обойти  их, проходя только однажды через  каждый мост. И тут же мне  было сообщено, что никто еще  до сих пор не мог это  проделать, но никто и не  доказал, что это невозможно. Вопрос  этот, хотя и банальный, показался  мне, однако, достойным внимания  тем, что для его решения  недостаточны ни геометрия, ни  алгебра, ни комбинаторное искусство… После долгих размышлений я нашел легкое правило, основанное на вполне убедительном доказательстве, с помощью которого можно во всех задачах такого рода тотчас же определить, может ли быть совершен такой обход через какое угодно число и как угодно расположенных мостов или не может. Кенигсбергские же мосты расположены так, что их можно представить на следующем рисунке [рис.1], на котором A обозначает остров, а B, C и D – части континента, отделенные друг от друга рукавами реки. Семь мостов обозначены буквами a, b, c, d, e, f, g ".

По поводу обнаруженного им способа  решать задачи подобного рода Эйлер  писал:

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

Так можно ли обойти Кенигсбергские мосты, проходя только один раз через  каждый из этих мостов? Чтобы найти  ответ, продолжим письмо Эйлера к  Маринони:

"Вопрос состоит в том, чтобы  определить, можно ли обойти все  эти семь мостов, проходя через  каждый только однажды, или  нельзя. Мое правило приводит  к следующему решению этого  вопроса. Прежде всего, нужно  смотреть, сколько есть участков, разделенных водой, – таких,  у которых нет другого перехода  с одного на другой, кроме как  через мост. В данном примере  таких участков четыре – A, B, C, D. Далее нужно различать, является  ли число мостов, ведущих к  этим отдельным участкам, четным  или нечетным. Так, в нашем случае  к участку A ведут пять мостов, а к остальным – по три  моста, т. е. Число мостов, ведущих  к отдельным участкам, нечетно,  а этого одного уже достаточно  для решения задачи. Когда это  определено, применяем следующее  правило: если бы число мостов, ведущих к каждому отдельному  участку, было четным, то тогда  обход, о котором идет речь, был бы возможен, и в то же  время можно было бы начать  этот обход с любого участка.  Если же из этих чисел два  были бы нечетные, ибо только  одно быть нечетным не может,  то и тогда мог бы совершиться  переход, как это предписано, но  только начало обхода непременно  должно быть взято от одного  из тех двух участков, к которым  ведет нечетное число мостов. Если бы, наконец, было больше  двух участков, к которым ведет  нечетное число мостов, то тогда такое движение вообще невозможно… если можно было привести здесь другие, более серьезные задачи, этот метод мог бы принести еще большую пользу и им не следовало бы пренебрегать".

 Обоснование вышеприведенного  правила можно найти в письме  Л. Эйлера к своему другу  Элеру от 3 апреля того же года. Мы перескажем ниже отрывок из этого письма.

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

 История с мостами города  Кенигсберга имеет современное  продолжение. Откроем, например, школьный учебник по математике  под редакцией Н.Я. Виленкина для шестого класса. В нем на странице 98 в рубрике развития внимательности и сообразительности мы найдем задачу, имеющую непосредственное отношение к той, которую когда-то решал Эйлер.

Задача № 569. На озере находится  семь островов, которые соединены  между собой так, как показано на рисунке 28. На какой остров должен доставить путешественников катер, чтобы они могли пройти по каждому мосту и только один раз? Почему нельзя доставить путешественников на остров A?

Решение. Поскольку эта задача подобна  задаче о Кенигсбергских мостах, то при ее решении мы также воспользуемся  правилом Эйлера. В результате получим  следующий ответ: катер должен доставить  путешественников на остров E или F, чтобы  они смогли пройти по каждому мосту  один раз. Из того же правила Эйлера следует невозможность требуемого обхода, если он начнется с острова A.

 В заключение отметим, что  задача о Кенигсбергских мостах  и подобные ей задачи вместе  с совокупностью методов их  исследования составляют очень  важный в практическом отношении  раздел математики, называемый теорией  графов. Первая работа о графах  принадлежала Л. Эйлеру и появилась  в 1736 году. В дальнейшем над  графами работали Кениг (1774-1833), Гамильтон (1805-1865), из современных  математиков – К. Берж, О. Оре,  А. Зыков.