Графы

Ломоносовский муниципальный район

МОУ Кипенская средняя общеобразовательная школа

Тема проекта: Теория графов.

Решение задач с помощью графов

Математика

                                                                   д.Кипень

2014 год

Цель проекта:  сформировать представление о значении теории графов как средства описания действительности; научиться применять полученные знания в реальной жизни.

Задачи: изучить и проанализировать литературу, содержащую задачи теории графов и их решение; экспериментально проверить, как можно применять изученные методы к решению нетипичных математических задач

Ожидаемые результаты: формирование логико-алгоритмического и системно-комбинаторного мышления; формирование опыта исследовательской деятельности

Гипотеза: Если теорию графов сблизить с практикой, то можно получить самые благотворные результаты, например, решить задачи по нахождению длины кратчайшего пути или составить блок-схему решения  задачи по программированию, физике, математике, логике

План проекта:

1. Введение
2. История возникновения графов
3. Применение графов в практической деятельности
4. Определение графа
5. Полный и неполный граф
6. Неориентированный граф. Ориентированный граф.
7. Задачи, решаемые с помощью неориентированного графа
8. Задачи, решаемые с помощью ориентированного графа
9. Взвешенные графы. Задачи, решаемые с помощью взвешенного графа
10. Четные и нечетные вершины графа
11. Решение задачи о Кенигсбергских мостах
12. Заключение и выводы
13. Список литературы

1. Введение

 «Графы» имеют корень греческого слова «графо», что значит «пишу». Тот же корень в словах «график», «биография», «голография». Изучая теорию графов на уроках математики я решил  узнать как можно применить теорию графов на практике, в жизни.

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

              В последние десятилетия происходит значительное увеличение интереса к теории графов. Зародившись более 200 лет назад при решении головоломок и занимательных задач, она стала простым, доступным  средством решения широкого круга важных практических задач. Особенно велико значение графов  при создании математических моделей. Построенные модели можно эффективно исследовать с помощью компьютера.

               Первая работа по теории графов, принадлежит известному швейцарскому математику  Л. Эйлеру. Основы теории графов как математической науки он заложил рассматривая задачу о кенигсбергских мостах. Сегодня эта задача стала классической.

               Ученый Леонард Эйлер принадлежит к числу гениев!

                  Задача о Кенигсбергских мостах:     Бывший Кенигсберг (ныне Калининград) расположен на реке Прегель. В пределах города река омывает два острова. С берегов на острова были перекинуты мосты. Старые мосты не сохранились, но осталась карта города, где они изображены. Кенигсбергцы предлагали приезжим следующую задачу: пройти по всем мостам и вернуться в начальный пункт, причём на каждом мосту следовало побывать только один раз.

3. Применение  графов

Графы эффективно используются в теории планирования и управления, теории расписаний,  экономике, биологии, медицине, географии.

    Широкое применение находят графы в таких областях, как программирование,  в решении вероятностных и комбинаторных задач.

Медицинский граф:

Граф программиста:

Граф расписание

   Многие структуры, представляющие практический интерес в математике и информатике  представлены графами.

  Например, строение сайта можно смоделировать при помощи графа , в котором вершины — это страницы, а дуги — гиперссылки

4. Определение графа

Граф - это картинка из точек, соединенных линиями

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

Вершины графа - это те самые точки

Граф состоит из вершин, связанных линиями.

Направленная линия (со стрелкой) называется дугой.

Линия ненаправленная (без стрелки) называется ребром.

Линия, выходящая из некоторой вершины и входящая в неё же, называется петлей.

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

Это граф. Пять компьютеров являются вершинами, а соединения (передача сигналов) между ними – ребра. Заменив в правой части компьютеры на вершины, в левой мы получим более привычный граф.

Он имеет 10 ребер и 5 вершин.

5. Полный и неполный граф

Соседние вершины (или, попросту, соседи) - это две вершины графа, соединенные ребром;

  Полный граф - это граф, в котором любые две вершины соседние.

Примеры полных и неполных графов:

6. Неориентированный граф.  Ориентированный граф  

Граф, вершины которого соединены ребрами. С помощью таких графов могут быть представлены схемы двухсторонних (симметричных) отношений.

Граф, вершины которого соединены дугами.

С помощью таких графов могут быть

 представлены схемы односторонних отношений.

7. Задача, решаемая с помощью неориентированного графа

Задача: В бутылке, стакане, кувшине и банке находятся молоко, лимонад, квас и вода. Известно, что вода и молоко не в бутылке, сосуд с лимонадом стоит между кувшином и сосудом с квасом, в банке – не лимонад и не вода. Стакан стоит около банки и сосуда с молоком. Куда налита каждая жидкость?

Ответ: в кувшине-молоко, в банке-квас, в стакане-вода, в бутылке-лимонад.

Ещё одна задача, решаемая с помощью неориентированного графа: Аркадий, Борис, Владимир, Григорий и Дмитрий при встрече обменялись рукопожатиями (каждый пожал руку каждому по одному разу). Сколько всего рукопожатий было сделано? Ответ: 10

8. Задача, решаемая с помощью ориентированного графа:

 По окончании деловой встречи специалисты обменялись визитными карточками (каждый вручил свою карточку каждому). Сколько всего визитных карточек было роздано, если во встрече участвовали: 1) 3 человека;  2) 4 человека;  3) 5 человек?

Ответ: 6; 12; 20

9. Взвешенные графы

Взвешенный граф  - это граф, некоторым элементам которого (вершинам, ребрам или дугам) сопоставлены числа. Наиболее часто встречаются графы с помеченными ребрами. Числа-пометки носят различные названия: вес, длина, стоимость.

Примеры взвешенных графов:

 Взвешенный  граф по заданной таблице (она еще называется  весовой  матрицей)

 может быть изображен  по-разному;  например,  той  же  таблице   соответствует  граф, показанный на рисунке справа от нее и слева

Длина пути во взвешенном графе

Длина пути во взвешенном (связном) графе - это сумма длин (весов) тех ребер, из которых состоит путь. Расстояние между вершинами - это, как и прежде, длина кратчайшего пути. Например, расстояние от Санкт-Петербурга до Омска во взвешенном графе,  

равна – 2760 км

Еще задача: Пусть, в стране есть несколько городов и дорог, соединяющих эти города. При этом у каждой дороги есть длина. Вы хотите попасть из 3 города в 6 , проехав как можно меньший путь. Какова длина пути?  Ответ: 7

10. Четность и нечетность вершин графа

Вершины, из которых выходит нечетное число ребер, называют нечетными вершинами, а вершины, из которых выходит четное количество ребер, - четными.

 Если все вершины графа четные, то можно одним росчерком ( т.е. не отрывая карандаша от бумаги и не проводя дважды по одной и той же линии ) начертить граф. При этом движение можно начать с любой вершины и окончить

                                              в той же вершине.

Графы, которые можно изобразить одним росчерком пера

11. Задача о Кенигсбергских мостах

Так как граф содержит четыре нечетные вершины,

то его нельзя начертить одним росчерком,

 значит, и пройти по всем семи мостам так, чтобы на каждом из них побывать лишь по одному разу

 и вернуться к тому месту, откуда начал маршрут – нельзя

12. Выводы:

Теория графов очень интересная тема. Я понял,  как решаются многие логические задачи  -   легко и быстро.

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

Таким образом, изучение этой темы имеет большое общеобразовательное, общекультурное и общематематическое значение. В повседневной жизни все большее применение находят графические иллюстрации, геометрические представления и другие приемы и методы наглядности.

Я научился  анализировать дополнительную литературу и применять полученные знания на практике.

Свои исследования я продолжу.

13. Список литературы:

Незнайка в стране графов, 6-8 классы,  Мельников О.И., 2007

Иванов С.В., Математический кружок  М.: Наука, 1988.

Кирюхин В.М., Лапунов А.В., Окулов С.М. Задачи по информатике.

Международные олимпиады 1989 – 1996: Для факультативов по информатике в старших классах. – М.: ABF, 1996

Журнал «Математика в школе». Приложение «Первое сентября» № 13        2008г.

 Перельман Я.И. «Занимательные задачи и опыты».- Москва: «Просвещение», 2000 год.

Кушниренко А.Г., Лебедев Г.В. Программирование для математиков.

Интернет источники:

Сайт К. Полякова: http://krolyakov.narod.ru

официальный сайт www.ege.ru