Тайны графов

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

«Средняя общеобразовательная школа 10»

 

 

 

 

Информационно- познавательный проект по математике

На тему: «Тайны графов»

 

 

                                                                                                                                   

 

 

 

Выполнил ученик 8 «А» класса:

Рахмонова Милана Орзуевна

Руководитель: учитель математики Казакова

Надежда Сергеевна

 

 

 

 

 

г. Кыштым, 2021 г

 

Содержание

 

Введение……………………………………………………………………………………3                                                                                                                                                              

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

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

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

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

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

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

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

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

2.4 Анкетирование в 8а классе на тему «Что такое граф?» ……………………………..11

Заключение………………………………………………………………………………….13

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

Приложение

 

 

 

 

 

 

 

 Введение

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

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

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

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

Цель моей проектной работы: изучение теории графов и рассмотрение решение задач с использованием «Графов».

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

  1.Изучить научно-популярную литературу по теме «Графы».

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

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

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

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

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

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

·         Подбор задач

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

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

 

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

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

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

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

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

 

 

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

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

 

 

                                          Рис.4

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

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

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

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

Закономерность 4.

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

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

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

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

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

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

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

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

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

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

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

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

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

 

 

 

 

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

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

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

 

 

 

Рис.5                                     Рис.  6

Решение:

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

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

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

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

 Рис. 8

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

Решение: Если куб – граф, тогда он имеет более двух нечетных вершин (8). Значит, невозможно изготовить такой каркас, не ломая проволоки.  Рис. 9

 

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

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

 

Рис 10

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

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

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

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

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

            

Рис 11                              Рис 12

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

Если подсчитать число ребер графа, изображенного на рисунке справа, то это число и будет равно количеству совершенных рукопожатий между пятью молодыми людьми.     Их 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 блузки - красная, желтая, голубая и зеленая и две юбки – синяя и оранжевая. Сколько у нее вариантов подбора костюма?  Решение: (рис 15)

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

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

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

Задача№1

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

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

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

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

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

Задача №5. Построить граф классификации геометрических объектов. (рис21)

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

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

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

А) число 3; Б) число 1; В) число 25? (рис 22)

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

2.4 Анкетирование в 8а классе на тему «Что такое граф?»

1.Знаете ли вы, что такое граф в математике?

Вывод: большинство в классе не знают, что такое граф в математике

2.Можно ли нарисовать графы изображённые на рисунке, не отрывая карандаш от бумаги и проводя каждое ребро один раз?

      

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

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

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

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

В задаче 65% (12 человек) учеников 8а класса справились. 25% (5 человек) учеников справились, но с моей помощью, я им показала пример на доске. А 10% (6 человек) не поняли, как решать данную задачку.

 

 

 

 

 

 

 

 

 

 

 

 

 

Заключение

 

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

 

 

 

 

 

 

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

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

 

 

 

 

 

 

 

 

 

 

 

 

  Рис 15

 

 

                                                                                                                                                              Рис 16 

 

 

 

 

 

 

                                        Рис 17

 

Рис 18                                                                                                                                               Рис 19

 

                  Рис 20

Рис 21

                   Рис 22

 

                                                                                                                                           Рис 23

 

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