Исследовательская работа по математике "Тайны графов"

 

 

 

 

 

Исследовательская работа на тему:

 

«Тайны графов»

                                                                                                                                   

 

 

 

 

 

 

 

                   Автор:                                                                                                                

Жгунова Александра

ученица 8 класса,                                                       

Муниципального общеобразовательного

учреждения Стрехнинской  средней

общеобразовательной школы

Ишимского района, с. Стрехнино

 

Научный руководитель:

Рогова Юлия Владимировна

учитель математики

Муниципального общеобразовательного

 учреждения Стрехнинской  средней

образовательной школы

Ишимского района, с. Стрехнино

 

 

 

 

 

 

 

«Тайны графов»

Жгунова Александра

Россия, Тюменская область, Ишимский район, село Стрехнино,

Муниципальное общеобразовательное учреждение

Стрехнинская средняя общеобразовательная школа

8  класс

 

 

 

Краткая аннотация

 

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

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

представление данных в виде графа придает им наглядность и простоту.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

«Тайны графов»

Жгунова Александра

Россия, Тюменская область, Ишимский район, село Стрехнино,

Муниципальное общеобразовательное учреждение

Стрехнинская средняя общеобразовательная школа

8  класс

 

Аннотация

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

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

Научная новизна 

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

представление данных в виде графа придает им наглядность и простоту.

Объектом исследования является теория графов, и ее приложения

 Предметом исследования выбраны задачи с использованием графов при решении.

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

На основании выше сказанного мы ставим перед собой следующие цели:

Изучить теорию графов и рассмотреть решение задач с использованием «Графов».

Для достижения поставленной цели были определены следующие задачи:

  1.Изучить научно-популярную литературу по данному вопросу.

  2.Применить теорию графов при решении задач.

  3. Показать связь с другими областями знаний.

В исследовании и были использованы следующие методы:

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

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

«Тайны графов»

Жгунова Александра

Россия, Тюменская область, Ишимский район, село Стрехнино,

Муниципальное общеобразовательное учреждение

Стрехнинская средняя общеобразовательная школа

8  класс

 

 

Содержание

 

Введение                                                                                                                                      3                                                                                                                     

Глава 1. Теория графов                                                                                                            

   1.1. Понятие графа. Виды графов                                                                                            5                                                                                                                                                                                                                                                                                                                                                                                                                        

   1.2. Закономерности Эйлеровских графов                                                                              6

  1.3. Информационные модели на графах                                                                                 6                                                                    

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

    2.1. Задачи решаемые «одним росчерком пера»                                                                   8

    2.2. Задачи, решаемые в школьном курсе математики (задачи 5-9 классов)                      9

    2.3.   Задачи, решаемые с использованием информационных моделей на графах           10            

Заключение                                                                                                                                   12                                          

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

Приложение 1

Приложение 2

Приложение 3

 

 

 

3

 

«Тайны графов»

Жгунова Александра

Россия, Тюменская область, Ишимский район, село Стрехнино,

Муниципальное общеобразовательное учреждение

Стрехнинская средняя общеобразовательная школа

8  класс

 

 

 

Научная статья

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

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

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

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

Научная новизна 

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

представление данных в виде графа придает им наглядность и простоту.

Объектом исследования является теория графов, и ее приложения  Предметом исследования выбраны задачи с использованием графов при решении.

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

Изучить теорию графов и рассмотреть решение задач с использованием «Графов».

4

Для достижения поставленной цели были определены следующие  задачи:

  1.Изучить научно-популярную литературу по данному вопросу.

  2.Применить теорию графов при решении задач.

  3. Показать связь с другими областями знаний.

В исследовании и были использованы следующие методы:

Теоретические:

1)Изучение литературы по теории графов

2)Анализ и обобщение изученной информации

Эмпирические

1)Решение логических задач

2)Подбор задач

Практическая значимость

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

«Тайны графов»

Жгунова Александра

Россия, Тюменская область, Ишимский район, село Стрехнино,

Муниципальное общеобразовательное учреждение

Стрехнинская средняя общеобразовательная школа

8  класс

5

Глава 1.  Теория «Графов»

1.1. Понятие графа. Виды графов

    Слово «граф» в математике означает картинку, где нарисовано несколько точек, некоторые из которых соединены линиями. С дворянским титулом «граф» их связывает общее происхождение от латинского слова «графио» - пишу.  В математике определение графа дается так: Графом называется конечное множество точек, некоторые из которых соединены линиями. Точки называются вершинами графа, а соединяющие линии – рёбрами.  Примерами графов могут служить схемы авиалиний, метро, дорог, электросхемы, чертежи многоугольников. Использует графы и дворянство. Например, в генеалогическом дереве, вершины – члены рода, а связывающие их отрезки – отношения родственности. Первая работа по теории графов принадлежит Леонарду Эйлеру (1736 год), хотя термин «граф» впервые ввел в 1936 году венгерский математик Денеш Кениг.[ 1,5,6]  Граф, состоящий из «изолированных» вершин, называется нулевым графом. (рис.1)

 Графы, в которых не построены все возможные ребра, называются неполными графами. (рис.2)  Графы, в которых построены все возможные ребра, называются полными графами. (рис3)[ 5,1,2]

                                 Рис.1                                            Рис.2                                 Рис.3

Граф, в котором линии направленные, называется ориентированным графом.

Две вершины, соединенные дугой или ребрами, называются смежными.

Размеченный (взвешенный) граф – это граф, в котором с вершинами или с линиями связана некоторая дополнительная информация. Эта информация называется весом вершины или линии. Вес задается в виде надписи на вершине или линии, цвет, форма вершины, толщина, цвет или тип линии.

 

6

1.2. Закономерности Эйлеровских графов.

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

 

 

                                          Рис.4

Такими графы названы в честь учёного Леонарда Эйлера. [5,1]

Закономерность 1   
Невозможно начертить граф с нечетным числом нечетных вершин.
 Закономерность 2.

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

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

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

Теорема. Граф является эйлеровым тогда и только тогда, когда он связен и имеет не более двух нечетных вершин. [5,3]

Доказательство:

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

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

1.3. Информационные модели на графах

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

7

Граф- это средство для наглядного представления состава и структуры системы.

Вершина графа- это компоненты системы изображаемые кругами, овалами, прямоугольниками…

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

Ребра- это ненаправленная линия, связывающая компоненты собой определенным образом.

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

Сеть- это граф, в котором вершины связаны между собой по принципу «Многие ко многим».

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

8

«Тайны графов»

Жгунова Александра

Россия, Тюменская область, Ишимский район, село Стрехнино,

Муниципальное общеобразовательное учреждение

Стрехнинская средняя общеобразовательная школа

8  класс

 

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

2.1. Задачи решаемые «одним росчерком пера»

       Задача 1.   Можно ли нарисовать графы изображенные на рисунках (5и 6), не отрывая карандаш от бумаги и проводя каждое ребро ровно один раз? [2,]

 

 

                       Рис.5                                                                       Рис.  6

Решение:

Рис 5.   Можно, т. к. только 2 нечетные вершины.

Рис 6.   Нельзя, т. к. 4 нечетные вершины.

Задача 2. Можно ли обвести карандашом, не отрывая его от бумаги и не проходя по одной линии дважды, правильный пятиугольник с диагоналями? [3]

Решение: Если пятиугольник – граф и все вершины его четные – то это выполнить можно.

 

Рис. 7

Задача 3. Дан кусок проволоки, длиной 120 см. Можно ли, не ломая проволоки, изготовить каркас куба с ребром 10 см? [4]

Решение:

 

Рис. 8

Если куб – граф, тогда он имеет более двух нечетных вершин (8).

Значит, невозможно изготовить такой каркас, не ломая проволоки.

Задача 4. Не отрывая карандаша от бумаги и не проводя по одной линии дважды, начертить «открытый конверт» [2]

                                                                                        Рис. 9

 

9

Задача 5. Хулиган Вася решил прогуляться по парку и его окрестностям, так, чтобы при этом перелезть через каждый забор один раз. Сможет ли он это сделать?

Решение: Не сможет т.к. представив окрестности парка в виде графа, то мы насчитываем ровно нечетных вершин, а значит, хулиган не сможет выполнить задуманное. [4]

 

 

Рис 10

Задача 6.Определите, какие фигуры можно построить одним росчерком карандаша, а какие нельзя. [2,3,4] Решение: рис 1, 5  – можно, т.к. все вершины четные; рис 2, 3,6 -  можно, т.к  всего две нечетные вершины; рис 4,7 нельзя т.к. нечетных вершин больше, чем четных. (Приложение1:  рисунки с 1 – 7.); рис 8 -14 можно, т.к. все вершины четные.

 (Приложение 1: рисунки с 8-14.)

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

2.2. Задачи, решаемые в школьном курсе математики (задачи 5-9 классов)

Задача №1 Аркадий, Борис. Владимир, Григорий и Дмитрий при встрече обменялись рукопожатиями (каждый пожал руку каждому по одному разу). Сколько всего рукопожатий было сделано?

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

               

 

            Рис 11                                                      Рис 12

 

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

 

 

10

Задача№2 В трех различных домах живут три поссорившиеся между собой соседа. Недалеко от их домов имеются три колодца. Можно ли от каждого дома проложить к каждому из колодцев тропинку так, чтобы никакие две из них не пересекались?

      Решение:

Построим граф, вершины которого  А, Б, В, 1, 2, 3
соответствуют домам и колодцам условия задачи, и попробуем доказать, что девятую тропинку — ребро графа, не пересекающее остальные ребра, провести нельзя.

Рис 13                             Рис 14

Проведенные в графе на рисунке ребра А1, А2, A3 и В1,В2, ВЗ (соответствующие тропинкам от домов А и В ко всем колодцам). Построенный граф разбил плоскость на три области: X, У, Z. Вершина Б, в зависимости от ее расположения на плоскости, попадает в одну из этих трех областей. Если вы рассмотрите каждый из трех случаев «попадания» вершины Б в одну из областей X, Y или Z, то убедитесь, что всякий раз одна из вершин графа 1, 2 или 3 (один из колодцев) будет «недоступной» для вершины Б (т. е. нельзя будет провести одно из ребер Б1, Б2 или Б3. которое не пересекло бы уже имеющихся в графе ребер).Таким образом, ответ на вопрос задачи будет таким: «Нельзя!»(Именно в таких задачах действует теорема Понтрягина-Куратовского, где, в общем условие задачи можно свести к выяснению вопроса — является ли рассматриваемый граф плоским или нет).

Задача№2.Одежда

У Даши 4 блузки - красная, желтая, голубая и зеленая и две юбки – синяя и оранжевая. Сколько у нее вариантов подбора костюма?

Решение: (Приложение 2, рис 15)

Задача №3 Меню

В школьной столовой на первое можно заказать щи, гороховый суп и борщ, на второе котлету и рыбу, а на третье чай и морс. Сколько вариантов обеда можно получить из указанных блюд? (Приложение 2, рис 16)

2.3. Задачи, решаемые с использованием информационных моделей на графах.

Задача№1

 

11

Мы поставили перед собой цель, можно ли использовать графы при обработке результатов анкетирования. Одним из вопросов анкеты, которую мы предложили своим одноклассникам, был следующий: «Какие предметы (указать 2) ты хочешь изучать наиболее глубоко и основательно?». В анкетировании принимали участие 9 человек.

При  обработке ответов мы получили следующие данные: математику выбрали – 6 человек, русский и английский язык – 3 человека. Ответы на этот вопрос мы представили в виде следующего графа. (Приложение3, рис 17)

Задача №2. На графе изображена система возможного переливания крови. (Приложение3, рис 18)

Задача №3. Нарисуйте в виде графа систему, состоящую из одноклассников, между  которыми существует следующие взаимоотношения: дружат Андрей и Даша, Андрей и Маша, Даша и Коля, Коля и Андрей.(Приложение3, рис 19)

Задача №4. Укажите результат выполнения действий (Приложение 3, 20)

Задача №5. Построить граф классификации геометрических объектов. (Приложение 4, рис 21)Решение: Среди геометрических объектов можно выделить линии, плоские фигуры и объемные тела. Среди линий, в свою очередь, выделяются прямые, кривые и ломаные. Среди плоских фигур – круги, эллипсы, параллелограммы и трапеции и т. д.

Стоит отметить, что классификация, в данном случае, неполная. Например, отсутствует первичный геометрический объект, с которого все начинается, - точка. Обратим внимание на то, что приведенная классификация не является деревом. Объект «квадрат» имеет сразу двух предков – прямоугольник и ромб. Это означает, что любой квадрат обладает всеми свойствами прямоугольника и в то же время всеми свойствами ромба.

Задача №6. Какое значение получится на выходе схемы на рисунке если на вход подать:

А) число 3; Б) число 1; В) число 25? (Приложение 3, рис 22)

Задание №7. Найдите пропущенные числа: (Приложение 3, рис 23).

 

 

 

:

 

 

 

 

 

12

«Тайны графов»

Жгунова Александра

Россия, Тюменская область, Ишимский район, село Стрехнино,

Муниципальное общеобразовательное учреждение

Стрехнинская средняя общеобразовательная школа

8  класс

 

 

Заключение

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

13

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

1. Математика:Учеб. Для 5-6 кл. общеобразват. Учреждений / Г.В. Дорофеев, И.Ф. Шарыгин и др., Под ред. Г.В. Дорофеева, И.Ф. Шарыгина. – М.: Просвещение,2001 -368с.

 2. Нестеренко Ю.В. Задачи на смекалку. Ю.В. Нестеренко.- М.: Дрофа, 2005.-233с.

3. Перельман Я.И. Веселые задачи. Я.И. Перельман. - М.:  АсрельАст,2005. – 287с.

4. Сборник олимпиадных задач по математике, В. Г. Горбачев, 2004г.

5. Энциклопедия для детей. Математика. Том 11.  М.: Акванта+, 2001.

6. Я познаю мир. Математика.- М.: Аст, 1998

7.Н.С. Новиков. Дискретная математика. СПб.: Питер, 2001.

8. А.Г.Мордкович, П.В. Семёнов. События, вероятности, статистическая обработка данных. 7-9 класс.

9. Коннова Л.П. Знакомтесь, графы. – Самара,2001.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Приложение 1

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

                             

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Приложение 2

 Рис 15

 

 

 

 

 

 

Рис 16

 

 

 

 

 

 

 

 

 

 

Приложение 3

 

 

 

 

 

 

Рис 17

 

 

 

 

 

 

Рис 18    

 

Рис 19

Рис 20

Рис 21

    Рис 22

 

 

 

 

 

 

 

 

 

 

                                                            Рис 23

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Скачано с www.znanio.ru