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

Старт в науке

Графы в математике и в жизни

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

Фардиева И.Р. 1

---

1ГАОУ "Гуманитарная гимназия-интернат для одарённых детей"

Фардиева Р.Р. 1

---

1ГАОУ "Гуманитарная гимназия-интернат для одарённых детей"

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

1.7 MB

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

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

Введение

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

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

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

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

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

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

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

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

Для реализации поставленной цели выдвинуты задачи:

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

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

Составить собственные задачи.

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

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

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

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

Моделирование.

.Глава I. Теоретические аспекты графов

Основные понятия теории графов.

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

Рисунок 1. Граф

Виды графов.

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

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

3. Граф - дерево. Деревом называется всякий связный граф, не имеющий циклов (Рис4).

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

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

6. Связный граф. Две вершины А и В графа называются связными, если в графе существует путь с концами А и В. Граф называется связным, если каждые две вершины его связные.(Рис.7)

7. Несвязный граф. Две вершины графа называются несвязными, если в графе не существует ни одного пути, связывающего их. Граф называется несвязным, если хотя бы две вершины его не­связные (Рис. 8)

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

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

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

Длиной пути называется число ребер этого пути.

Длиной цикла называется число ребер в этом цикле.

Степени вершин и подсчет числа ребер.

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

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

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

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

Закономерность 3 Невозможно начертить граф с нечетным числом нечетных вершин.

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

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

Закономерность 6. Граф, имеющий более двух нечетных вершин, невозможно начертить «одним росчерком». Фигура (граф), которую можно начертить не отрывая карандаш от бумаги, называется уникурсальной) [4]

Глава II. Применение теории графов на практике

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

- научиться строить различные виды графов на примерах из жизни (Приложение 2)

- научиться применять графы при решении олимпиадных задач и задач ОГЭ и ЕГЭ по математике и информатике;

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

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

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

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

Графы широко применяются при решении логических и олимпиадных задач.

Пример 1: Имеется шахматная доска 3x3, в верхних двух углах стоят два чёрных коня, в нижних – два белых (Рис. 11). За какое минимальное количество ходов можно поставить белых коней на место чёрных, а чёрных на место белых [9].

 Занумеруем поля доски (кроме центрального) в порядке обхода их шахматным конём (рис 12); белые кони стоят на полях 1 и 3, чёрные — на полях 5 и 7. Рассмотрим вспомогательную схему, изображённую на рис.13.

Ответ: 16 ходов, т. к. фигура не может встать на занятую клетку, каждой приходится делать 2 круга.

Пример 2. Задача про лабиринты. Как можно попасть в центр и выйти из неё (Рис.14). [9]

Рисунок 14. Лабиринт

Решение :Построим соответствующий ему граф (рис.15). Коридоры лабиринта - это ребра графа, а перекрестки, тупики, входы и выходы - это вершины.

Рисунок 15 Граф, соответствующий лабиринту

Теперь хорошо видно, что в центр лабиринта можно попасть, следуя по следующим вершинам: 1 - 4 - 7 - 10 - 9 - 11 - 12 - 13. И, соответственно, выйти из центра лабиринта по маршруту: 13 - 12 - 11 - 9 - 10 - 7 - 4 - 1.

Пример 3. (Задание №20 базового ЕГЭ  № 506731) Кузнечик прыгает вдоль координатной прямой в любом направлении на единичный отрезок за прыжок. Сколько существует различных точек на координатной прямой, в которых кузнечик может оказаться, сделав ровно 6 прыжков, начиная прыгать из начала координат?[8]

Решение. Если построить граф к данной задаче (Рис. 16), то чётко видно, что это точки: : -6, -4, -2, 0, 2, 4, 6.

Рисунок 16. Граф к условию задачи

Ответ: 7

Графы применяются при решении задачи №11 ОГЭ и задачи №15 ЕГЭ по информатике. Рассмотрим, один из таких задач на примере.

Пример 4: На рисунке 17 схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, И, К, Л. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город Л? [8]

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

2.2. Авторские задачи

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

Задача №1. У Ислама 3 рубашки – белая, голубая и фиолетовая и два костюма – синий и чёрный. Сколько у него вариантов подбора одежды?

Задача №2. Айзиля, Алия, Алиса и Алина занимаются различными видами спорта (баскетбол, волейбол, пионербол и теннис), но каждая только на одном. Эти же ученицы владеют разными иностранными языками (английским, французским, немецким и испанским), но каждая знает только один из них. Известно что:

- та, которая играет пионербол, говорит по-испански;

- Алия не играет ни в теннис, ни в баскетбол и не знает английского языка;

- Айзиля не играет ни в теннис, ни в баскетбол и не знает ни немецкого, ни английского языка;

- та, которая говорит по-немецки, не играет в баскетбол;

- Алиса знает французский, но не играет в теннис.

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

Задача №3.При встрече каждый из моих одноклассников пожал руку другому (каждый пожал каждому). Сколько рукопожатий было сделано, если друзей было в нашем классе 5.

Задача №4. В 7ом классе гимназии 28 человек. Может ли быть так, что 9 человек имеют по 3 друга, 11 – по 4 друга, а 10 – по 5 друзей?

Задача №5. У меня 17 подружек. Может ли оказаться так, что у каждой девочки 1, 3 или 7 знакомых среди моих подружек?

2.4. Применение теории графов в различных сферах деятельности.

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

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

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

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

Инженер чертит схемы электрических цепей.

Историк прослеживает родословные связи по генеалогическому дереву.

Военачальник наносит на карту сеть коммуникаций, по которым из тыла к передовым частям доставляется подкрепление.

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

Даже в литературе графы применяются для определения точности перевода (Приложение 6).

Выводы

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

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

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

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

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

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

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

Генкин, С. А, Итенберг И. В. Ленинградские математические кружки: пособие для внеклассной работы.-Киров, 2004г.

Горбачев, В.Г. Сборник олимпиадных задач по математике.- М., 2004г

«За страницами учебника математики (открытые уроки, математические кружки, подготовка к олимпиадам)», С.А. Литвинова, Л.В. Куликова, С.В. Шиловская, Г.Ю. Тараева, О.Л. Безрукова, 2-е издание, дополненное, г. Волгоград: «Панорама», 2008

«Решение задач с помощью графов», Л.Н. Харламова, Волгоград: Учитель, 2007.

Перельман, Я.И. Весёлые задачи.- Москва, 2003г

http://school-sector.relarn.ru/dckt/projects/ctrana/graf/gr1.htm

http://www.comprice.ru/articles/detail.php

ege.sdamgia.ru

http://www.problems.ru/

Приложение 1. История возникновения графов

И

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

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

П

оявление теории графов, как математической дисциплины, все единодушно относят к 1736 году, когда Леонард Эйлер (1707-1782), российский математик, швейцарец по происхождению, академик Петербургской и Берлинской академии наук, решил широко известную в то время задачу о Кёнигсбергских мостах.

Б

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

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

Получился граф, вершины которого–части города, а рёбра–мосты.

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

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

2) Замкнутый путь, проходящий по одному разу по всем рёбрам графа, называют с тех пор эйлеровым циклом.

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

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

Этот результат более ста лет оставался единственным в теории графов.

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

К

ак отдельная математическая дисциплина теория графов была впервые представлена в 1936 году в монографии австрийского математика Д.Кинега «Теории конечных и бесконечных графов», к сожалению, не переведённой на русский язык.

Так же над теорией графов работали Уильям Гамильтон (1805-1865), из современных математиков – К. Берж, О. Оре, А. Зыков.

Математические развлечения и головоломки тоже являются частью теории графов.

Теория графов быстро развивается, находя все новые приложения.

Приложение 2. Примеры построения различных видов графов из жизни

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

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

Для наглядности я решила построить свою родословную. Где вершинами являются мои родственники, а рёбра – родственные отношения (Рис. 12).

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

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

Как видно из рисунка, до финальной игры каждый участник сыграл по 3 партии.В результате этого соревнования «чемпионом» стала Амирханова Рамиля.

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

Одним из вопросов анкеты, которую мы предложили своим одноклассникам, был следующий: «Какие предметы ( указать 2) ты хочешь изучать в дополнительное время?» В анкетировании принимали участие 6 человек.

При обработке ответов мы получили следующие данные: английский язык выбрали – 5 человек, турецкий язык – 3 человека, русский язык – 4 человека.

Ответы на этот вопрос мы изобразили в виде следующего графа:

Приложение 3. Решения авторских задач

Задача №1. У Ислама 3 рубашки – белая, голубая и фиолетовая и два костюма – синий и чёрный. Сколько у него вариантов подбора одежды?

Рисунок 21. Выбор вариантов подбора одежды

Ответ: 6 вариантов.

Задача №2. (для самостоятельного решения) Айзиля, Алия, Алиса и Алина занимаются различными видами спорта (баскетбол, волейбол, пионербол и теннис), но каждая только на одном. Эти же ученицы владеют разными иностранными языками (английским, французским, немецким и испанским), но каждая знает только один из них. Известно что:

- та, которая играет пионербол, говорит по-испански;

- Алия не играет ни на скрипке, ни в баскетбол и не знает английского языка;

- Айзиля не играет ни в теннис, ни в баскетбол и не знает английского;

- та, которая говорит по-немецки, не играет в баскетбол;

- Алиса знает французский, но не играет в теннис.

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

Задача №3.При встрече каждый из моих одноклассников пожал руку другому (каждый пожал каждому). Сколько рукопожатий было сделано, если друзей было в нашем классе 5.

Ответ: 10 рукопожатий

Задача №4. В 6ом классе гимназии 28 человек. Может ли быть так, что 9 человек имеют по 3 друга, 11 – по 4 друга, а 10 – по 5 друзей?

Ответ. Нет (по теореме о четности числа нечетных вершин).

Задача №5. У меня 17 подружек. Может ли оказаться так, что у каждой девочки 1, 3 или 7 знакомых среди моих подружек?
Ответ. Нет, не может. В противном случае получился бы граф из девочек с нечётным количеством подружек.

Приложение 4. Графы в химии, физике, биологии информатике

Графы и химия;

Еще А. Кэли рассмотрел задачу о возможных структурах насыщенных (или предельных) углеводородов, молекулы которых задаются формулой: CnH2n+2 Все атомы углеводорода четырехвалентны, все атомы водорода одновалентны. Структурные формулы простейших углеводородов показаны на рисунке 3.1 (а – метан CH4, б – этан C2H6). (РИСУНОК 3.1) Молекула каждого предельного углеводорода представляет собой дерево. Если удалить все атомы водорода, то оставшиеся атомы углеводорода также будут образовывать дерево, каждая вершина которого имеет степень не выше 4. Следовательно, число возможных структур предельных углеводородов, т. е. число гомологов данного вещества, равно числу деревьев с вершинами степени не больше четырех. Таким образом, подсчет числа гомологов предельных углеводородов также приводит к задаче о перечислении деревьев определенного типа. Эту задачу и ее обобщения рассмотрел Д. Пойа.

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

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

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

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

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

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

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

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

Приложение 4. Профессия логист

Профессия логист

О писание профессии:

Это специалист, который координирует движение товаров на пути от производства до точек реализации.

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

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

Цепочка может выглядеть, например, так: закупка товаров у иностранного поставщика - их страхование - перевозка - растаможивание (прохождение таможенного контроля, уплата пошлин) - складирование - упаковка и/или снабжение русскоязычными этикетками и документацией - распределение по оптовым торговым базам - продажа в розничной сети.

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

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

Приложение 6. Графы, как инструмент для определения точности перевода

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

А теперь выясним, по какому принципу лингвисты проводят анализ художественного текста. И.П. Севбо привел семь таких признаков, мы приведём для примера четыре.

Количество узлов дерева (т.е. количество слов во фразе).

Количество простых предложений в сложном. 

Число уровней в дереве (длина самого длинного из путей дерева).

Ширина ветвления корня (число узлов подчиненных корню).
Проведём эксперимент. Перед нами строки из произведения

«Кемнәрбиек мөнбәр биләгән...» Гамиля Афзала и перевод М.Сафина. 

Кемнәр биек мөнбәр биләгән дә, Кто только с неба звезд здесь не хватал,

Кемнәр күктән йолдыз чүпләгән, Кто только в креслах здесь не хлопотал,

Елый-елый кемнәр килмәгән дә, Кто только,горько обидясь, не плакал,

Янып-көеп кемнәр китмәгән. Кто только здесь о невзгодах не каркал.
Проверим , на сколько точен перевод, и сделаем это с помощью Севбо.

Теперь начертим графы строк этих стихотворений

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