V Международный конкурс научно-исследовательских и творческих работ учащихся

Старт в науке

В мире графов

• Авторы
• Руководители
• Файлы работы
• Наградные документы

Кушнарев  А.С. 1

---

1Муниципальное общеобразовательное учреждение средняя общеобразовательная школа №4

Мельникова  Е.Н. 1

---

1Муниципальное общеобразовательное учреждение средняя общеобразовательная школа №4

Работа в формате PDF

3.2 MB

Автор работы награжден дипломом победителя III степени

Диплом школьникаСвидетельство руководителя

Введение

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

Работу начали с анкетирования учащихся 6 – 11 классов нашей школы, чтобы выяснить,что они знают о графах. Вопросы были следующие:

1. Играли ли вы в игру «Соедини цифры и получи картинку»?

2. Решали ли вы задачи типа «Начертите фигуру, не отрывая карандаша от бумаги и не проводя никакую линию дважды».

3. Вы выполняли задания 1 и 2 ,используя метод проб и ошибок или применяя какие-то научные знания?

4. Знаете ли вы, что существует целая наука «Теория графов», которая помогает решить такие задачи?

5. Хотели бы вы побольше узнать о теории графов?

В опросе приняли участие 114 человек. Результаты оказались следующими (Приложение 1).

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

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

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

Задачи:

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

2.Провести опрос по теме «Графы».

3.Изучить элементы теории графов.

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

5. Разобрать решение различных видов задач.

Объект исследования: раздел математики «Теория графов»

Предмет исследования: математические и логические задачи, головоломки на предмет применения метода графов

Методы исследования:

1.Работа с учебной и научно-популярной литературой, ресурсами сети Интернет.

2. Анкетирование,

Этапы проекта:

- Теоретический

- Практический

2. Основная часть

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

Граф - в переводе с древневерхненемецкогоgravo, gravio - «предводитель, вождь»

Граф – от греческого.γράφω «царапаю, черчу, пишу».

Граф (титул) — дворянский титул;

Слово «граф» как математический термин первым стал использовать Джеймс Джозеф Сильвестр (англ. JamesJosephSylvester; 3 сентября1814, Лондон, — 15 марта1897, Оксфорд) — известный английский математик, известный своими работами в комбинаторики.

Графом в математике называется конечное множество точек, некоторые из которых соединили линиями. Точки называются вершинами графа, а соединяющие их линии – рёбрами.

Родоначальником теории графов считается Леонард Эйлер-швейцарскийматематик и механик. В 1736 году в одном из своих писем он формулирует ипредлагает решение задачи о семи кёнигсбергских мостах, ставшей впоследствии одной из классических задач теории графов.

Задача:Рукава реки Прегель, на берегу которой расположен город Кёнигсберг (ныне Калининград), образовывали два острова. В ту эпоху четыре образовавшихся участка суши (правый и левый берег и два острова) соединяло семь мостов так, как это показано на рисунке. Среди жителей города была распространена такая загадка: как пройти по всем мостам, не проходя ни по одному из них дважды? Многие кёнигсбержцы пытались решить эту задачу как теоретически, так и практически, во время прогулок. Но это им не удавалось, а Эйлер доказал, что это принципиально невозможно, приведя следующие рассуждения. Расположение районов города можно представить на схеме, где четырём точкам A, B, C и D соответствуют четыре района города, а кривым, соединяющим эти точки, - мосты.

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

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

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

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

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

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

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

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

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

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

не выполняется.

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

Деревья особенно часто возникают на практике при изображении различных иерархий. Например, популярны генеалогические деревья (Приложение2-генеалогическое дерево А.С. Пушкина).Мы составили своё родословное дерево(Приложение 3).

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

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

Плоские графы обладают многими интересными

свойствами. Так, Эйлер обнаружил простую связь

между количеством вершин (В), количеством ребер (Р)

и количеством частей (Г), на которые граф разделяет

плоскость: В–Р+Г=2.

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

Такой путь существует лишь в том случае, если граф – связный,

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

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

Если степени всех вершин графа равны, то граф называется однородным. Таким образом, любой полный граф — однородный.

2.3. Некоторые задачи теории графов

Задач о вычерчивании фигур одним росчерком

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

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

Граф с более чем двумя нечётными вершинами невозможно начертить одним росчерком.

Задача 1.Говорят, что Магомет вместо подписи (он был неграмотен) описывал одним росчерком состоящий из двух рогов луны знак, представленный на рисунке. Возможно ли это?

Решение. Да, потому что в данном случае мы имеем дело с вершинами четного порядка.

Задача 2. (Муха в банке). Муха забралась в банку из-под сахара. Банка имеет форму куба. Сможет ли муха последовательно обойти все 12 ребер куба, не проходя дважды по одному ребру? Подпрыгивать и перелетать с места на место не разрешается.

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

Задачи с лабиринтами

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

Задача о прохождении лабиринта приобретает практический интерес, поскольку устройство линий электропередач, канализации, сетей дорог, каналов и т.д. – все это более или менее сложные лабиринты. Начало решению вопроса о существовании безвыходных лабиринтов положено Эйлером.

Задача 3: Можно ли обойти все данные комнаты, пройдя через каждую дверь ровно один раз и выйти на улицу через комнату 1 или 10? С какой комнаты надо начинать?

Решение:

1) Пусть комнаты – вершины графа, а двери – ребра. Проверим степени вершин:

2)Только две вершины имеют нечетную степень. Начать движение можно из комнаты 10, а закончить в комнате 8, либо наоборот.

3) Но, чтобы выйти на улицу (из комнаты 10), надо начинать из комнаты 8. В этом случае пройдём все двери один раз и попадём в комнату 10, но окажемся внутри комнаты, а не снаружи:

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

Логические задачи

Задача 4: Если задуманное число умножить на 5 и к результату прибавить 1, потом сумму увеличить в 6 раз и к результату прибавить 2, затем новую сумму умножить на 7 и полученное произведение увеличить на 4, то получим число, которое в 16 раз больше числа 135. Найдите это число.

Решение: Сделаем рисунок (построим граф).

Решая, действия выполняем наоборот.

Задача 5:Колхозница принесла на базар корзину яблок. I покупателю она продала половину всех яблок и еще 1 яблоко, II – половину остатка и еще 1 яблоко, III – половину нового остатка и еще 1 яблоко и т.д. Последнему – шестому покупателю она также продала половину оставшихся яблок и еще 1 яблоко, причем оказалось, что она продала все свои яблоки. Сколько яблок принесла для продажи колхозница?

Решение: Составим граф.

Решая, действия делаем обратно.

Ответ: 126 яблок.

Задача 6: Несколько мальчиков встретились на вокзале, чтобы поехать за город в лес. При встрече все они поздоровались друг с другом за руку. Сколько мальчиков поехали за город, если всего было 10 рукопожатий?

Решение: Сделаем рисунок. Точки будут изображать мальчиков, а отрезки рукопожатия.

1) 2) 3) 4)

Из рисунка видно, что на вокзале встретились 5 мальчиков.

Задача 7.У Наташи есть 2 конверта: обычный и авиа, и 3 марки: прямоугольная, квадратная и треугольная. Сколькими способами Наташа может выбрать конверт и марку, чтобы отправить письмо?

Решение:6 способов

2.4. Применение теории графов

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

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

Графы и информатика

Составление различных блок-схем

Графы и химия

Молекула каждого предельного углеводорода представляет собой дерево (например бутан и изобутан)

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

Элементарная ячейка кристалла NaCl

Графы и биология

Деревья играют большую роль в биологической теории ветвящихся процессов.

Размножение бактерий

Графы и астрономия

Графы есть на картах звёздного неба

Графы и физика

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

Графы и история

Социальная структура и основные категории населения Древней Руси

Графы и социальная сфера (Приложение 4- Приложение 6)

4.Заключение

В данной работе нами были рассмотрены основные понятия теории графов, их виды, разобраны задачи.

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

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

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

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

5.Список используемой литературы

Е.И.Игнатьев. «Математическая смекалка»

О.Оре. Графы и их применение. – М.: Мир, 1965.

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

«Математика в школе», №2,1994

«Первое сентября. Информатика», №20,2007

http://kenigsberg-pr.narod.ru/image/i3.gif

http://ru.wikipedia.org/wiki.

http://school-sector.relarn.ru.

Приложение 1

Анкетирование

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

Приложение 2

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

Приложение 3

Родословное дерево семьи Кушнаревых

Приложение 4

Схема сети железной дороги в Забайкальском крае

Схема сети автомобильных дорог в Забайкальском крае

Приложение 5

Ученическое самоуправление МОУ СОШ №4

Приложение 6