Рефераты Теория графов

Вернуться в Математика

Теория графов
ВЛАДИМИРСКИЙ ГОСУДАРСТВЕННЫЙ ПЕДАГОГИЧЕСКИЙ УНИВЕРСИТЕТ



РЕФЕРАТ



«ТЕОРИЯ ГРАФОВ»



Выполнила:
Зудина Т.В.



Владимир 2001


СОДЕРЖАНИЕ:



1. Введение

2. История возникновения теории графов

3. Основные определения теории графов

4. Основные теоремы теории графов

5. Задачи на применение теории графов

6. Применение теории графов в школьном курсе математики

7. Приложение теории графов в различных областях науки и техники

8. Последние достижения теории графов

9. Вывод



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

Родоначальником теории графов принято считать математика Леонарда
Эйлера (1707-1783). Историю возникновения этой теории можно проследить по
переписке великого ученого. Вот перевод латинского текста, который взят из
письма Эйлера к итальянскому математику и инженеру Маринони, отправленного
из Петербурга 13 марта 1736 года [см. [5]стр. 41-42]:
"Некогда мне была предложена задача об острове,
расположенном в городе Кенигсберге и окруженном рекой, через
которую перекинуто семь мостов. Спрашивается, может ли кто-
нибудь непрерывно обойти их, проходя только однажды через каждый
мост. И тут же мне было сообщено, что никто еще до сих пор не
мог это проделать, но никто и не доказал, что это невозможно.
Вопрос этот, хотя и банальный, показался мне, однако, достойным
внимания тем, что для его решения недостаточны ни геометрия, ни
алгебра, ни комбинаторное искусство… После долгих размышлений я
нашел легкое правило, основанное на вполне убедительном
доказательстве, с помощью которого можно во всех задачах такого
рода тотчас же определить, может ли быть совершен такой обход
через какое угодно число и как угодно расположенных мостов или
не может. Кенигсбергские же мосты расположены так, что их можно
представить на следующем рисунке [рис.1], на котором A
обозначает остров, а B, C и D – части континента, отделенные
друг от друга рукавами реки. Семь мостов обозначены буквами a,
b, c, d, e, f, g ".

(РИСУНОК 1.1)

По поводу обнаруженного им способа решать задачи подобного рода
Эйлер писал [см. [5]стр. 102-104]:
"Это решение по своему характеру, по-видимому, имеет мало
отношения к математике, и мне непонятно, почему следует скорее
от математика ожидать этого решения, нежели от какого-нибудь
другого человека, ибо это решение подкрепляется одним только
рассуждением, и нет необходимости привлекать для нахождения
этого решения какие-либо законы, свойственные математике. Итак,
я не знаю, каким образом получается, что вопросы, имеющие совсем
мало отношения к математике, скорее разрешается математиками,
чем другими".
Так можно ли обойти Кенигсбергские мосты, проходя только один раз
через каждый из этих мостов? Чтобы найти ответ, продолжим письмо Эйлера к
Маринони:
"Вопрос состоит в том, чтобы определить, можно ли обойти
все эти семь мостов, проходя через каждый только однажды, или
нельзя. Мое правило приводит к следующему решению этого вопроса.
Прежде всего, нужно смотреть, сколько есть участков, разделенных
водой, – таких, у которых нет другого перехода с одного на
другой, кроме как через мост. В данном примере таких участков
четыре – A, B, C, D. Далее нужно различать, является ли число
мостов, ведущих к этим отдельным участкам, четным или нечетным
Добавить в Одноклассники    

 

Rambler's Top100