XIX Международный конкурс научно-исследовательских и творческих работ учащихся
Старт в науке
ГРАФЫ ПОВСЮДУ
Автор работы награжден дипломом победителя III степени
Полная версия работы доступна во вкладке "Файлы работы" в формате PDF
Введение
Актуальность работы. В современном мире математика используется не только как инструмент расчетов, но и способствует решению задач выбора наиболее эффективного варианта в реальных жизненных проблемах. Одним из методов решения таких задач является метод математического моделирования, а одним из его инструментов - теория графов. К сожалению, теории графов незаслуженно уделено мало внимания в школьной программе. В учебнике Математика за 6 класс под редакцией Г.В. Дорофеева, по которому я учусь, представлены задачи в разделе комбинаторика (глава 10.4 Комбинаторика, стр. 221 - 227), решение которых осуществляется с применением графов.
Проблема: не хватает знаний для решения ряда олимпиадных задач и умений моделировать практические ситуации.
Цель: изучить основы теории графов и научится применять её при решении ряда олимпиадных задач по математике.
Задачи:
найти и изучить теоретический материал по выбранной теме;
показать практическое применение теории графов в различных областях знаний;
продемонстрировать применения теории графов при решении различных задач.
Гипотеза: теория графов широко применяются в жизни. Если её изучить, то решение многих сложных задач становится простым.
Объект исследования: математические графы.
Предмет исследования: применение графов в разных видах деятельности, как способ решения целого ряда задач практической направленности.
Методы и приёмы: поиск, анализ, синтез информации, обобщение, систематизация, сравнение, составление математических моделей.
Новизна работы заключается в изучении теоретического материала по данной теме, выходящей за пределы школьной программы.
Практическая значимость:
Сформировалось целостное представление о теории графов.
Приобретён успешный опыт применения знаний, полученных при выполнении работы для решения математических задач.
Модели графов, изготовленные в результате работы, можно использовать, как наглядное пособие на уроках наглядной геометрии или факультативах по математике.
Приобретён опыт представления повседневных ситуаций в виде математической модели-графа.
Описание основных источников информации:
Математика: Наглядная геометрия. 5— 6 кл.: учебник / И. Ф. Шарыгин, Л. Н. Ерганжиева. — М.: Дрофа, 2015. — 189 с.
Содержание учебника направлено на развитие геометрической интуиции, пространственного воображения навыков учащихся. Включение в учебник интересных задач, исторических сведений, примеров влияния геометрии на архитектуру и искусство, а также головоломок, лабиринтов орнаментов и др. способствует развитию интереса к изучению геометрии.
Математическая составляющая / Редакторы-составители Н. Н. Андреев, С. П. Коновалов, Н. М. Панюнин. — М.: Фонд «Математические этюды», 2019. — 367 с.
В сюжетах, собранных в книге, рассказывается как о математической «составляющей» крупнейших достижений цивилизации, так и о математической «начинке» привычных, каждодневных вещей. Увлекательный, популярно-описательный стиль изложения делает материалы книги доступными для широкого круга читателей.
Теория графов/ А. В. Омельченко. — М.: МЦНМО, 2018. — 416 с.
Учебник, в котором рассматриваются основные темы: деревья, циклы, связность в графах, паросочетания, раскраски графов, планарные графы. С одной стороны, изложение математически строгое с доказательством теорем, с другой стороны — новые понятия иллюстрируются большим числом примеров. К каждому параграфу приводится список задач и эти задачи — серьезное преимущество учебника. Они в основном нестандартные, направлены на глубокое усвоение понятий, а не на отработку стандартных приемов.
Школьные математические кружки. Графы / В. М. Гуровиц., В. В Ховрина. — М.: МЦНЦО, 2008. — 367 с.
Вторая брошюра серии ШКОЛЬНЫЕ МАТЕМАТИЧЕСКИЕ КРУЖКИ посвящена графам. В ней приведены четыре занятия по этой теме, в которых подобран материал для начального знакомства с графами, адресованный школьникам 6-8 классов и руководителям кружков. Несмотря на то, что в школьном курсе математики термин "граф" отсутствует, авторам представляется важным познакомить школьников с этим объектом, научить оперировать существующими терминами и использовать их при решении задач.
Из истории возникновения теории графов
Первая половина XVIII века
Рис. 1
Родоначальником теории графов принято считать математика Леонарда Эйлера (1707-1783, российский математик, швейцарец по происхождению, академик Петербургской и Берлинской академии наук). Он решает "задачу о кёнигсбергских мостах" (рис.1) - доказывает, что в Кёнигсберге, расположенном на берегах реки Прегель и двух её островах, нельзя было пройти по каждому из семи мостов, существовавших в то время, ровно один раз и вернуться после этого в исходную точку. Леонардо Эйлер предложил изящное решение этой задачи, а также придумал общий метод решения подобных задач.
Вторая половина XIX века
Математик Уильямс Гамильтон рассматривает внешне похожую на эйлерову задачу: найти на графе замкнутый путь, проходящей через каждую вершину по одному разу.
XX век
Широкое развитие теория графов получила с 50-х годов 20 века в связи со становлением кибернетики и развитием вычислительной техники. Было установлено, что замкнутый гамильтонов цикл (в отличие от замкнутого эйлерова цикла) является представителем класса задач, для которых эффективные алгоритмы решения не известны.
Конец XX века – XXI век
В середине 1990-х годов был севенирован геном бактерии, в 2001 году - человека. Математиками были разработаны быстродействующие методы сборки, связанные с замкнутым эйлеровым циклом.
Основные положения теории графов
Термин «графы» впервые ввел в 1936 году венгерский математик Денеш Кениг. Фигура, образованная конечным набором точек плоскости и отрезков, соединяющих некоторые пары из этих точек, называется плоским графом или просто графом. Точки называются вершинами, а отрезки - ребрами графа. Две вершины называют смежными (или соседними), если они соединены ребром. Ребра смежные, если они имеют общую вершину.
Рис. 2 Рис. 3 Рис. 4
Г раф называется связным, если любые две его вершины можно соединить ломаной, состоящей из рёбер графа. Вместо отрезков в качестве рёбер рассматриваются также кривые линии. Схема графа (рис.2), состоящая из «изолированных» вершин, называется нулевым графом. Графы, в которых не построены все возможные ребра, называются неполными графами (рис.3). Графы, в которых построены все возможные ребра, называются полными графами (рис.4).
Количество рёбер, выходящих из вершины графа, называется степенью вершины. Вершина графа, имеющая нечётную степень, называется нечетной, а чётную степень – чётной.
Граф, который можно нарисовать так, чтобы его рёбра не пересекались нигде, кроме вершин, называются плоским или планарным.
Теорема: Сумма индексов вершин равна удвоенному числу рёбер этого графа.
Доказательство: Индекс вершины - это число рёбер, выходящих из этой вершины. Сумма индексов всех вершин – это число рёбер выходящих из всех вершин. При таком подсчёте мы каждое ребро посчитаем дважды. Следовательно, сумма индексов вершин равна удвоенному числу индексов этого графа.
Следствие: Число вершин с нечётным индексом чётно.
Доказательство: Действительно, если б оно было нечётно, то сумма индексов вершин графа была бы нечётной. С другой стороны, сумма индексов вершин графа с чётным индексом чётна. Но тогда сумма индексов вершин графа была бы нечёта, что противоречит теореме.
Графы называют уникурсальными если по каждому ребру этого графа можно пройти один раз, или, что то же самое, нарисовать граф «одним росчерком», т.е. не отрывая карандаша от бумаги и проходя по каждому ребру ровно один раз.
Теорема Эйлера
Для уникурсального графа число вершин нечётного индекса равно нулю или двум.
Рис. 5
б)
Рис. 5
а)
Д оказательство: Если граф уникурсален, то у него есть начало и конец обхода. Остальные вершины имеют чётный индекс, так как с каждым входом в такую вершину есть и выход. Если начало A и конец B не совпадают (рис.5, а), то они являются единственными вершинами нечётного индекса. У начала выходов на один больше, чем входов, а у конца входов на один больше, чем выходов. Если начало A совпадает с концом B(рис.5, б), то вершин с нечётным индексом нет.
Верно и обратное утверждение. Если у связного графа число вершин нечётного индекса равно 0 или 2, то этот граф уникурсален.
Следствие:
Если все вершины графа четные, то можно не отрывая карандаш от бумаги («одним росчерком»), проводя по каждому ребру только один раз, начертить этот граф. Движение можно начать с любой вершины и закончить его в той же вершине.
Граф, имеющий всего две нечетные вершины, можно начертить, не отрывая карандаш от бумаги, при этом движение нужно начать с одной из этих нечетных вершин и закончить во второй из них.
Граф, имеющий более двух нечетных вершин, невозможно начертить «одним росчерком».
Решение задачи Эйлера
Рис. 6
Найдем индексы вершин графа задачи Эйлера (рис.6). Вершина А имеет индекс 5, Б – 3, П – 3 и Л – 3. Таким образом, мы имеем четыре вершины нечётного индекса, и, следовательно, данный граф не является уникурсальным. Значит, нельзя пройти по каждому из семи мостов только один раз.
Теорему Эйлера и следствия из неё можно успешно применять для решения разных олимпиадных задач.
Задача 1. На рисунке 7 изображён план подземелья, в одной из комнат которого находится клад, для отыскания которого нужно войти в одну из крайних комнат, пройти через все двери ровно по одному разу через каждую. Клад будет в комнате за последней дверью. В какой комнате находится клад?
Р ешение. Клад находится в комнате 18. На рисунке две комнаты имеют нечётное количество дверей нечётное - 6 и 18. Согласно условию задачи войти нужно в одну из крайних комнат, значит в комнату 6, тогда клад будет в последней комнате - 18.
Рис. 7
Задача 2. Есть моток проволоки. Можно ли, не ломая проволоки, изготовить каркас куба?
Решение. Нельзя, так как в кубе вершины представляют собой узлы графа, где сходятся по три ребра. Такие узлы называют "нечетными". Нельзя построить граф, не отрывая карандаша от бумаги, если в графе больше двух нечетных узлов. В кубе – 8 нечетных вершин.
Задача 3. Выясните, какие фигуры, изображенные на рисунке 8, можно нарисовать «одним росчерком», т.е. не отрывая карандаша от бумаги и проходя по каждому ребру ровно один раз?
Рис. 8
Ответ: а), б), г), д), ж), з).
Задача 4. В первенстве школы по шашкам 6 участников: Андрей, Борис Виктор, Галина, Дмитрий и Елена. Первенство проводят по круговой системе – каждый из участников играет с каждым из остальных один раз. К настоящему моменту некоторые игры уже проведены: Андрей сыграл с Борисом, Галиной, Еленой; Борис – с Андреем, Галиной; Виктор – с Галиной, Дмитрием, Еленой; Галина – с Андреем, Виктором и Борисом. Сколько игр проведено к настоящему моменту и сколько еще осталось?
Решение. Всего необходимо сыграть , сыграно 7 игр, а осталось – 8.
Теорема Эйлера 2
Для связного простого графа имеет место равенство , где В - число вершин, Р - общее число рёбер, Г- число областей, на которые граф разбивает плоскость.
Н апример, для изображённого графа (рис.9, а), В = 8, Р = 12, Г = 6.
а) б) в) г) д)
Рис. 9
Доказательство:
Стянем какое-нибудь ребро связного простого графа, соединяющее две его вершины, в точку (рис7, б). При этом число рёбер и число вершин уменьшится на единицу, а число областей не изменится. Следовательно, В – Р + Г не изменится. Продолжая стягивать рёбра (рис. 9, в, г, д), мы придём к графу, у которого имеется одна вершина, а рёбрами являются петли. Уберём какое-нибудь ребро. При этом число рёбер и число областей уменьшится на единицу. Следовательно, В – Р + Г не изменится. Продолжая убирать рёбра, мы придём к графу, у которого имеется одна вершина и одно ребро. У этого графа В = 1, Р = 1, Г = 2 и, следовательно, . Значит, для исходного графа также выполняется равенство .
Задача Эйлера 2:
Т ри соседа имеют три общих колодца. Можно ли провести непересекающиеся дорожки от каждого дома к каждому колодцу?
Рис. 10
То что не получилось на рисунке 10, не является доказательством невозможности соединения дорожками домиков и колодцев. Для доказательство воспользуемся теоремой Эйлера 2. Предположим, что можно провести непересекающиеся дорожки от каждого дома к каждому колодцу . Рассмотрим граф, вершинами которого являются домики и колодцы, а рёбрами – дорожки. У него В = 6, Р = 9 и, следовательно, Г = 5. Каждая из пяти областей ограничена, по крайней мере, четырьмя рёбрами, поскольку, по условию задачи, ни одна из дорожек не должна непосредственно соединять два дома или два колодца. Так как каждое ребро разделяет две области, то количество рёбер должно быть не меньше , что противоречит тому, что их число равно 9.
Рассмотрим ещё несколько похожих задач.
Задача 5. Два соседа имеют: а) три общих колодца; б) четыре общих колодца. Можно ли провести непересекающиеся дорожки от каждого дома к каждому колодцу?
Ответ: а), б) да.
Задача 6. Три соседа имеют: а) два общих колодца; б) четыре общих колодца. Можно ли провести непересекающиеся дорожки от каждого дома к каждому колодцу?
Ответ: а) да; б) нет.
Задача 7. Четыре соседа имеют четыре общих колодца. Можно ли провести непересекающиеся дорожки так, чтобы каждый домик был соединён с тремя колодцами и каждый колодец соединён с тремя домиками?
Ответ: Да.
Задача 8. Докажите, что пять домиков нельзя соединить непересекающимися дорожками так, чтобы каждый домик был соединён со всеми другими домиками.
Доказательство. Предположим, что это сделать можно. Тогда мы имеем связный простой граф, у которого В = 5, Р = 10 и, следовательно, Г = 7. С другой стороны, поскольку
каждая область ограничена, по крайней мере тремя рёбрами, то число ребер должно быть больше или равно . Противоречие.
Примеры графов в реальной действительности
Схемы транспортных путей
Рис. 11
В реальной жизни, графы встречаются на каждом шагу, а мы ведь об этом даже не задумываемся. Например, люди, живущие в больших городах, пользуются метро для следования до места работы или учебы и каждый день они смотрят на схему метро, а ведь она является тем же самым графом. Станции на схеме - это вершины графа, линии между станциями - это ребра графа – обозначают пути (рис. 11).
Р одственные отношения
Рис. 12
Генеалогическое древо – это список людей, связанных родственными отношениями, соответствующий порядку родственных связей. Генеалогическое древо – это тот же самый граф, только здесь вершинами графа, являются люди, а ребрами графа – линии, соединяющие родственников в определенном порядке. Применяется в решении судебных процессов – пример распределение имущественных прав (рис.12).
Графы и химия
Рис. 13
Теория графов широко используется в анализе структуры химических веществ. Существуют вещества с одинаковым атомным составом, и в то же время с разными химическими свойствами, что обусловлено их химическим строением. В качестве примера рассмотрим бутан и изобутан, имеющие одну химическую формулу С4H10 (рис.13), но отличающиеся строением и соответственно химическими свойствами (температура кипения бутан 0,50С, изобутна - 11,70С). Химические графы дают возможность прогнозировать химические превращения.
Графы и схемотехника
Рис. 14
Создание схем для электрических приборов до сих пор является одной из наиболее сложных и утомительных задач. Печатная схема - пластина из какого-либо диэлектрика (изолирующего материала), на которой в виде металлических полосок вытравлены дорожки (рис.14). Пересекаться дорожки (ребра) могут только в определенных точках (вершины), куда устанавливаются необходимые элементы (резисторы, конденсаторы, диоды и т.д.), их пересечение в других местах вызовет замыкание электрической цепи. В ходе решения этой задачи необходимо вычертить плоский граф, с вершинами в указанных точках.
Заключение
По итогам работы можно сделать следующие выводы:
Графы – это замечательные математические объекты, с помощью которых можно решать математические, экономические и логические задачи.
Главным преимуществом применения графов в решении различных задач является наглядность.
Метод решения задач с помощью теории графов более рациональный, не содержащий громоздкого математического аппарата.
Спектр применения теории графов имеет выраженный прикладной характер.
Теория графов- один из инструментов математического моделирования жизненных ситуаций.
Полученные нами знания имеют практическую значимость:
Сформировалось целостное представление о теории графов.
Приобретён успешный опыт применения знаний, полученных при выполнении работы для решения математических задач.
Модели графов, изготовленные в результате работы, можно использовать, как наглядное пособие на уроках наглядной геометрии или факультативах по математике.
Приобретён опыт представления повседневных ситуаций в виде математической модели-графа.
Таким образом, поставленные задачи выполнены. Гипотеза подтвердилась.
Источники информации
Математика: Наглядная геометрия. 5— 6 кл.: учебник / И. Ф. Шарыгин, Л. Н. Ерганжиева. — М.: Дрофа, 2015.
Математическая составляющая / Редакторы-составители Н. Н. Андреев, С. П. Коновалов, Н. М. Панюнин. — М.: Фонд «Математические этюды».
Теория графов/ А. В. Омельченко. — М.: МЦНМО.
Школьные математические кружки. Графы / В. М. Гуровиц., В. В Ховрина. — М.: МЦНЦО, 2008.
Дети и графы / Папи Ф., Папи Ж. – М.: Педагогика, 1974.
Графы и их применение / Березина Л.Ю. – М.: Просвещение, 1979.
Графы и их применение / Оре О. – М.: Мир, 1965.
https://ru.wikipedia.org/wiki/Граф_(математика)
https://foxford.ru/wiki/matematika/eylerovy-grafy
https://www.sites.google.com/a/labore.ru/teoria-grafov/vvedenie-v-teoriu/1