В данной работе вы познакомитесь с основами теории графов, с историей их развития. В последнее время теория графов стала простым, доступным и мощным средством решения вопросов, относящихся к широкому кругу проблем. Это проблемы исследования блок-схем программ, экономики и статистики. В работе приведены примеры применения графов в современном мире, решающие данные проблемы.
Вложение | Размер |
---|---|
![]() | 936 КБ |
Муниципальное бюджетное общеобразовательное учреждение
средняя общеобразовательная школа № 17
г. Липецка
Проект на тему:
Выполнила: ученица 9 «Б» класса
Сафронова Кристина.
Руководитель:
учитель математики
Сафронова О.Н.
2012 г.
« Эйлер вычислял без всякого видимого усилия, как человек дышит или как орёл парит над землёй ».
Доминик Араго.
Гипотеза:
Если теорию графов сблизить с практикой, то можно получить самые благотворные результаты.
Цель:
Познакомиться с понятием графы и показать их применение на практике.
Задачи:
1.Познакомиться с историей возникновения графов.
2.Изучить различные виды графов и их свойства.
3.Рассмотреть примеры применения графов в современном мире.
1
Содержание:
I. Введение. 3 стр.
II. Основная часть.
1. Понятие графа. Задача о Кенигсбергских мостах. 3-4 стр.
2. Свойства графов. 4- 6 стр.
3. Использование графов в повседневной жизни 7-9 стр.
Ш. Заключение.
Значение графов. 10 стр.
IV. Список используемой литературы. 11стр.
2
I. ВВЕДЕНИЕ.
Теория графов – наука сравнительно молодая. Графы, о которых пойдет речь, к аристократам былых времен никакого отношения не имеют. Эти «графы» имеют корень греческого слова «графо», что значит «пишу». Тот же корень в словах «график», «биография», «голография».
Услышав и прочитав теорию графов меня эта тема очень заинтересовала. Я решила узнать как можно применить теорию графов на практике, в жизни, и поделиться с этим с одноклассниками.
Впервые с задачами, для решения которых используются графы, я встретились на олимпиаде по математике. Трудности в решении этих задач объяснялись отсутствием этой темы в обязательном курсе школьной программы. Возникшая проблема стала главной причиной выбора темы данной исследовательской работы.
II. ОСНОВНАЯ ЧАСТЬ.
1. Понятие графа.
Слово «граф» в математике означает картинку, где нарисовано несколько точек, некоторые из которых соединены линиями.
Первая работа по теории графов принадлежит Леонарду Эйлеру. Она появилась в 1736 году в публикациях Петербургской Академии Наук и начиналась с рассмотрения задачи о кенигсбергских мостах.
Работа эта начинается следующими строками, определяющими к какой области математики относятся подобные вопросы:
«Кроме той отрасли геометрии, которая рассматривает величины и способы измерения, и которая тщательно разрабатывалась еще в древности, Лейбниц первый упомянул о другой отрасли, названной им «геометрией положения». Эта отрасль геометрии занимается только порядком расположения частей фигуры друг относительно друга, отвлекаясь от их размеров (в наше время эту отрасль геометрии принято называть «топология»). Недавно мне пришлось слышать об одной задаче,
относящейся к геометрии положения, и я решил изложить здесь в виде примера найденный мной способ решения этой задачи».
Вы наверное, знаете, что есть такой город Калининград, раньше он назывался Кенигсберг. Через город протекает река Преголя. Она делится на два рукава и огибает остров. В 17 веке в городе было семь мостов, расположенных так, как показано на рисунке.
3
Рассказывают, что однажды житель города спросил у своего знакомого, сможет ли он пройти по всем мостам так, чтобы на каждом из них побывать только один раз и вернуться к тому месту, откуда началась прогулка. Многие горожане заинтересовались этой задачей, однако придумать решение никто не смог. Этот вопрос привлек внимание ученых из многих стран. Разрешить проблему удалось известному математику Леонарду Эйлеру. Леонард Эйлер, уроженец города Базеля родился 15 апреля, 1707 года. Научные заслуги Эйлера огромны. Он оказал влияние на развитие почти всех разделов математики и механики как в области фундаментальных исследований, так и в их приложениях. Леонард Эйлер не только решил эту конкретную задачу, но и придумал общий метод решения этих задач. Эйлер поступил следующим образом: он «сжал» сушу в точки, а мосты «вытянул» в линии. В результате получилась фигура, изображенная на рисунке.
Такую фигуру, состоящую из точек и линий, связывающих эти точки, называют графом. Точки A,B,C,D называют вершинами графа, а линии, которые соединяют вершины – ребра графа. На рисунке из вершин B,C,D выходят по 3 ребра, а из вершины A – 5 ребер. Вершины, из которых выходит нечетное число ребер, называют нечетными вершинами, а вершины, из которых выходит четное количество ребер, - четными.
2.Свойства графа.
Решая задачу про кенигсбергские мосты, Эйлер установил, в частности, свойства графа:
1.Если все вершины графа четные, то можно одним росчерком ( т.е. не 4
отрывая карандаша от бумаги и не проводя дважды по одной и той же линии ) начертить граф. При этом движение можно начать с любой вершины и окончить в той же вершине.
2.Граф с двумя нечетными вершинами тоже можно начертить одним росчерком. Движение нужно начинать от любой нечетной вершины, а заканчивать на другой нечетной вершине.
3.Граф с более чем двумя нечетными вершинами невозможно начертить одним росчерком.
4.Число нечетных вершин графа всегда четное.
5.Если в графе имеются нечетные вершины, то наименьшее число росчерков, которыми можно нарисовать граф будет равно половине числа нечетных вершин этого графа.
Например, если фигура имеет четыре нечетные, то её можно начертить, самое меньшее, двумя росчерками.
В задаче о семи кенигсбергских мостах все четыре вершины соответствующего графа нечетные, т.е. нельзя пройти по всем мостам один раз и закончить путь там, где он был начат.
Решение задач с помощью графов.
1. Задачи на вычерчивание фигур одним росчерком.
Попытки нарисовать одним росчерком пера каждую из следующих фигур приводят к неодинаковым результатам.
Если нечетных точек в фигуре нет, то она всегда поддается вырисовыванию одним росчерком пера, безразлично, с какого места ни начинать черчение. Таковы фигуры 1 и 5.
Если в фигуре имеется только одна пара нечетных точек, то такую фигуру можно нарисовать одним росчерком, начав черчение в одной из нечетных точек (безразлично в какой). Легко сообразить, что
5
вычерчивание должно оканчиваться во второй нечетной точке. Таковы
фигуры 2, 3, 6. В фигуре 6, например, вычерчивание надо начинать либо из точки А, либо из точки В.
Если фигура имеет более одной пары нечетных точек, то она вовсе не может быть нарисована одним росчерком. Таковы фигуры 4 и 7, содержащие по две пары нечетных точек. Сказанного достаточно, чтобы безошибочно распознавать, какие фигуры нельзя нарисовать одним
росчерком и какие можно, а также, с какой точки надо начинать вычерчивание.
Предлагаю начертить одним росчерком следующие фигуры.
Виды графов:
6
3. Использование графов в повседневной жизни:
Пожалуй, самым впечатляющим примером графа в современном мире выступает Интернет. Да-да, именно Интернет со всем его многообразием и сложностью форм является типичным графом. Его узлы - это адреса страничек и файлов, находящихся в сети, а ребра - гиперссылки, связывающие их в месте. С другой стороны, компьютеры, связанные вместе и образующие Всемирную паутину, также можно рассматривать как граф.
Другая сложная система, появившаяся гораздо раньше Интернета - глобальная общемировая телефонная сеть - также является графом. Если мы будем рассматривать все телефонные аппараты (а вернее, номера, соответствующие им) как узлы, а звонки, совершаемые с одного телефонного аппарата на другой, - как ребра, то получим громадную, сложную сеть, истинные размеры которой, наверное, не каждый сможет себе представить.
7
И глобальной телефонной сетью, и Интернетом очень сложно управлять, поскольку предсказать все возможные звонки и связи просто никто не в силах. Если вы делаете звонок из Питера в Нью-Йорк, существует множество способов соединить вас с тем абонентом, которому вы пытаетесь дозвониться, но телефонные станции должны выбирать кратчайший (с точки зрения графа) путь, соединяющий эти две точки. То же самое и в Интернете: для того чтобы броузер на вашем компьютере мог загрузить страничку, физически находящуюся в Южно-Африканской Республике, данные должны пройти через некоторое количество серверов, то есть у них будет иметься своеобразный маршрут в Сети. Он будет автоматически выбираться серверами таким образом, чтобы его длина была минимальной (опять-таки, с точки зрения графа), а данные по возможности проходили через незагруженные сегменты Сети. Из-за того, что нагрузка в разных участках Сети постоянно и случайным образом меняется, даже если вы загрузите с одного и того сайта страничку два раза подряд с интервалом в 1 секунду, она может прийти к вам двумя разными путями. Если быть более точными и вспомнить о том, что по Сети гуляют не странички в готовом виде, а пакеты с данными, и даже одна страничка может состоять из нескольких пакетов, то становится ясно: даже фрагменты одной страницы могут приходить в Интернете с одного компьютера на другой разными путями. Задача доставки пакетов данных из одного узла Сети (хоста) в другой называется задачей маршрутизации, и она отнюдь не является тривиальной.
Если спуститься с высокотехнологичных небес на землю, то все равно окажется, что графы и связанные с ними задачи окружают нас. Представьте себе, что вы - путешественник и вам нужно, двигаясь на машине по автодорогам, попасть из Петербурга в Берлин. Задача окажется не такой уж простой, как кажется на первый взгляд. В Европе дорог тысячи и тысячи, не то, что у нас где-нибудь в Центральной Сибири. Можно придумать несколько разнообразных маршрутов, пролегающих по территории разных государств и различных по своей длине. Они будут удовлетворять разным условиям в зависимости от тех задач, которые мы ставим: проехать из одной точки в другую максимально быстро, побывать по дороге в какой-нибудь стране, или, наоборот, объехать ее, так как нам не удалось получить визу; останавливаться каждую ночь в каком-нибудь городском мотеле и т. д. Задача нахождения оптимального пути между двумя географическими точками, удовлетворяющего определенным условиям, известна в теории графов под названием задачи нахождения кратчайшего пути. В данном случае в качестве узлов графа выступают перекрестки и развязки дорог, иногда они будут совпадать с городами и другими населенными пунктами. Ребра - это дороги, соединяющие узлы.
8
И последний интересный пример, связанный с графами. Это задача составления календаря. Предположим, есть некая организация, в которой, скажем, работают 500 человек. Каждый из них периодически встречается со своими коллегами в рамках различных мероприятий, кто-то - каждый день, кто-то - раз в неделю или раз в месяц. Составить общее расписание рабочих встреч для всех этих людей - это задача достаточно непростая, но и здесь нам может помочь теория графов. Общая схема будет сложнее, чем в предыдущих ситуациях. Самый простой вариант - разбить рабочее время каждого сотрудника на определенные интервалы, скажем, по 15 минут, и установить между ними для каждого сотрудника ориентированные последовательные связи, в результате получатся вертикальные цепочки из узлов - интервалов рабочего времени. Если два сотрудника в определенное время встречаются, нужно установить горизонтальные связи между соответствующими интервалами времени - узлами. К счастью, сегодня эту довольно утомительную работу выполняют компьютеры, однако совсем недавно расписания и календари составлялись вручную.
9
III. ЗАКЛЮЧЕНИЕ.
В результате работы над проектом я узнала, что Леонард Эйлер был основоположником теории графов, решил задачи с применением теории графов. Для себя сделала вывод, что теория графов находит применение в различных областях современной математики и её многочисленных приложений, в особенности это относится к экономике. Не приходится сомневаться в полезности ознакомления нас, учащихся, с основными понятиями теории графов. Решение многих математических задач упрощается, если удается использовать графы. Представление данных в виде графа придает им наглядность. Многие доказательства также упрощаются, приобретают убедительность, если воспользоваться графами. В особенности это относится к таким областям математики, как математическая логика, комбинаторика.
Таким образом, изучение этой темы имеет большое общеобразовательное, общекультурное и общематематическое значение. В повседневной жизни все большее применение находят графические иллюстрации, геометрические представления и другие приемы и методы наглядности. С этой целью изучения элементов теории графов полезно ввести в начальном и среднем звене школы, хотя бы во внеклассной работе, так как в программу по математике эта тема не включена.
10
V. СПИСОК ЛИТЕРАТУРЫ:
1. Альхова З.Н., Макеева А.В. «Внеклассная работа по математике».
2. Журнал «Математика в школе». Приложение «Первое сентября» № 13
2008г.
3. Я.И.Перельман «Занимательные задачи и опыты».- Москва: Просвещение, 2000 г.
11
Любимое яичко
Что общего у травы и собаки?
Как выглядело бы наше небо, если вместо Луны были планеты Солнечной Системы?
Бородино. М.Ю. Лермонтов
Девочка-Снегурочка