Размещено на http://www.allbest.ru/

Государственное бюджетное общеобразовательное учреждение города Москвы "Инженерно-техническая школа имени дважды Героя Советского Союза П.Р. Поповича"

Исследовательская работа

на тему: Графы

Выполнил: Ученик 9 «Г» класса Фонин Дмитрий

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

Быстрова Мария Владимировна

Москва 2018



Оглавление

Введение

1. Его величество граф

1.1 История возникновения теории графов

1.2 Понятие графа

1.3 Виды графов и их элементы

2. Графы вокруг нас

2.1 Теория графов в транспортных, коммуникационных и геоинформационных системах

2.1 Графы в медицине

2.2 Теория графов в биологии

2.3 Теория графов в химии

2.4 Графы в физике и технике

2.5 Графы в информатике

2.6 Лабиринты

2.7 Графы в астрономии

2.8 Теория графов в истории

2.9 Теория графов в музыке

2.10 Теория графов в литературе

2.11 Теория графов в искусстве

3. Собственные разработки по теории графов

3.1 Задачи

3.2 Наше видеопособие для уроков математики

3.3 Эксперимент с дошкольниками

Заключение

Приложения

Используемая литература и ресурсы



Введение

граф транспортный коммуникационный геоинформационный

Проживая в таком огромном мегаполисе как Москва тема Графы стала сегодня неотъемлемой частью нашей жизни. Каждый проживающий в Москве ежедневно совершает переезды в общественном транспорте по нескольку раз в день и тратит огромное количество времени на эти поездки. Так проблема решения задач Графов о кратчайшем пути стала одной из самых актуальных и важнейших задач, которую мы решаем ежедневно при планировании маршрута. Я участвую в олимпиаде «Музеи. Парки. Усадьбы.», поэтому решение данной задачи для меня стала во главе угла как одно из основных условий при планировании своего времени. Над решением таких задач я задумывался уже давно, но подтолкнуло меня к изучению этой темы приезд моих родственников в гости к нам, когда надо было показать им достопримечательности Москвы в довольно короткий срок. Обычно я пользовался GPS-навигаторами, осуществляя поиск кратчайшего пути между станциями метро и перекрестками. Но в тот момент телефона у меня не оказалось и мне пришлось на ходу вычислять кратчайшие пути наших экскурсий. В качестве вершин выступили перекрестки, а дороги являлись ребрами, которые лежат между ними. Если сумма длин дорог между перекрестками минимальна, тогда найденный путь самый короткий.

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

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

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

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

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

1. Изучить научно-популярную литературу и Интернет-ресурсы о теории графов:

a. Изучить историю возникновения теории графов.

b. Изучить основные понятия в теории графов и виды графов.

c. Изучить, как и где применяются графы.

d. Научиться применять теорию графов на практике.

2. Провести занятия с дошкольниками

3. Составить видеорешение задачи и выложить ее в сеть интернет.

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

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

1. Анализ информации о развитии и современном состоянии темы исследования.

2. Синтез и интерпретация изученной информации.

3. Дедуктивный метод проверки выдвинутой гипотезы.

4. Методы сравнения и аналогии.

5. Метод классификации.

6. Обобщение при формулировке выводов исследования.



1. Его величество граф

1.1 История возникновения теории графов

Родоначальником теории графов считается Леонард Эйлер, знаменитый теоретик, математик. Родился в Швейцарии. Написал множество трудов по математике. В школьной программе изучают теорему Эйлера о многогранниках, которая гласит: «Для любого простого многогранника В-Р+Г=2, где В -- число вершин, Р -- число рёбер, Г -- число граней».

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

13 марта 1736 года Леонард Эйлер пишет письмо итальянскому математику и инженеру Мариони, авторитетному инженеру, бывшему тогда придворным астрономом в Берлине, с которым Эйлер вёл переписку по самым разным вопросам науки и техники. Он пишет о том, что смог найти правило, чтобы определить, можно ли пройти по всем мостам, не проходя дважды ни по одному из них. Таким образом, Эйлер стал первым человеком, который смог сформулировать решение задачи о семи мостах. При этом Эйлер пишет: «Если бы можно было привести здесь другие, более серьезные задачи, этот метод мог бы принести ещё большую пользу и им не следовало бы пренебрегать. Петербург, 13 марта 1736»

Таким образом получается, что в 2016 году исполняется 280 лет со дня зарождения теории графов. Казалось бы, ребус, детская забава -- а из неё выросла целая наука -- теория графов.

В дальнейшем над графами работали Кениг (1774-1833), Гамильтон (1805-1865), из современных математиков -- К. Берж, О. Оре, А. Зыков. Термин «граф» впервые ввел в 1936 году венгерский математик Денеш Кениг. Широкое развитие теория графов получила с 50-х годов 20 века в связи со становлением кибернетики и развитием вычислительной техники.

1.2 Понятие графа

Приступив к изучению теории графов, мы проанализировали учебную литературу. Это:

1) учебник Информатика и ИКТ, 9 класс. Семакин И. Г.

2) Уилсон Р. Введение в теорию графов.

3) Оре О. Графы и их применение.

4) Клауди Альсина. Карты метро и нейронные сети. Теория графов.

5) Анализируя тексты пособий, мы составили краткий конспект изученного и подобрали свои примеры. Ниже -- результаты моего теоретического исследования.

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

С дворянским титулом «граф» их связывает общее происхождение от латинского слова «графио» - пишу.

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

Использует графы и дворянство. Например, в генеалогическом дереве, вершины - члены рода, а связывающие их отрезки - отношения родственности. В качестве примера можно привести генеалогическое дерево великого русского поэта А.С.Пушкина. (см. Приложение 2.)

1.3 Виды графов и их элементы

Схема графа, на рисунке 2 состоящая из «изолированных» вершин, называется нулевым графом.

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

Графы, в которых построены все возможные ребра, называются полными графами. Этому определению соответствует граф на рисунке 4.

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

рис. 5

Граф называется несвязным, если первое условие не выполняется (рис.6).

рис. 6

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

Граф, в котором две любые вершины соединены ровно одним простым путём, является деревом (рис.7). Чаще всего они встречаются при составлении родословных. Я составил своё родословное дерево (см.Приложение 3).



рис. 7

После удаления любого ребра дерева, оно «распадается» на два дерева. Кружком обведены висячие вершины.

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

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

В-Р+Г=2.

В качестве примера можно рассмотреть следующую задачу:

В стране «Озерной» - 7 озер,

Каналы их соединяют.

А между ними - острова,

И сколько их - никто не знает

Решение. Рассмотрим граф, в котором вершины соответствуют островам, а рёбра -- каналам. Полученный граф будет плоским и связным, значит, для него выполняется формула Эйлера: В -- Р + Г = 2. Для нашего графа В = 7, Р = 10. Подставляя в формулу, получаем 7 -- 10 + Г = 2. Отсюда следует, что Г = 5, то есть, рёбра графа разбивают плоскость на 5 частей. Островам соответствуют все грани, кроме внешней (она бесконечно большая во все стороны и острову соответствовать не может), значит, их 4.



Рис. 8

Большой интерес вызывают графы, которые можно нарисовать, не отрывая карандаша от бумаги. Их называют эйлеровыми в честь учёного Леонарда Эйлера.(рис.9)

Размещено на http://www.allbest.ru/

Рис. 9

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

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



рис. 10

На рисунке 10: Ст.А = 1, Ст.Б = 2, Ст.В = 3, Ст.Г= 2, Ст.Д= 0.

Если степени всех вершин графа равны, то граф называется однородным. Таким образом, любой полный граф -- однородный. Соединив А с Б и А с Д получим полный, однородный граф.



2. Графы вокруг нас

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

2.1 Теория графов в транспортных, коммуникационных и геоинформационных системах

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

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

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

2.1 Графы в медицине

Размещено на http://www.allbest.ru/

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

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

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

2.2 Теория графов в биологии

Деревья играют большую роль в биологической теории ветвящихся процессов. Самый простой пример -- размножение бактерии или процесс гаметогенеза у человека. Размножение бактерий это одна из разновидностей ветвящихся процессов. Предположим, что через определенный промежуток времени каждая бактерия либо делится на две новые, либо погибает. Тогда для потомства одной бактерии мы получим двоичное дерево. Нас будет интересовать лишь один вопрос: в скольких случаях n-е поколение одной бактерии насчитывает ровно k потомков? Математически вычисляемое на основе значений предыдущих членов последовательности соотношение, обозначающее число необходимых случаев, известно в биологии под названием процесса Гальтона-Ватсона. Его можно рассматривать как частный случай многих общих формул

Яркий пример дерева -- схема дивергенции форм на рисунке Чарльза Дарвина.



2.3 Теория графов в химии

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

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

Компьютерная химия (хеминформатика) и биоинформатика -- сравнительно молодая область химии и биологии. Их основой является теория графов и комбинаторика. На стыке трёх наук -- химии, биологии, информатики, -- решаются проблемы, для которых раньше необходимы были годы исследований, тысячи подопытных животных и добровольцев, испытывавших на себе новые синтетические лекарственные средства. Сейчас эти дорогостоящие процедуры решаются с помощью различных компьютерных программ и онлайн-сервисов. О важности этого полезного инструмента говорят темы исследований: «Компьютерное прогнозирование противоопухолевого действия фармакологически активных веществ на клеточные линии рака молочной железы человека», «Компьютерная оценка нежелательных мишеней лекарственных соединений, связанных с индукцией инфаркта миокарда» и др.

Специальность «Хемоинформатика и молекулярное моделирование» -- одно из самых молодых и востребованных направлений на инновационных предприятиях.

2.4 Графы в физике и технике

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

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

2.5 Графы в информатике

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

Дерево каталогов

Конфигурации локальной вычислительной сети по типу «звезда» и «кольцо»:



2.6 Лабиринты

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

«Живой» лабиринт я нашел в Москве в парке 50-летия Октября

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

2.7 Графы в астрономии

Чтобы выделить отдельные созвездия из общего «звездного хаоса», первые астрономы условно соединили наиболее яркие звёзды линиями (построили графы). Всё множество видимых звёзд разделилось на отдельные группы - созвездия. Если граф ассоциировался с каким-либо знакомым объектом, то созвездию давалось соответствующее название.

Когда кругом густая тьма,

А бездна звездами мерцает,

Струится с неба красота

И счастьем душу наполняет.

Какой порядок иль закон

Творит вселенское величье?

Но нам художник незнаком,

Скрывает тьма его обличье.

Мы, ведь, знаем то, что звезды

Группируются в созвездья

Волопаса, Девы, Рака,

Скорпиона и Стрельца.

А отрезки между ними -

Это просто ребра графа,

От начала до конца.



2.8 Теория графов в истории

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

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

В программе MyHeritage мной было составлено полное генеалогическое дерево моей семьи. (Приложение 4) Теперь мне на почту приходят напоминания о предстоящих семейных праздниках, днях рождения родственников. Это очень удобно и помогает помнить мне о своих корнях.

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

Но всё-таки, существует ли такая область человеческих занятий, в которой теория графов, графы не играют никакой роли? Например, есть ли графы в искусстве, в музыке, поэзии?

2.9 Теория графов в музыке

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

Занимаясь в музыкальной школе, мне известно, что в музыке и математике много общего. Например, монохроматическая гамма -- это последовательность логарифмов, а среди учёных, особенно математиков, физиков много хороших музыкантов. И теория графов тоже немало помогает музыкальному развитию. Так, например, мы отыскали работы М.И.Ройтерштерна (род. в 1925 г.), музыканта, композитора: «Граф и матрица как инструменты ладового анализа» (1973), «О классификации ладов и графов. Сегментация напева куплета» (1975).

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

Мне как выпускнику музыкальной школы, было полезно познакомиться с этими текстами.

2.10 Теория графов в литературе

«Поэзия имитирует беспорядок, чтобы мы приложили больше сил для восстановления, может быть даже придумывания порядка» (Ю.Лотман). Графы помогают анализировать, и поэтому задания на составление кластера изучаемого произведения часто практикуют на своих уроках учителя литературы:



Основополагающими здесь можно считать работы Ю.М.Лотмана, советского литературоведа, критика. Вот что он пишет: «Одно из основных свойств художественной реальности обнаружится, если мы поставим перед собой задачу отделить то, что входит в самую сущность произведения, без чего оно перестает быть самим собой, от признаков, порой очень существенных, но отделимых в такой мере, что при их изменении специфика произведения сохраняется и оно остается собой.» Далее автор говорит о структуре поэтического, литературного текста, подчёркивая, что эта структура -- модель произведения. «Переведём» эту фразу на язык графов: вершинами графа литературного произведения должны быть существенные и уникальные его признаки, свойства, а второстепенные можно представить рёбрами или дугами между узлами графа.

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

Помните сказку о царе Солтане? Можно построить граф по отрывкам из сказки.

К морю лишь подходит он,

Вот и слышит будто стон...

Бьётся лебедь средь зыбей,

Коршун носится над ней;

Но как раз стрела запела,

В шею коршуна задела --

Коршун в море кровь пролил,

Лук царевич опустил;

Смотрит: коршун в море тонет

И не птичьим криком стонет,

Лебедь около плывёт,

Злого коршуна клюёт,

И царевичу потом

Молвит русским языком…

Вот открыл царевич очи;

Отрясая грёзы ночи

И дивясь, перед собой

Видит город он большой,

Мать и сын идут ко граду.

Лишь ступили за ограду,

Пышный двор встречает их;

Все их громко величают

И царевича венчают

Княжий шапкой, и главой

Возглашают над собой…

И так далее.

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

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

2.11 Теория графов в искусстве

Как вы думаете, какая связь между коррупцией и известным художником? Да, графы!

Марк Ломбарди, Global Networks

Марк Ломбарди (1951-2000), создавал графические полотна, при поверхностном взгляде похожие на звёздные карты. Но если приглядеться, можно увидеть имена известных политиков и главарей международной преступности, стоящие в узлах графа, а связи показывают глобальную коррупцию.

Последователем Ломбарди можно считать Эдварда Тафти, политолога, статистика --и художника. Он является почетным профессором политологии, статистики и информатики Йельского университета. Он -- автор 4 книг по визуализации данных, которые давно считаются классическими, среди которых «The Cognitive Style of PowerPoint», «Визуальное представление больших объемов информации» и «Beautiful Evidence» (красота доказательства). The New York Times назвал Эдварда Тафти «Леонардо да Винчи данных».

Э.Тафти -- автор «искрографиков». Искрографик -- это миниатюрная вставка в текст, иллюстрирующая его. На искрографике (см. справа) помещается довольно большой объём информации, передавая общую картину. Например, на примере справа можно увидеть состояние человека (текст, цифры и линии) и насколько оно укладывается в норму (серые прямоугольники). Конкретный пример применения искрографиков Тафти можно увидеть на сайте дизайн-бюро Артёма Горбунова.

Изучая работы Эдварда Тафти, можно понять, насколько важна в науке красота. Его рекомендации выступающим на научных конференциях сходны с советами опытного художника своему подмастерью. По ссылке ниже можно увидеть одну из работ Тафти, гравировка по стали. На стене в лаборатории Ферми установлено это панно, изображающее 32 диаграммы Фейнмана из области квантовой механики. Эти 32 диаграммы можно увидеть и в трёхмерном виде в настенных панно «Всемогущий фотон» Тафти

Почему Тафти так восхитили эти 32 схемы-графа, что он повторяет их бессчётно на стенах своего гаража, в арт-объектах своего сада, в печатных работах? Мы, поработав над данным исследованием, понимаем его: граф -- это красота науки, выраженная линиями, приятная глазу картина, помогающая понять даже сами основы мироздания.



3. Собственные разработки по теории графов

3.1 Задачи

Задача 1

Из Солнечного города в Зеленый город ведут 3 дороги, а из Зеленого города в Лунный город - четыре дороги. Сколькими способами можно проехать из Солнечного города в Лунный город?

Представим условие задачи в виде графов. Возьмем одну дорогу, ведущую из Солнечного в Зеленый город. Ее можно продолжить до Лунного города 4 разными способами. То же самое можно сделать с каждой из двух других дорог, ведущих из Солнечного в Зеленый город. Всего из Солнечного в Лунный город через Зеленый город можно проехать 3 · 4= 12 способами.

Задача 2

На рисунке в квадратиках живут друзья: Ворчун, Молчун, Пончик, Растеряйка и Тюбик. Кружочками обозначены их цветочки. Могут ли эти жители проложить тропинки к своим цветочкам так, чтобы тропинки не пересекались?

Один из способов решения задачи:



Задача 3

Марина, Лариса, Жанна и Катя умеют играть на разных инструментах- пианино, виолончели, гитаре, скрипке, но каждая только на одном. Они же знают иностранные языки-английский, французский, немецкий и испанский, но каждая только один. Известно:

1. Девушка, которая играет на гитаре, говорит по-испански.

2. Лариса не играет ни на скрипке, ни на виолончели и не знает английского языка.

3. Марина не играет ни на скрипке, ни на виолончели и не знает ни немецкого, ни английского.

4. Девушка, которая говорит по-немецки, не играет на виолончели.

5. Жанна знает французский язык, но не играет на скрипке.

Кто на каком инструменте играет и какой иностранный язык знает?

Решение задачи



Из пятого условия, что Жанна знает французский язык, рисуем стрелку. Из третьего условия, что Марина не знает ни немецкого, ни английского, а французский знает Жанна, то Марина знает испанский и, рассматривая первое условие она играет на гитаре. Из условия №2 видим, что Лариса играет на пианино, т.к. Марина играет на гитаре, а на других инструментах она играть не умеет, и значит, она говорит по-немецки.

Жанна не играет на скрипке, то остается один инструмент, на котором она может играть это виолончель. Тогда Катя играет на скрипке, и знает английский язык

3.2 Наше видеопособие для уроков математики

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

Условие задачи.

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

Известно, что в настоящий момент:

Ваня сыграл шесть партий;

Толя сыграл пять партий;

Леша и Дима сыграли по три партии;

Семен и Илья сыграли по две партии;

Женя сыграл одну партию.

Требуется определить: с кем сыграл Леша.

В ходе проведённой нами работы были использованы:

· В виде источников информации всемирная система объединённых компьютерных сетей для передачи информации или интернет.

· Для создания графической части были задействованы:Paint, OpenOffice, Ocam, Abobe Premier Pro.

После того как видеорешение было готово мы выложили его в интернет:

https://youtu.be/_dZD7whFQ4k

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

3.3 Эксперимент с дошкольниками

Вы думаете, что графы изучают только в углубленном курсе математики? Мы доказали, что это не так. Мы составили несколько задач, из теории графов и уже опробовали на наших младших сестрах и братьях, а также в детском саду. Мы провели в детском саду занятие с детьми старшей группы. С дошкольниками мы начинали свою беседу с обычных рисунков графов. Просто обсуждали на что они похожи. Мы ожидали, что дети дошкольного возраста скажут -- железная дорога + станции, дерево, созвездие… Но ребята удивили, один нашел здесь велосипед, другой собаку, третий идущего человека и даже жука.

Интересно, что на вопрос “Слышал ли ты, что такое граф?”, дети толково объясняли, что это богатый человек, который живет “где-то недалеко от короля или просто в его королевстве”. А дальше мы просто строили свои графы на столе с помощью шнурков и кружков, вырезанных из картона. Мы говорили маленьким детям, что кружки -- это дома, а шнурки -- дороги. (Приложение 5)

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

Следующим упражнением было построение детьми графа из шнурков на столе. Срисовав эти графы в игровой форме мы предложили детям выступить в роли главных «картографов», проверить рисунок и дать заключение, правильно ли выполнен чертеж города. (По сути проверить, изоморфность или “одинаковость” двух графов. В ходе занятий в детском саду мы заметили, что это упражнение очень хорошо развивает пространственное мышление. Детям приходилось немало потрудиться, чтобы сопоставить шнурки на столе с рисунком.

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

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

· красная дорога занимает -- 3 минуты

· желтая дорога -- 2 минуты

· голубая дорога- 1 минуту

Автомобилю надо добраться до розового домика: какую дорогу выбрать? Сначала мы обозначили, какие дороги возможны, потом сложили и выбрали ту, что занимала меньшее всего времени. (То есть голубая + голубая)

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

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

Приложение 5



Заключение

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

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

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

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

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

Подводя итоги главе 2 необходимо подчеркнуть, что применение графов встречается почти в любой отрасли науки и. В физике - при построении электрических схем, в химии и биологии- при изучении молекул и их цепочек, в географии - при составлении карт, в истории - при составлении родословной (в ходе работы было составлено генеалогическое дерево моей семьи), в геометрии - в чертежах многоугольников, многогранников, пространственных фигур, в экономике - при решении задач о выборе оптимального пути для потоков грузового транспорта (схем авиалиний, метро, железных дорог). Графами являются блок-схемы программ для ЭВМ, сетевые графики строительства. С помощью графов решается задача о назначении на должности. А именно: если имеется несколько вакантных должностей и группы лиц, желающих их занять, причем каждый из претендентов имеет квалификацию для нескольких должностей, то при каких условиях каждый из претендентов сможет получить работу по одной из своих специальностей? Тема графов оказалась настолько многогранной, что находит применение везде, даже в музыке и поэзии. Теория графов в школьной программе не изучается, но широко применяется при решении математических олимпиадных задач. Подводя промежуточные итоги, мы можем сказать, что с помощью теории графов можно решить проблему или задачу из любой области человеческой жизни.

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

Мы разработали видеорешения задач и выложили ее в сеть интернет.

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

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

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

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

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



Приложения.

Приложение 1

Схема линий Московского метрополитена



Приложение 2

Генеалогическое дерево А.С.Пушкина



Приложение 3

Мое генеалогическое дерево

Я составил генеалогическое дерево моей семьи. Дерево -- связный ациклический граф. Так как его узлам можно поставить в соответствие некоторые параметры -- возраст, имя и т.п., то этот граф взвешенный. Так как связи между узлами зависят от направления (от Петра Николаевича к Андрею Петровичу -- отец, в обратном направлении -- сын), то этот граф ориентированный мультиграф. Если же этот граф дополнить связями «бабушка -- внучка», «дядя -- племянник», то граф станет полным (каждый узел будет соединён с другим).



Приложение 4

Мое генеалогическое дерево

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

	Здравствуйте Fonin Dmitry, Это автоматическое уведомление на MyHeritage Вот предстоящие события в Вашей семье: Завтра 7 января 2017 20 день рождения Дарья Отправить Дарья поздравление Предстоящие семейные события в следующие 30 дней 26 января 2017 75 день рождения Виктор Антонов Отправить Виктор поздравление 4 февраля 2017 39 день рождения Александр Фонин Отправить Александр поздравление Всего наилучшего, MyHeritage



Приложение 5

Занятия с дошкольниками

Задание 1. Урок мы начали с обычных рисунков графов. Просто обсуждали на что они похожи. Мы ожидали, что дети скажут -- железная дорога + станции, дерево, созвездие… Но ребята удивили, нашли здесь велосипед, собаку, идущего человека и даже жука.

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



Задание 3. Срисовывание графа и подсчет количества вершин и ребер.

Задание 4. Дети в роли главных «картографов»

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



Задание 6. Найти кратчайший путь из одной вершины графа в другую.

Задание 7. Найти дорогу от голубого домика до розового (того, что напротив)

Задание 8. Собственные графы дошкольников



Используемая литература и ресурсы

1. Клауди Альсина. Карты метро и нейронные сети. Теория графов (Мир математики Т.11), 2014.

2. Белов В.В., Теория графов, Москва, 1976.

3. Бенгальское письмо [https://ru.wikipedia.org/wiki/Бенгальское_письмо]

4. Бурков В.Н. Элементы теории графов, Москва, 1996

5. Дизайн-бюро Артёма Горбунова. http://artgorbunov.ru/bb/soviet/20090820/

6. Гамильтонов граф. [https://ru.wikipedia.org/wiki/Гамильтонов_граф]

7. Граф (математика). [https://ru.wikipedia.org/wiki/Граф_(математика)]

8. Искрографик. Материал из Википедии, свободной энциклопедии. https://ru.wikipedia.org/wiki/Искрографик

9. Искрографик. Материал из Википедии, свободной энциклопедии. https://ru.wikipedia.org/wiki/Искрографик

10. Раздел «Графы» в архиве номеров журнала «Квант». [http://kvant.ras.ru/key.htm]

11. Эйлер Леонард. Сборник статей в честь 250-летия со дня рождения. Публичная библиотека. Электронные книжные полки Вадима Ершова и К°) [http://publ.lib.ru/ARCHIVES/E/EYLER_Leonard/_Eyler_L..html#013]

12. Марк Ломбарди [https://en.wikipedia.org/wiki/Mark_Lombardi]

13. Анализ поэтического текста: Структура стиха // Лотман Ю. М. О поэтах и поэзии. СПб., 1996. [Электронный ресурс. Режим доступа: http://www.ruthenia.ru/lotman/papers/apt, проект Тарутсского университета «Lotmaniana Tartuensia: Монографии, статьи, заметки»]

14. Мельников О.И. Теория графов в занимательных задачах. 2009.

15. Ориентированный граф. [https://ru.wikipedia.org/wiki/Ориентированный_граф

16. Оре О. Теория графов. М.: Наука, 1968.

17. Эдвард Тафти. Всемогущий фотон. http://www.edwardtufte.com/bboard/q-and-a-fetch-msg?msg_id=0003oo

18. Николай Товеровский. Искрографики (sparklines). Официальный сайт KSoftWare http://www.ksoftware.ru/wiki/sparklines

19. Теория графов. Виртуальная лаборатория [http://ru.vlab.wikia.com/wiki/Теория_графов]

20. Письма к Эйлеру и письма Эйлера. Архив Российской Академии наук. Ф. 136. Оп. 002. Д. 3 http://db.ranar.spb.ru/ru/list/id/1117/

21. Уилсон Р. Введение в теорию графов. Пер с англ. М.: Мир, 1977.

22. Харари Ф. Теория графов. М.: Мир, 1973.

23. Фосс В. Элементы теории графов. Журнал «Квант», №8, 1973. [http://kvant.ras.ru/1973/08/index_n.htm]

Используемые изображения

1. Кабак В.О. Родовод Пушкина А.С. https://ru.wikipedia.org/wiki/Пушкины#/media/File:Pushkin_rod.png

2. Схема метрополитена Москвы, Россия http://mosmetro.ru/metro-map/

3. Блок-схема. https://ru.wikipedia.org/wiki/Блок-схема

4. Древнерусский алфавит “глаголица” https://upload.wikimedia.org/wikipedia/commons/0/01/Glagolica.png

5. Малахова Л.Т. Использование структурно-логических схем на уроках литературы. Материалы международных педагогических чтений. http://www.wecomm.ru/structure/?idstucture=685

6. Филиппова Г.В. Структурно-логические схемы по литературе. http://pedsovet.su/load/28-1-0-17747

7. Марк Ломбарди, Global Networks, Университет Олбани, США http://www.albany.edu/museum/wwwmuseum/work/lombardi/index.html

Размещено на Allbest.ru