Семинар ДООМ.Из истории создания графов.

Текущая версия на 09:10, 22 сентября 2008

Участник:Хайруллина Гульнара Равильевна

Участник:ГРАФиК 132

Хайруллина Гульнара Равильевна_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), из современных математиков – К. Берж, О. Оре, А. Зыков.