Научно-исследовательская работа «Графы вокруг нас»

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

средняя общеобразовательная школа № 51

г. Оренбург.

 

Проект на тему:

 

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

Егорчева Виктория Андреевна

 

2017

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

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

Задачи:

1)Расширить знания о способах построения графов.

2)Выделить типы задач, решение которых требует применения теории графов.

3) Исследовать использование графов в математике.

« Эйлер вычислял без всякого видимого усилия, как человек дышит или как орёл парит над землёй ».

Доминик Араго.

 

Содержание:

I. Введение. стр.

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

1. Понятие графа. Задача о Кенигсбергских мостах. стр.

2. Свойства графов. стр.

3. Задачи с применением теории графов. стр.

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

Значение графов. стр.

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

 

I. ВВЕДЕНИЕ.

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

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

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

II. ОСНОВНАЯ ЧАСТЬ.

1. Понятие графа.

Первая работа по теории графов принадлежит Леонарду Эйлеру. Она появилась в 1736 году в публикациях Петербургской Академии Наук и начиналась с рассмотрения задачи о кенигсбергских мостах.

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

4

Рассказывают, что однажды житель города спросил у своего знакомого, сможет ли он пройти по всем мостам так, чтобы на каждом из них побывать только один раз и вернуться к тому месту, откуда началась прогулка. Многие горожане заинтересовались этой задачей, однако придумать решение никто не смог. Этот вопрос привлек внимание ученых из многих стран. Разрешить проблему удалось известному математику Леонарду Эйлеру. Леонард Эйлер, уроженец города Базеля родился 15 апреля, 1707 года. Научные заслуги Эйлера огромны. Он оказал влияние на развитие почти всех разделов математики и механики как в области фундаментальных исследований, так и в их приложениях. Леонард Эйлер не только решил эту конкретную задачу, но и придумал общий метод решения этих задач. Эйлер поступил следующим образом: он «сжал» сушу в точки, а мосты «вытянул» в линии. В результате получилась фигура, изображенная на рисунке.

Такую фигуру, состоящую из точек и линий, связывающих эти точки, называют графом. Точки A,B,C,D называют вершинами графа, а линии, которые соединяют вершины – ребра графа. На рисунке из вершин B,C,D выходят по 3 ребра, а из вершины A – 5 ребер. Вершины, из которых выходит нечетное число ребер, называют нечетными вершинами, а вершины, из которых выходит четное количество ребер, - четными.

2.Свойства графа.

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

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

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

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

4.Число нечетных вершин графа всегда четное.

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

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

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

3.Решение задач с помощью графов.

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

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

 

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

Если в фигуре имеется только одна пара нечетных точек, то такую фигуру можно нарисовать одним росчерком, начав черчение в одной из нечетных точек (безразлично в какой). Легко сообразить, что вычерчивание должно оканчиваться во второй нечетной точке. Таковы фигуры 2, 3, 6. В фигуре 6, например, вычерчивание надо начинать либо из точки А, либо из точки В.

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

Предлагаю начертить одним росчерком следующие фигуры.

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

ЗАДАЧА №1.

В первенстве класса по настольному теннису 6 участников: Андрей, Борис, Виктор, Галина, Дмитрий и Елена. Первенство проводят по круговой системе – каждый из участников играет с каждым из остальных один раз. К настоящему моменту некоторые игры уже проведены: Андрей сыграл с Борисом, Галиной, Еленой; Борис - с Андреем, Галиной; Виктор – с Галиной, Дмитрием, Еленой; Галина – с Андреем, Виктором и Борисом. Сколько игр проведено к настоящему моменту и сколько ещё осталось?

РЕШЕНИЕ:

Построим граф как показано на рисунке.

7

Сыграно 7 игр.

На этом рисунке граф имеет 8 ребер, следовательно, осталось провести 8 игр.

ЗАДАЧА №2

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

РЕШЕНИЕ:

Решение задачи приведено на рисунке.

3. Решение текстовых задач.

Для решения задач методом графов надо знать следующий алгоритм:

1.О каком процессе идет речь в задаче? 2.Какие величины характеризуют этот процесс? 3.Каким соотношением связаны эти величины? 4.Сколько различных процессов описывается в задаче? 5.Есть ли связь между элементами?
 

Отвечая на эти вопросы, анализируем условие задачи и записываем его схематично.

Например. Автобус шёл 2 ч со скоростью 45 км/ч и 3 ч со скоростью 60 км/ч. Какой путь прошёл автобус за эти 5 часов?

S¹=90 км V¹=45 км/ч t¹=2ч

S= VT

S²=180 км V²=60 км/ч t²=3 ч

 

S¹ + S² = 90 + 180

Решение:

1)45 x 2 = 90 (км) – прошёл автобус за 2 ч.

2)60 x 3 = 180 (км) – прошёл автобус за 3 ч.

3)90 + 180 = 270 (км) –прошёл автобус за 5 ч.

Ответ: 270 км.

 

III. ЗАКЛЮЧЕНИЕ.

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

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

 

V. СПИСОК ЛИТЕРАТУРЫ:

1. Альхова З.Н., Макеева А.В. «Внеклассная работа по математике».

2. Журнал «Математика в школе». Приложение «Первое сентября» № 13

2008г.

3. Я.И.Перельман «Занимательные задачи и опыты».- Москва: Просвещение, 2000 г.

16

Рецензия.

Проект на тему «Графы вокруг нас» выполнил ученик 7 «А» класса МОУ-сош №3г.Красный Кут Зайцев Никита.

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

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

В работе рассматриваются такие вопросы как:

1. Понятие графа. Задача о Кенигсбергских мостах.

2. Свойства графов.

3. Задачи с применением теории графов.

4. Значение графов.

5. Вариант маршрута школьного автобуса.

При выполнении своей работы Зайцев Н. использовал:

1. Альхова З.Н., Макеева А.В. «Внеклассная работа по математике».

2. Журнал «Математика в школе». Приложение «Первое сентября» № 13

2008г.

3. Я.И.Перельман «Занимательные задачи и опыты».- Москва: Просвещение, 2000 г.

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

Данная работа рекомендована на научно-практическую конференцию «Шаг в будущее».