Индивидуальный учебный проект по теме "Графы и их применение"

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

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

Индивидуальный  проект

по математике

за курс 10 класса

по теме: «Графы и их применение»

Выполнила:

Пирогова Анастасия Юрьевна

10"Б" класс

Руководитель:

Максимова Елена Леонидовна

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

п.Большевик 2018

СОДЕРЖНИЕ:

Введение _____________________________________________

Введение

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

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

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

ЦЕЛИ, ЗАДАЧИ И МЕТОДЫ ИССЛЕДОВАНИЯ

Цель исследовательской работы:

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

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

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

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

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

Методы исследования, которые используются в проекте:

Поиск и анализ информации в литературе и интернет – ресурсах.

I. ТЕОРЕТИЧЕСКАЯ ЧАСТЬ

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

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

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

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

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

Задача 1. Между девятью планетами солнечной системы установлено космическое сообщение. Рейсовые ракеты летают по следующим маршрутам: Земля – Меркурий; Плутон – Венера; Земля – Плутон; Плутон – Меркурий; Меркурий – Вене; Уран – Нептун; Нептун – Сатурн; Сатурн – Юпитер; Юпитер – Марс и Марс – Уран. Можно ли долететь на рейсовых ракетах с Земли до Марса?

Решение: Нарисуем схему условия: планеты изобразим точками, а маршруты ракет – линиями.  

Теперь нам видно, что долететь с Земли до Марса на рейсовых ракетах нельзя.

Задача 2. В одном городе шесть станций метро: Алмазная, Золотая, Лесная, Парковая, Садовая, Серебряная. Поезда следуют по маршрутам Алмазная – Золотая, Золотая – Серебряная, Серебряная – Алмазная. Лесная – Садовая, Садовая – Парковая, Парковая – Лесная. Можно ли с помощью этих поездов добраться со станции Парковая до станции Алмазная?

Решение: Нарисуем картинку, на которой будем отмечать станции точками, а соединяющие их маршруты – непересекающимися линиями.

 Ответ: добраться со станции Парковая до станции Алмазная нельзя.

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

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

Такие одинаковые, но по-разному нарисованные графы, называются изоморфными

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

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

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

       Все три фигуры на рисунке  изображает один и тот же граф.

1.2. Виды графов:

1. Ориентированный граф (кратко орграф) — рёбрам которого присвоено направление.

2. Неориентированный граф - это граф, в котором нет направления линий.

3.Взвешенный граф – дуги или ребра имеют вес.

4. Связный граф

Две  вершины А и В графа называются связными, если в графе существует путь с концами А и В.

        Две вершины графа называются  несвязными, если в графе не существует ни одного пути, связывающего их.

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

        Несвязный граф имеет вид нескольких “кусков”, каждый из которых – либо отдельная вершина без ребер, либо связный граф.

1.3. Полнота графа

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

      В полном графе каждая его вершина принадлежит одному и тому же числу

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

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

1.4. Степень вершины

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

      У графа на рисунке 13 (а): степень= 1; на рисунке 13(б) степень = 2. У графа на рисунке 13 (в) степени всех вершин равны нулю.

      Вершина называется нечетной, если ее степень – число нечетное. Вершина называется четной, если ее степень – число четное.    

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

1.5. Свойства графов:

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

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

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

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

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

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

II. ИССЛЕДОВАТЕЛЬСКАЯ ЧАСТЬ

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

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

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

       Каждая вершина графа с девятью вершинами может иметь степень, равную 0,1,2….7,8.  Предположим, что существует граф , все вершины которого имеют одинаковую степень, т.е. каждое из чисел  последовательности 0,1,2,…,7,8 является степенью одной и только одной из его вершин. Но этого не может быть. Действительно, если в графе есть вершина А степени 0, то в нем   найдется вершина В   со степенью 8, так как эта вершина В должна быть соединена ребрами со всеми остальными вершинами графа, в том числе и с А. Иначе говоря, в графе с девятью  вершинами не могут быть одновременно вершины 0 и 8. Следовательно, найдутся хотя бы две вершины, степени которых равны между собой.

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

Решение: Допустим, что такое соединение телефонов возможно. Тогда представим себе граф, в котором вершины обозначают телефоны, а ребра – провода, их соединяющие. Подсчитаем, сколько всего получится проводов. К каждому телефону подключено ровно 5 проводов, т.е. степень каждой вершины нашего графа – 5. Чтобы найти число проводов, надо просуммировать степени всех вершин графа и полученный результат разделить на 2 (т.к. каждый провод имеет два конца, то при суммировании степеней каждый провод будет взят 2 раза). Но тогда количество проводов получится разным . Но это число не целое. Значит наше предположение о том, что можно соединить каждый телефон ровно с пятью другими, оказалось неверным.

Задача 3. Охотник за мертвыми душами Павел Иванович Чичиков побывал у помещиков по одному разу у каждого. Он посещал их в следующем порядке: Манилова, Коробочку, Ноздрева, Собакевича, Плюшкина, Тентентникова, генерала Бетрищева, Петуха, Констанжогло, полковника Кошкарева. Найдена схема, на которой Чичиков разбросал взаимное расположение имений и проселочных дорог, соединяющих их. Установите, какое имение кому принадлежит, если ни по одной дороге Чичиков не проезжал более одного раза.

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

        Определены участки маршрута, проходящие через А: АС и АВ. По дорогам АЕ, АК и АМ Чичиков не ездил. Перечеркнем их. Отметим жирной линией ЕD; перечеркнем DK. Перечеркнем МО и МН; отметим жирной линией MF; перечеркнем FHO; отметим жирной линией FH, HK и КО. Найдем единственно возможный при данном условии маршрут. С рисунка  остается только считать ответ: имение Е принадлежит Манилову, D-Коробочке, С – Ноздреву, А -Собакевичу, В – Плюшкину, М – Тентентникову, F – Бетрищеву, Н – Петуху, К – Констанжогло, О – Кошкареву.

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

2.2.1. Графы в структуре управления

 Первый пример применения  - граф «Структура управления МОУ «Дашковская СОШ»», в которой показано, как работает система образования. Есть три уровня, которые связаны между собой.

- Уровень государственно – общественного управления

- Административный уровень

- Методический уровень.

Эту связь мы можем увидеть с помощью графов.

2.2.2. Графы в психологии.

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

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

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

Заключение.

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

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

1. Коннова Е.Г. Издательство «Легион-М» 2009 г.
2. Энциклопедический словарь юного математика.  Москва, Педагогика, 1985г.
3. Засенок В.П. Графы в математике и в жизни/программа интеллектуального развития учащихся /выпуск 6./ Инновационно-образовательный центр-М. 1997года.
4. Е.В. Галкин. Нестандартные задачи по математике. Задачи логического характера . Книга для учащихся 5-11 классов. “Просвещение” – “Учебная литература” Москва 1996.
5. О.И.Мельников. Незнайка в стране графов. М.: КомКнига,2006.
6. Л.Ю.Березина. Графы и их применение. Москва, «Просвещение», 1979

Список онлайн-ресурсов.

1. https://globallab.org/ru/project/cover/reshenie_zadatch_s_pomoshju_grafa.ru.html#.WgAagF27WUl
2. https://infourok.ru/issledovatelskaya_rabota_po_matematike_grafy_i_ih_primenenie-300803.htm
3. https://infourok.ru/nauchnoissledovatelskaya-rabota-po-matematike-na-temu-grafi-414185.html
4. https://ru.wikipedia.org/wiki/Граф_(математика)
5. https://infourok.ru/issledovatelskaya_rabota_po_teme_reshenie_olimpiadnyh_zadach_s_pomoschyu_grafov-294265.htm
6. https://globallab.org/ru/project/cover/reshenie_zadatch_s_pomoshju_grafa.ru.html#.WlsXpTeWSUm