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

Старт в науке

Графы и применение

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

Наумова Д.С. 1

---

1МБОУ "Старомокшинская СОШ имени В.Ф.Тарасова"

Михайлова В.М. 1

---

1МБОУ "Старомокшинская СОШ имени В.Ф.Тарасова"

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

485.9 KB

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

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

Введение

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

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

Начало теории графов датируют 1736 г., когда Л. Эйлер решил популярную в то время «задачу о кенигсбергских мостах», ставшей впоследствии одной из классических задач теории графов. (Приложение 1)

Термин «граф» впервые был введен спустя 200лет (в 1936г.) Д.Кениго.

Историю возникновения этой теории можно проследить по переписке великого ученого. Вот перевод латинского текста, который взят из письма Эйлера к итальянскому математику и инженеру Маринони, отправленного из Петербурга 13 марта 1736 года. (Приложение 2)

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

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

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

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

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

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

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

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

Объект исследования: сфера деятельности человека на предмет применения метода графов.

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

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

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

В ходе нашего исследования были использованы такие методы, как:

1) Работа с различными источниками информации.

2) Описание, сбор, систематизация материала.

3) Наблюдение, анализ и сравнение.

4) Составление задач.

5) Анкетирование.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

В начале своей работы я провел анкетирование среди учащихся 5 - 11 классов МБОУ «Старомокшинской СОШ имени В.Ф.Тарасова». В опросе приняли участие 70 учащихся. Результаты опроса. (Приложение 3)

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. Графы в психологии.

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

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

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

Заключение.

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

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

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

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

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

Коннова Е.Г. Издательство «Легион-М» 2009 г.

Энциклопедический словарь юного математика. Москва, Педагогика, 1985г.

Засенок В.П. Графы в математике и в жизни/программа интеллектуального развития учащихся /выпуск 6./ Инновационно-образовательный центр-М. 1997года.

Е.В. Галкин. Нестандартные задачи по математике. Задачи логического характера . Книга для учащихся 5-11 классов. “Просвещение” – “Учебная литература” Москва 1996.

О.И.Мельников. Незнайка в стране графов. М.: КомКнига,2006.

Л.Ю.Березина. Графы и их применение. Москва, «Просвещение», 1979

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

https://globallab.org/ru/project/cover/reshenie_zadatch_s_pomoshju_grafa.ru.html#.WgAagF27WUl

https://infourok.ru/issledovatelskaya_rabota_po_matematike_grafy_i_ih_primenenie-300803.htm

https://infourok.ru/nauchnoissledovatelskaya-rabota-po-matematike-na-temu-grafi-414185.html

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

https://infourok.ru/issledovatelskaya_rabota_po_teme_reshenie_olimpiadnyh_zadach_s_pomoschyu_grafov-294265.htm

https://globallab.org/ru/project/cover/reshenie_zadatch_s_pomoshju_grafa.ru.html#.WlsXpTeWSUm

Приложение 1

Эйлер Леонард (1707—1783), математик, физик, механик, астроном.

Родился 15 апреля 1707 г. в Базеле (Швейцария). Окончил местную гимназию,

слушал в Базельском университете лекции И. Бернулли. В 1723 г. получил степень магистра. В 1726 г. по приглашению Петербургской академии наук приехал в Россию и был назначен адъюнктом по математике.

В 1730 г. занял кафедру физики, а в 1733 г. стал академиком. За 15 лет своего пребывания в России Эйлер успел написать первый в мире учебник теоретической механики, а также курс математической навигации и многие другие труды.

В 1741 г. он принял предложение прусского короля Фридриха II и переехал в Берлин. Но и в это время учёный не порвал связи с Петербургом. В 1746 г. вышло три тома статей Эйлера, посвящённых баллистике.

В 1749 г. он выпустил двухтомный труд, впервые излагающий вопросы навигации в математической форме. Многочисленные открытия, сделанные Эйлером в области математического анализа, были позже объединены в книге «Введение в анализ бесконечно малых величин» (1748 г.).

Вслед за «Введением» вышел трактат в четырёх томах. 1-й том, посвящённый дифференциальному исчислению, вышел в Берлине (1755 г.), а остальные, посвящённые интегральному исчислению, — в Петербурге (1768—1770 гг.).

В последнем, 4-м томе рассматривается вариационное исчисление, созданное Эйлером и Ж. Лагранжем. Одновременно Эйлер исследовал вопрос о прохождении света через различные среды и связанный с этим эффект хроматизма.

В 1747 г. он предложил сложный объектив.

В 1766 г. Эйлер вернулся в Россию. Работу «Элементы алгебры», увидевшую свет в 1768 г., учёный вынужден был диктовать, так как к этому времени он ослеп. Тогда же печатались три тома интегрального исчисления, два тома элементов алгебры, мемуары («Вычисление Кометы 1769», «Вычисление затмения Солнца», «Новая теория Луны», «Навигация» и др.).

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

Эйлеру принадлежит более 865 исследований по самым разнообразным и труднейшим вопросам. Он оказал большое и плодотворное влияние на развитие математического просвещения в России в XVIII в. Петербургская математическая школа, в которую входи ли академики С. К. Котельников, С. Я Румовский, Н. И. Фусс, М. Е. Головин и другие учёные, под руководством Эйлера провела огромную просветительную работу, создала обширную и замечательную для своего времени учебную литературу, выполнила ряд интересных исследований.

Скончался Эйлер 18 сентября 1783 г. в Петербурге.

Приложение 2

"Некогда мне была предложена задача об острове, расположенном в городе Кенигсберге и окруженном рекой, через которую перекинуто семь мостов. Спрашивается, может ли кто- нибудь непрерывно обойти их, проходя только однажды через каждый мост. И тут же мне было сообщено, что никто еще до сих пор не мог это проделать, но никто и не доказал, что это невозможно. Вопрос этот, хотя и банальный, показался мне, однако, достойным внимания тем, что для его решения недостаточны ни геометрия, ни алгебра, ни комбинаторное искусство… После долгих размышлений я нашел легкое правило, основанное на вполне убедительном доказательстве, с помощью которого можно во всех задачах такого рода тотчас же определить, может ли быть совершен такой обход через какое угодно число и как угодно расположенных мостов или не может. Кенигсбергские же мосты расположены так, что их можно представить на следующем рисунке  , на котором A обозначает остров, а B, C и D – части континента, отделенные друг от друга рукавами реки. Семь мостов обозначены буквами a, b, c, d, e, f, g ":

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

Так можно ли обойти Кенигсбергские мосты, проходя только один раз через каждый из этих мостов? Чтобы найти ответ, продолжим письмо Эйлера к Маринони:

"Вопрос состоит в том, чтобы определить, можно ли обойти все эти семь мостов, проходя через каждый только однажды, или нельзя. Мое правило приводит к следующему решению этого вопроса.   Прежде всего, нужно смотреть, сколько есть участков, разделенных водой, – таких, у которых нет другого перехода с одного на другой, кроме как через мост. В данном примере таких участков четыре – A, B, C, D. 
Далее нужно различать, является ли число мостов, ведущих к этим отдельным участкам, четным или нечетным. Так, в нашем случае к участку A ведут пять мостов, а к остальным – по три моста, т. е. Число мостов, ведущих к отдельным участкам, нечетно, а этого одного уже достаточно для решения задачи. Когда это определено, применяем следующее правило: если бы число мостов, ведущих к каждому отдельному участку, было четным, то тогда обход, о котором идет речь, был бы возможен, и в то же время можно было бы начать этот обход с любого участка. Если же из этих чисел два были бы нечетные, ибо только одно быть нечетным не может, то и тогда мог бы совершиться переход, как это предписано, но только начало обхода непременно должно быть взято от одного из тех двух участков, к которым ведет нечетное число мостов. Если бы, наконец, было больше двух участков, к которым ведет нечетное число мостов, то тогда такое движение вообще невозможно… если можно было привести здесь другие, более серьезные задачи, этот метод мог бы принести еще большую пользу и им не следовало бы пренебрегать".

Приложение 3

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

Результаты оказались следующими: