Работу выполнила Ученица 9 «а» класса Хребтова Мария Руководитель Шакирова Г.К., I кв. категория Новосибирская область Искитимский район Муниципальное образовательное учреждение «Средняя общеобразовательная школа ст. Евсино» уч.год

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

Вступление, цель и задачи; Как появились графы; Основные понятия и виды графов; Применение теории графов; Вывод; Используемые источники.

Научиться применять теорию графов на практике. Выяснить, что такое графы и где они применяются; Узнать, как решаются задачи на применение теории графов; Научиться самой составлять подобные задачи.

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

Толчок к развитию теория графов получила на рубеже ХIX и ХХ столетий, когда резко возросло число работ в области топологии и комбинаторики, с которыми ее связывают самые тесные узы родства. Графы стали использоваться при построении схем электрических цепей и молекулярных схем. Как отдельная математическая дисциплина теория графов была впервые представлена в 1936 году в монографии австрийского математика Д.Кинега «Теории конечных и бесконечных графов», к сожалению, не переведённой на русский язык. Д. Кинег

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

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

A B C D E изолированная вершина, нуль-граф полный граф неполный граф Начало пути Конец пути

Родившись при решении головоломок и занимательных игр теория графов стала в настоящее время простым, доступным и мощным средством решения вопросов, относящихся к широкому кругу проблем. Графы буквально вездесущи. За последние четыре десятилетия теория графов превратилась в один из наиболее бурно развивающихся разделов математики.

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

Оказывается, даже предложение можно представить в виде графа. Рассмотрим это на примере предложения из «Капитанской дочки» А.С. Пушкина: (Белогорская 1 крепость 2) (находилась 3 (в 4 (сорока 5 верстах 6)) от 7 Оренбурга 8)). L1 =(x1, x2, x3, x4, x5, x6, x7, x8) L2=(x1, x2) L3=(x3, x4, x5, x6, x7, x8) L4=(x4, x5, x6) L5=(x5, x6) x1x2 L1 L2 L3 L4 L5 x3 x4x5x6

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

При составлении расписания на субботу в 10 классе преподаватели высказали просьбы: 1. Учитель математики: «Желаю иметь первый или второй урок». 2. Учитель истории: «Желаю иметь первый или третий урок». 3. Учитель литературы: «Желаю иметь второй или третий урок». Какое расписание может быть составлено, если по каждому предмету может быть только один урок? Если предположить, что 1 й урок – математика, то 2 й – литература, а 3 й – история. Если предположить, что 1 й урок – история, то 2 й – математика, а 3 й – литература. Учитель математики Учитель истории Учитель литературы 1 урок 2 урок 3 урок

В физике анализ электрических цепей распознаётся методом графов, также применяется в классической электродинамике СТО, энергетике, радиоэлектронике. В химии эта теория используется для составления формул, для исследования реакций.

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

Одним из самых важных разделов в информатике являются графы. Многие связи записываются с их помощью. В соревнованиях по гимнастике на первенство школы участвуют Алла, Валя, Таня и Даша. Болельщики высказали предположения о возможных победителях. 1 й болельщик: «Первой будет Таня, Валя будет второй». 2 й болельщик: «Второй будет Таня, Даша - третьей». 3 й болельщик: «Алла будет второй, Даша - четвертой». По окончанию соревнований оказалось, что в каждом предположении одно истинно, а другое – ложно. Какое место заняла каждая из девочек, если все они оказались на разных местах?

Из этого следует, что Таня – первая, Алла – вторая, Даша – третья, Валя – четвертая. Т 1 В 2 Т 2 Д 3 А 2 Д 4

С помощью графов можно определить и родственные связи. Такой граф – генеалогическое древо. И. П. Толстой 1726 П. М. Ртищева 1748 Граф А. Т. Толстой Княжна А. И. Щёткина Князь С. Ф. Волков М. Д. Чаадаева Граф И. А. Толстой Княжна П. Н. Горчакова Князь Н. С. Волконский Княжна Е. Д. Трубецкая Граф Николай Ильич Толстой Княжна Мария Николаевна Волконская Граф Лев Николаевич Толстой

Фартышева Марья Ефтифеевна Усольцев Степан Дмитриевич Михаил Иванович Чукмасов Усольцева Пелагея Степановна Чукмасова Мария Михайловна Агарин Григорий Захарович Чукмасова Надежда Михайловна Щукин Михаил Иванович Агарина Галина Григорьевна Кошелев Алексей Анатольевич Агарина Лидия Григорьевна Тимонин Александр Кузьмич Тимонина Ирина Александровна Хребтов Сергей Владимирович Хребтова Мария Сергеевна Кошелев Анатолий Алексеевич Мусякаева Вера Аллэмовна Кошелева Маргарита Алексеевна Кошелева Анна Алексеевна

Чтобы легче решать задачи надо знать следующий алгоритм: 1. О каком процессе идет речь в задаче? 2. Какие величины характеризуют этот процесс? 3. Каким соотношением связаны эти величины? 4. Сколько различных процессов описывается в задаче? 5. Есть ли связь между элементами? Надо отвечать на эти вопросы, анализировать условие задачи и записывать его схематично.

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

«Введение в теорию графов», Уилсон Р «Графы и их применение», Верезина Л.Ю «Графы и их применение», Оре Ойстин М, 1965 «За страницами учебника математики (открытые уроки, математические кружки, подготовка к олимпиадам)», С.А. Литвинова, Л.В. Куликова, С.В. Шиловская, Г.Ю. Тараева, О.Л. Безрукова, 2-е издание, дополненное, Волгоград: «Панорама», 2007 «Конечные графы и сети», Басанер Р. И Саити Т. М, 1971 «Математика помогает лингвистике», Крейдлин Г.Е Математика. Еженедельное учебно-методическое приложение к газете «Первое сентября», 15 (16-22 апреля 2001 г), Москва, издательство «ОЦ КУДИЦ-ОБРАЗ» «Основа теории графов», Зыков Л.А «Теория графов и её применение», Берж К «Теория графов и её применение», Липатов Е. П htm