XVI Международный конкурс научно-исследовательских и творческих работ учащихся
Старт в науке. Летняя площадка 2022
Решение задач с помощью графов
Автор работы награжден дипломом победителя III степени
Полная версия работы доступна во вкладке "Файлы работы" в формате PDF
ВВЕДЕНИЕ
Теория графов как область математики, особенностью которой является геометрический подход к изучению объектов, привлекает все более пристальное внимание специалистов различных областей знаний.
Актуальность исследования: при решении многих логических и математических задач, головоломок можно применять графы. Желание быстро их решать, сподвигло меня к более тщательному изучению теории графов. Раньше данный термин мне был знаком только по урокам истории, но, оказывается, графы есть и в математике.
Объект исследования: понятие графа, решение задач с помощью графов.
Цель исследования: исследовать роль графов в решении задач по математике.
Задачи исследования:
познакомиться с историей возникновения графов;
познакомится с основными понятиями графов, видами, элементами;
научиться решать задачи с помощью графов.
Графы являются очень удобным средством для описания самых разнообразных систем и их анализа. Метод графов применяется тогда, когда между объектами, о которых идет речь в задаче, существует много связей. Граф позволяет наглядно представить эти связи и определить, какие из них не противоречат. В настоящее время эта теория находит многочисленное применение в разнообразных практических вопросах: при установлении разного рода соответствий, при решении транспортных задач, задач о потоках в сети нефтепроводов, в программировании игр и т .д.
Знание основ теории графов необходимо и широко применяется в таких областях, как экономика и бизнес (например, сетевой график строительства, графики доставки почты и т.д.), психология, биология, химия. Схемы метро и авиалиний, карты автодорог также являются примерами графов. В повседневной жизни мы все часто сталкиваемся с такими вопросами: как спланировать оптимальный маршрут, найти кротчайший объездной путь до магазина, места отдыха и т.д. Эти вопросы могут быть разрешены с помощью графов.
История возникновения теории графов.
Родоначальником теории графов принято считать математика Леонарда Эйлера (1707-1783). Однако теория графов многократно переоткрывалась разными авторами при решении различных прикладных задач.
В 1736 году Л.Эйлером (1707-1783 г.г.), который является автором более 800 научных работ, в «Записках Петербургской академии наук» была опубликована статья, в которой приводилось решение широко известной теперь задачи о Кёнигсбергских мостах (чуть позже мы рассмотрим эту задачу). Разумеется, работа содержала не только отрицательный ответ на вопрос о возможности обойти все семь мостов города Кёнигсберга так, чтобы по каждому из них пройти только один раз. В ней великий математик сформулировал и обосновал принцип, позволяющий отвечать на данный вопрос для любого графа.
Но эта статья оказалась единственной почти в течении столетия. Вначале теория графов казалась довольно незначительным разделом математики, так как она имела дело в основном с математическими развлечениями и головоломками. Однако дальнейшее развитие математики и особенно её приложений дало сильный толчок развитию теории графов.
В XIX веке возродился интерес к теории графов. Графы начали использовать при построении схем. Широкое развитие теория графов получила с 50-х гг. 20 в. В связи со становлением кибернетики и развитием вычислительной техники.
Термин ГРАФ подразумевает наличие наглядной графической интерпретации (модели) рассматриваемого объекта. Граф - это (не пустое) множество вершин и множество соединяющих их ребер. Таким образом, граф определяется множеством вершин, и множеством ребер.
При изображении графа на рисунках, отрезки (рёбра) могут быть криволинейными и прямолинейными, а длины отрезков и расположение точек произвольным. Путь называется простым, если он не проходит ни через одну из вершин графа более одного раза.
Циклом называется путь, в котором совпадают его начальная и конечная вершины. Простым циклом в графе называется цикл, не проходящий ни через одну из вершин графа более одного раза. Слово «дерево» в теории графов означает граф, в котором нет циклов, то есть в котором нельзя из некоторой вершины пройти по нескольким различным ребрам и вернуться в ту же вершину.
Решение задач с помощью графов
В школьном курсе математики наиболее часто встречаются задания на следующие темы:
1) задачи на построение уникурсальных графов
2) логические задачи
3) задачи о «правильном» раскрашивании карт
4) задачи коммивояжера
Рассмотрим задачи на данные темы.
Задачи на построение уникурсальных графов
Принято всякую замкнутую линию, если ее можно начертить, не отрывая карандаша от бумаги, проходя при этом каждый участок в точности один раз, называть уникурсальной (эйлеровым графом).
Задача №1 Вычерчивание фигур одним росчерком.
Решая задачу про Кенигсбергские мосты, Эйлер установил следующие свойства графа:
Граф с более чем двумя нечётными вершинами, невозможно начертить одним росчерком.
Если все вершины графа чётные, то можно одним росчерком (т.е. не отрывая карандаша от бумаги и не проводя дважды по одной и той же линии) начертить граф.
Граф с двумя нечётными вершинами тоже можно начертить одним росчерком. Движение нужно начинать от любой нечётной вершины, а заканчивать на другой нечётной вершине. Надо заметить, что если в графе более 2 нечетных вершин, то наименьшее число росчерков, которыми можно нарисовать граф, равно половине числа нечетных вершин.
Можно ли обвести изображения графов на рисунке, не отрывая карандаша от бумаги и не проходя уже по обведенному ребру вторично
Решение:
Рассмотри рисунок (ж). На рисунке изображена птица. Взяв за вершины графа точки пересечения линии, получим 7 вершин, только две из которых имеют нечетную степень.
Поэтому в этом графе существует эйлеров путь, а значит, его (т.е. птицу) можно нарисовать одним росчерком.
Задание по обведению ребер удается выполнить для графов на рисунках (а, б, г, д). Графы на рисунках (в, е) нарисовать без отрыва карандаша от бумаги или, не проходя дважды по ребрам, не удастся
Задача № 2
Шесть островов на реке в парке "Лотос" соединены мостами. Можно ли, начав прогулку на одном из островов, пройти по каждому из мостиков ровно один раз и вернуться на тот же остров? В случае отрицательного ответа определите, сколько мостиков и между какими островами нужно построить, чтобы такая прогулка стала возможной.
Решение:
Построим граф G, в котором каждому участку суши поставим в соответствие вершину и соединим две вершины ребром тогда и только тогда, когда соответствующие участки суши будут соединены мостом.
Рассмотрим построенный граф G. В этом графе вершины 2 и 4 имеют нечетную степень, следовательно, граф G не является эйлеровым. Это означает, что желаемую прогулку по мостикам совершить нельзя.
Если же соединить ребром вершины 2 и 4, то степень всех вершин нового графа будет четной, а сам граф будет эйлеровым. Поэтому после постройки моста, соединяющего острова 2 и 4, можно найти маршрут прогулки по мостикам, начинающийся и заканчивающийся в одном месте, при котором каждый мостик будет пройден ровно один раз.
Задача№ 3 «Муха в банке»
Муха забралась в банку из-под сахара. Банка имеет форму куба. Сможет ли муха последовательно обойти все двенадцать ребер куба, не проходя дважды по одному ребру. Подпрыгивать и перелетать с места на место не разрешается.
Решение:
Является ли куб эйлеровым графом? Куб представляет собой граф, у которого все вершины имеют степень 3. Для того чтобы был эйлеровым нужно, чтобы все его вершины были четными, а это условие в данном случае не выполняется. Следовательно, граф не является эйлеровым. Значит, муха не сможет обойти все ребра куба, не проходя по одному ребру дважды.
Задача№ 4
Экспозиция картинной галереи представляет собой систему коридоров, на обоих стенах которых развешены картины (схема представлена на рисунке. Можно ли предложить такой маршрут осмотра экспозиции, при котором посетитель проходит вдоль каждой стены ровно один раз.
Решение:
Превратим схему коридора в мультиграф, заменив каждый коридор двумя рёбрами.
Полученный граф называется эйлеровым, поскольку степень его вершины чётная. Можно найти эйлеров цикл в графе. Этот цикл и определит нужный маршрут.
Задача№ 5
Можно ли нарисовать фигуру, изображённую на рисунке не отрывая карандаша от бумаги, причём каждую линию фигуры, карандаш должен проходить только один раз.
Решение:
Рассмотрим граф, связанный с фигурой
Степени вершин 1 и 2 графа нечётные. Если мы соединим ещё одним ребром эти вершины, то получим уникурсальный граф. Построим эйлеров цикл. Удалим из цикла добавленное ребро, получим цикл, который начинается в вершине 1 и заканчивается в вершине 2 и содержит каждое ребро графа ровно один раз. Построенный цикл определяет движение карандаша при рисовании фигуры.
Задача№ 6
Имеется план помещения, где будет проходить выставка. Закрашенные места - это подсобные nомещенuя, незакрашенные - территорuя выставки. Можно ли составить карту маршрута таким образом, чтобы каждый посетитель прошёл по территории выставки один раз?
Решение:
Определим местоположение вершин будущего графа. Нетрудно догадаться, что они будут располагаться на месте входов в «коридоры» территории выставки. Мы поставим их таким образом, как показано на рисунке:
Что мы имеем? Ничего, пока не построим граф. Соединим вершины рёбрами и получим такой граф:
Для того чтобы ответить на вопрос задачи - можно ли пройти по территории выставки, осмотреть все экземпляры, не повторяясь в просмотрах, и вернуться к выходу за один раз, - нужно определить, является ли граф эйлеровым. И если да, найти эйлерову цепь.
Для начала посчитаем степени вершин графа, то есть количество рёбер, из них выходящих. Нетрудно заметить, что из каждой вершины выходит по четыре ребра, степени всех вершин - чётные, а это значит, что построенный граф является эйлеровым, Следовательно, в этом графе существует эйлерова цепь. Значит ответ – да.
Логическиезадачи
Задача№ 1
Беседуют трое молодых людей: Белокуров, Чернов и Рыжов. Брюнет сказал Белокурову: «Любопытно, что один из нас русый, другой - брюнет, а третий -рыжий, но никакой цвет волос не соответствует фамилии». Какой цвет волос имеет каждый из беседующих?
Решение:
Сплошной линией обозначены соответствия, пунктирной –несоответствия.
Задача № 2
Пытаясь вспомнить победителей прошлогоднего турнира, пять бывших зрителей турнира заявили:
- Антон был вторым, а Борис - пятым.
- Виктор был втopым, а Денис - третьим.
- Евгений был первый, а Борис - третьим.
- Антон был третьим, а Григорий - шестым.
- Виктор был третьим, а Григорий - четвертым.
Впоследствии выяснилось. что каждый зритель ошибся в одном из двух своих высказываний. Каково было истинное распределение мест в турнире? Решение:
Задача № 3
Купленные в подарок игрушки ( пистолет, сумочка, кукла и машина) уложили в коробки (красная, синяя, желтая, зеленая). Требуется узнать, что лежит в каждой коробке, если известно: машинка и пистолет не в красной коробке; сумочка находится между синей коробкой и коробкой с куклой; в зеленой - не сумочка и не машинка; желтая и зеленая коробки находятся возле коробки с пистолетом.
Для решения построим граф:
Ответ: Сумочка в красной коробке, пистолет - в синей, кукла - в зеленой, машинка - в желтой коробках.
Заключение
В проведённом исследовании были рассмотрены математические графы, области их применения, решены задач с помощью графов. Графы достаточно широко применяются в математике, технике, экономике, управлении. Знание основ теории графов необходимо в различных областях, связанных с управлением производством, бизнесом (например, сетевой график строительства, графики доставки почты).
В работе решены задачи из теории графов, многие из которых уже стали классическими. Изучая теорию о графах, я узнала области применения теории графов и сделала вывод, что этот раздел математики является одним из важнейших, который используется в нашей повседневной жизни, но часто незаметно для нас. Я их сама раньше не замечала, но теперь понимаю, что и простой поход в магазин можно изобразить с помощью графов.
Очень интересно решать задачи с помощью графов, кроме того они способствуют развитию воображения и логического мышления. Раньше я и представить не могла, что математика может быть такой интересной.
После проведения данной работы я узнала много интересного и полезного и стала любить математику ещё сильнее.
Литература
Занимательная математика. 5 - 11 классы. (Как сделать уроки математики нескучными)/ Авт.-сост. Т. Д. Гаврилова. - Волгоград: Учитель, 2005. -96 с.
Энциклопедический словарь юного математика, сост .А.П.Савин.- М.:
Педагогика, 1989
«Соросовский образовательный журнал» № 11 1996 (ст. "Плоские графы");
Гарднер М. "Математические досуги", М. "Мир", 1972(глава 35);
Олехник С. Н., Нестеренко Ю. В., Потапов М. К. "Старинные занимательные задачи", М. "Наука", 1988(часть 2, раздел 8; приложение 4);
Гарднер М. "Математические головоломки и развлечения", М. "Мир", 1971;
Лекции по теории графов. / Емеличев В.А., Мельников О.И. и др. М.: Наука, 1990.