Nika в 05:10, 22 сентября 2008

2008-09-22T05:10:19Z

Одегова Светлана в 16:41, 31 марта 2008

2008-03-31T16:41:44Z

Хайруллина Гульнара Равильевна в 12:17, 31 марта 2008

2008-03-31T12:17:02Z

Хайруллина Гульнара Равильевна в 12:14, 31 марта 2008

2008-03-31T12:14:27Z

Хайруллина Гульнара Равильевна в 12:10, 31 марта 2008

2008-03-31T12:10:22Z

Хайруллина Гульнара Равильевна в 11:51, 31 марта 2008

2008-03-31T11:51:47Z

Хайруллина Гульнара Равильевна: Новая: ИСТОРИЯ ВОЗНИКНОВЕНИЯ ТЕОРИИ ГРАФОВ. Родоначальником теории графов принято считать математика Л...

2008-03-31T11:43:09Z

Новая: ИСТОРИЯ ВОЗНИКНОВЕНИЯ ТЕОРИИ ГРАФОВ. Родоначальником теории графов принято считать математика Л...

Новая страница

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

Родоначальником теории графов принято считать математика Леонарда
Эйлера (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), из современных математиков – К. Берж, О. Оре, А. Зыков.

← Предыдущая		Версия 05:10, 22 сентября 2008
Строка 102:		Строка 102:
	1865), из современных математиков – К. Берж, О. Оре, А. Зыков.		1865), из современных математиков – К. Берж, О. Оре, А. Зыков.

−	[[Категория:~~Проект~~ ДООМ]]	+	[[Категория:Архив проекта ДООМ 2007-2008 (2 цикл)]]

← Предыдущая		Версия 16:41, 31 марта 2008
Строка 102:		Строка 102:
	1865), из современных математиков – К. Берж, О. Оре, А. Зыков.		1865), из современных математиков – К. Берж, О. Оре, А. Зыков.

−	--[[Категория: ~~Семинар ДООМ\|~~Проект ДООМ]]	+	[[Категория:Проект ДООМ]]

← Предыдущая		Версия 12:17, 31 марта 2008
Строка 1:		Строка 1:
		+	[[Участник:Хайруллина Гульнара Равильевна]]
		+
		+	[[Участник:ГРАФиК 132]]
	Хайруллина Гульнара Равильевна_ID_132.ИСТОРИЯ ВОЗНИКНОВЕНИЯ ТЕОРИИ ГРАФОВ.		Хайруллина Гульнара Равильевна_ID_132.ИСТОРИЯ ВОЗНИКНОВЕНИЯ ТЕОРИИ ГРАФОВ.

← Предыдущая		Версия 12:14, 31 марта 2008
Строка 99:		Строка 99:
	1865), из современных математиков – К. Берж, О. Оре, А. Зыков.		1865), из современных математиков – К. Берж, О. Оре, А. Зыков.

−	--[[Категория: Семинар ДООМ]]	+	--[[Категория: Семинар ДООМ\|Проект ДООМ]]

← Предыдущая		Версия 12:10, 31 марта 2008
Строка 99:		Строка 99:
	1865), из современных математиков – К. Берж, О. Оре, А. Зыков.		1865), из современных математиков – К. Берж, О. Оре, А. Зыков.

−	[[Категория: ~~СЕМИНАР~~ ДООМ]]	+	--[[Категория: Семинар ДООМ]]

@@ Строка 1: / Строка 1: @@
-  ИСТОРИЯ ВОЗНИКНОВЕНИЯ ТЕОРИИ ГРАФОВ.
+  Хайруллина Гульнара Равильевна_ID_132.ИСТОРИЯ ВОЗНИКНОВЕНИЯ ТЕОРИИ ГРАФОВ.
 Родоначальником теории  графов  принято  считать  математика  Леонарда
@@ Строка 98: / Строка 98: @@
 году. В дальнейшем над графами работали Кениг (1774-1833), Гамильтон  (1805-
 ), из современных математиков – К. Берж, О. Оре, А. Зыков.