проект. в мире графов. Исследовательская работа "В мире графов"
 Скачать 1.31 Mb.
|
|
Исследовательская работа "В мире графов"  Тематика: Математика Автор работы: Кучин Анатолий Николаевич Руководитель проекта: Куклина Татьяна Ивановна Учреждение: МБОУ "Основная общеобразовательная школа" п. Троицко-Печорск Респ. Коми Класс: 7 В своей исследовательской работе по математике "В мире графов" я постараюсь выяснить особенности применения теории графов при решении задач и в практической деятельности. Результатом моей исследовательской работы по математике о графах станет генеалогическое древо моей семьи. В исследовательской работе по математике я планирую познакомиться с историей теории графов, изучить основные понятия и виды графов, рассмотреть методы решения задач с помощью графов. Также, в исследовательском проекте по математике о графах я покажу применение теории графов в различных областях жизнедеятельности человека. Содержание Введение Глава 1. Знакомимся с графами 1.1. История графов. 1.2. Виды графов Глава 2. Возможности применения теории графов в различных областях повседневной жизни 2.1. Применение графов в различных областях жизни людей 2.2. Применение графов при решении задач 2.3. Генеалогическое древо – один из способов применения теории графов 2.4. Описание исследования и составление генеалогического древа моей семьи Заключение Использованная литература Приложения «В математике следует помнить не формулы, а процесс мышления». Е.И. Игнатьева Введение Графы повсюду! В моей исследовательской работе по математике на тему "В мире графов" речь пойдет о графах, которые, к аристократам былых времен никакого отношения не имеют. «Графы» имеют корень греческого слова «графо», что значит «пишу». Тот же корень в словах «график», «биография», «голография». Впервые с понятием “граф” я встретился при решении олимпиадных задач по математике. Трудности в решении этих задач объяснялись отсутствием этой темы в обязательном курсе школьной программы. Возникшая проблема стала главной причиной выбора темы данной исследовательской работы. Я решил подробно изучить всё, что связано с графами. Как широко используется метод графов и насколько важен он в жизни людей. В математике даже есть специальный раздел, который так и называется: «Теория графов». Теория графов является частью как топологии, так и комбинаторики. То, что это топологическая теория, следует из независимости свойств графа от расположения вершин и вида соединяющих их линии. А удобство формулировок комбинаторных задач в терминах графов привела к тому, что теория графов стала одним из мощнейших аппаратов комбинаторики. При решении логических задач обычно бывает достаточно трудно держать в памяти многочисленные факты, данные в условии, устанавливать связь между ними, высказывать гипотезы, делать частные выводы и пользоваться ими. Цель: выяснить особенности применения теории графов при решении задач и в практической деятельности. Объектом исследования является математические графы. Предметом исследования являются графы как способ решения целого ряда задач практической направленности. Гипотеза: если метод графов так важен, то обязательно найдется его широкое применение в различных областях науки и жизнедеятельности человека. Для реализации поставленной цели, мною были выдвинуты следующие задачи: 1. познакомиться с историей теории графов; 2. изучить основные понятия теории графов и виды графов; 3. рассмотреть способы решения задач с помощью графов; 4. показать применение теории графов в различных областях жизни человека; 5. создать генеалогическое древо моей семьи. Методы: наблюдение, поиск, отбор, анализ, исследование. Исследование: 1. были изучены ресурсы сети Интернет и печатные издания; 2. выписаны области науки и жизнедеятельности человека, в которых используется метод графов; 3. рассмотрено решение задач с помощью теории графов; 4. изучена методика составления генеалогического древа моей семьи. Актуальность и новизна. Теория графов в настоящее время является интенсивно развивающимся разделом математики. Это объясняется тем, что в виде графовых моделей описываются многие объекты и ситуации. Теория графов находит применение в различных областях современной математики и ее многочисленных приложениях, в особенности это относится к экономике, технике, к управлению. Решение многих математических задач упрощается, если удается использовать графы. Представление данных в виде графа придает им наглядность и простоту. Многие математические доказательства также упрощаются, приобретают убедительность, если пользоваться графами. Чтобы убедится в этом, мной и руководителем было предложено учащимся 5-9 классов, участникам школьного и муниципального туров Всероссийской олимпиады школьников, 4 задачи, при решении которых можно применить теорию графов (Приложение 1). Результаты решения задач таковы: Всего 15 учащихся (5 класс – 3 ученика, 6 класс - 2 ученика, 7 класс – 3 ученика, 8 класс - 3 ученика, 9 класс - 4 ученика) применили теорию графов в 1 задаче – 1, во 2 задаче – 0, в 3 задаче – 6, в 4 задаче – 4 учащихся. Практическая значимость исследования заключается в том, что результаты несомненно вызовут интерес у многих людей. Разве не пытался кто-то из вас построить генеалогическое дерево своей семьи? А как это сделать грамотно? Оказывается они решаются при помощи графов легко. Перейти к разделу 1.1. История графов Содержание: История графов Виды графов Применение графов в различных областях жизни людей Применение графов при решении задач Генеологическое древо – один из способов применения графов Описание исследования и составление генеалогического древа моей семьи Заключение. Литература Приложения Если Вам понравилась страница, поделитесь ссылкой с друзьями: История графов Пт, 27/01/2017 - 12:16 | nikolay Исследовательская работа: Исследовательская работа "В мире графов" Глава 1. Знакомимся с графами 1.1. История графов  Родоначальником теории графов принято считать математика Леонарда Эйлера (1707-1783, российский математик, швейцарец по происхождению, академик Петербургской и Берлинской академии наук).Он предложил изящное решение знаменитой задачи о 7 Кенигсбергских мостах в 1736 году, а также придумал общий метод решения подобных задач. В дальнейшем над графами работали Кениг (1774-1833), Гамильтон (1805-1865), из современных математиков - К. Берж, О. Оре, А. Зыков. Термин «граф» впервые ввел в 1936 году венгерский математик Денеш Кениг. Широкое развитие теория графов получила с 50-х годов 20 века в связи со становлением кибернетики и развитием вычислительной техники. Графом называется набор точек (эти точки называются вершинами), некоторые из которых объявляются смежными (или соседними). Считается, что смежные вершины соединены между собой ребрами (или дугами).  С помощью графов часто упрощалось решение задач, сформулированных в различных областях знаний: в автоматике, электронике, физике, химии и др. Помогают графы в решении математических и экономических задач. Перейти к разделу 1.2. Виды графов Виды графов Пт, 27/01/2017 - 12:32 | nikolay Исследовательская работа: Исследовательская работа "В мире графов" 1.2. Виды графов  Схема графа, состоящая из «изолированных» вершин, называется нулевым графом. (рис.2) Графы, в которых не построены все возможные ребра, называются неполными графами. (рис.3) Графы, в которых построены все возможные ребра, называются полными графами. (рис.4) Если на ребрах графа нанесены стрелочки, указывающие направление ребер, то такой граф называют направленным.  Стрелка от одной работы к другой на графе, изображенном на рисунке, означает последовательность выполнения работ. Нельзя начинать монтаж стен, не закончив строить фундамент, чтобы приступить к отделке, нужно иметь на этажах воду и т. д. Степени вершин и подсчет числа ребер. Количество рёбер, выходящих из вершины графа, называется степенью вершины. Вершина графа, имеющая нечётную степень, называется нечетной, а чётную степень – чётной. Если степени всех вершин графа равны, то граф называется однородным. Таким образом, любой полный граф — однородный.  На рисунке 5 изображен граф с пятью вершинами. Степень вершины А обозначим Ст.А. На рисунке: Ст.А = 1, Ст.Б = 2, Ст.В = 3, Ст.Г= 2, Ст.Д= 0. Сформулируем некоторые закономерности, присущие определенным графам. Закономерность 1. Степени вершин полного графа одинаковы, и каждая из них на 1 меньше числа вершин этого графа. Закономерность 2. Сумма степеней вершин графа число четное, равное удвоенному числу ребер графа. Эта закономерность справедлива не только для полного, но и для любого графа. ТЕОРЕМА. Число нечетных вершин любого графа четно. Заметим, что если полный граф имеет n вершин, то количество ребер будет равно n(n-1)/2. Граф, не являющийся полным, можно дополнить до полного с теми же вершинами, добавив недостающие ребра. Так, например, на рисунке 3 изображен неполный граф с пятью вершинами. На рисунке 4 ребра превращающие граф в полный граф изображены другим цветом, совокупность вершин графа с этими ребрами называется дополнением графа. Эйлеровы графы.  Граф, который можно нарисовать, не отрывая карандаша от бумаги, называется эйлеровым. (рис.6)Такими графы названы в честь учёного Леонарда Эйлера. Закономерность 3. (вытекает из рассмотренной нами теоремы). Невозможно начертить граф с нечетным числом нечетных вершин. Закономерность 4. Если все вершины графа четные, то можно не отрывая карандаш от бумаги («одним росчерком»), проводя по каждому ребру только один раз, начертить этот граф. Движение можно начать с любой вершины и закончить его в той же вершине. Закономерность 5. Граф, имеющий всего две нечетные вершины, можно начертить, не отрывая карандаш от бумаги, при этом движение нужно начать с одной из этих нечетных вершин и закончить во второй из них. Закономерность 6. Граф, имеющий более двух нечетных вершин, невозможно начертить «одним росчерком». Фигура (граф), которую можно начертить, не отрывая карандаш от бумаги, называется уникурсальной. Связные графы.  Граф называется связным, если любые две его вершины могут быть соединены путем, т. е. последовательностью ребер, каждое следующее из которых начинается в конце предыдущего. На рисунке 7, очевидно, изображен несвязный граф. Граф называется несвязным, если это условие не выполняется. Если, например, на рисунке между вершинами Д и Е провести ребро, то граф станет связным.(рис.8) Такое ребро в теории графов (после удаления которого граф из связного превращается в несвязный) называется мостом. Примерами мостов на рисунке 7 могли бы служить ребра ДЕ, A3, ВЖ и др., каждое из которых соединяло бы вершины «изолированных» частей графа. (рис.8) Несвязный граф состоит из нескольких «кусков». Эти «куски» называются компонентами связности графа. Каждая компонента связности является, конечно, связным графом. Отметим, что связный граф имеет одну компоненту связности. ТЕОРЕМА. Граф является эйлеровым тогда и только тогда, когда он связен и имеет не более двух нечетных вершин. Деревья. Деревом называется любой связный граф, не имеющий циклов. Договорились считать «деревом» и всякий граф, состоящий из одной (изолированной) вершины. Циклом называется путь, в котором совпадают начало с концом.  Если все вершины цикла разные, то такой цикл называется элементарным (или простым) циклом. Если же цикл включает в себя все ребра графа по одному разу, то такой цикл называется Эйлеровой линией (рис.9а). В графе на рис.9б два цикла: 1-2-3-4-1 и 5-6-7-5. Путем в графе от одной вершины к другой называется такая последовательность ребер, по которой можно проложить маршрут между этими вершинами. При этом никакое ребро маршрута не должно встречаться более одного раза. Вершина, от которой проложен маршрут, называется началом пути, вершина в конце маршрута — конец пути.  Висячей вершиной называется вершина, из которой выходит ровно одно ребро (рис.10). (кружком обведены висячие вершины). Свойство 1. Для каждой пары вершин дерева существует единственный путь, их соединяющий. Этим свойством пользуются при нахождении всех предков в генеалогическом дереве, например, по мужской линии, любого человека, чья родословная представлена в виде генеалогического дерева, которое является «деревом» и в смысле теории графов. Свойство 2. Всякое ребро в дереве является мостом. Действительно, после удаления любого ребра дерева, оно «распадается» на два дерева. Граф, в котором две любые вершины соединены ровно одним простым путём, является деревом. ЛЕММА (о висячей вершине). В каждом дереве есть висячая вершина. ТЕОРЕМА. В дереве число вершин на одну больше числа ребер. Изоморфизм. Плоские графы и теорема Эйлера. Два графа называются изоморфными, если у них поровну вершин, и вершины каждого графа можно занумеровать числами от 1 до n, так, чтобы вершины первого графа были соединены ребром тогда и только тогда, когда соединены ребром соответствующие вершины второго графа. Докажем, что графы изображенные на рисунке 11 изоморфны.  Пронумеруем вершины первого и второго графов от 1 и до 4 (рис.12). В первом графе соединены вершины 1 и 2, 2 и 3, 3 и 4, 1 и 4, 1 и 3, 2 и 4; заметим, что во втором графе также соединены вершины 1 и 2, 2 и 3, 3 и 4, 1 и 4, 1 и 3, 2 и 4, следовательно, данные графы изоморфны. Для того, чтобы выяснить, изоморфны ли два графа, нужно убедиться в том, что у них: одинаковое количество вершин если вершины одного графа соединены ребром, то и соответствующие им вершины другого графа тоже соединены ребром. Граф, который можно нарисовать так, чтобы его рёбра не пересекались нигде, кроме вершин, называются плоским или планарным. ТЕОРЕМА Эйлера. Для правильно нарисованного связного плоского графа имеет равенство: V-E+F=2, где V – число вершин, E - число рёбер, F – число кусков.(равенство V -E+F=2 обычно называют формулой Эйлера). Граф, каждая вершина которого соединена с ребром любой другой вершины, называется полным.  ТЕОРЕМА Понтрягина – Куратовского. Граф является плоским тогда и только тогда, когда он не содержит (в топологическом смысле) графа с шестью вершинами типа «домики-колодцы» и полного графа с пятью вершинами. (В основном используется в старинных задач о домах и колодцах, суть которой сводится к выяснению вопроса — является ли рассматриваемый граф плоским или нет, рис.13) Ориентированные графы. Существуют значительные классы практических задач, которые решить с помощью ранее рассмотренных типов графов невозможно. Так, например, схема дорог и площадей города изображается с помощью плоского графа. Но если нужно этой схемой воспользоваться с целью проезда по городу на автомашине, а движение на отдельных (или на всех) улицах одностороннее? Тогда могут помочь сориентироваться в этой ситуации стрелки, расположенные, например, прямо на ребрах - улицах рассматриваемой схемы (графа) города. Граф, на рёбрах которого расставлены стрелки, называется ориентированным.  Степенью выхода вершины ориентированного графа называется число ребер, для которых эта вершина является началом (число ребер, «выходящих» из вершины). Степенью входа вершины ориентированного графа называется число ребер, для которых эта вершина является концом (число ребер, «входящих» в вершину). Так, на рисунке 15 изображен ориентированный граф АБВГД. Степени входа и выхода некоторых его вершин такие: Ст.вх.А=2, Ст.вых.А=1 Ст.вх.В=2, Ст.вых.В=0 Ст.вх.Д=1, Ст.вых.Д=3.  Путем, в ориентированном графе от вершины А1 к вершине An называется последовательность ориентированных ребер A1A2, A2A3, ..., Аn-1Аn, в которой конец каждого предыдущего ребра совпадает с началом следующего и каждое ребро встречается в этой последовательности только один раз. На рисунке.15 показаны примеры путей в ориентированном графе. Причем, первые два пути простые — ни одна из вершин не содержится в нем более одного раза. Третий путь не является простым ,т. к. через вершину Г путь «проходил» дважды. Ориентированным циклом называется замкнутый путь в ориентированном графе. На рисунке 15 приведены примеры ориентированных циклов в последних двух графах. Цикл, как и любой другой путь в графе, имеет длину, которая определяется числом ребер в этом пути.  Так, на рисунке 16 пути от А к Д могут быть различны и иметь различную длину. Первый путь имеет длину 2, второй - 3, а третий — 4. Длина «кратчайшего пути» между двумя вершинами называется расстоянием между ними. Так расстояние между вершинами А и Д на графе рисунка 16 равно 2; записывают так: S(АД)=2. Если в ориентированном графе нельзя «пройти» от одной вершины до другой, то расстояние между ними называют бесконечным(обозначают значком бесконечности). Так, расстояние между вершинами Б и Д графа, представленного на рисунке 17 бесконечно: S(БД) = ∞ Ориентированные графы в экономике активно используются в сетевом планировании, в математике — в теории игр, теории множеств; при решении многих задач, в частности, комбинаторных. Перейти к разделу 2.1. Применение графов в различных областях жизни людей Применение графов в различных областях жизни людей Пт, 27/01/2017 - 16:07 | nikolay Исследовательская работа: Исследовательская работа "В мире графов" |