XXII Международный конкурс научно-исследовательских и творческих работ учащихся
Старт в науке
Графы и их применение к решению задач
Автор работы награжден дипломом победителя II степени
Полная версия работы доступна во вкладке "Файлы работы" в формате PDF
Введение
Всякое логически совершенное знание всегда имеет какую-нибудь возможную пользу, которая нам пока хотя и неизвестна, однако может быть, будет найдена потомками. Если бы при культивировании наук всегда имели в виду лишь материальную выгоду, пользу от них, то мы не имели бы арифметики и геометрии.
И.Кант
Тема графов очень интересна при изучении, что позволяет привлечь школьников к активной познавательной деятельности. Графы, как никакая другая модель, позволяет изучать свойства отношений в «чистом виде», а графическое представление решения логических задач делает этот процесс более наглядным. С помощью графов решать задачи очень удобно, интересно, можно рассмотреть несколько вариантов решения одной и той же задачи и выбрать наиболее легкое, удобное, красивое, интересное решение. Начальные сведения о графах достаточно просты, а работа с ними вызывает у детей большой интерес.
В обновленных ФГОС вводится отдельный предмет «Теория вероятности и статистика», в котором целенаправленно рассматривается решение задач с помощью графов. Олимпиадные задачи и некоторые задачи ЕГЭ тоже наполнены заданиями, которые легче решить, применяя графический способ. При этом легко показать, как с помощью теории графов можно быстро решать «сложные» задачи. Тем более, что некоторый теоретический материал доступен для понимания детей уже даже начальной школы.
Толчок к развитию теория графов получила на рубеже XIX и XX столетий, когда наибольший интерес стали вызывать работы по комбинаторике. Как отдельная математическая дисциплина теория графов была впервые представлена в работе венгерского математика Кёнига в 30-е годы XX столетия.
В настоящее время графы и связанные с ними методы исследований распространены практически на всю современную математику. Графы эффективно используются в теории планирования и управления, социологии, математической лингвистике, экономике, биологии, медицине. Широкое применение находят графы в таких областях прикладной математики, как в программирование, в решение вероятностных и комбинаторныхзадач.
Цель исследовательской работы: овладеть основными понятиями теории графов, новыми методами решения задач.
В этом проекте поставлены следующие задачи:
•изучить теоретические основы теории графов.
• разобрать решения различных видов задач.
• разработать рабочий лист для учащихся 7 класса.
Предмет исследования: раздел математики «Теория графов» (курс 7 класса).
Гипотеза: мы предполагаем, что изучение теории графов с помощью рабочего листа поможет учащимся структурировать материал, научиться решать логические задачи.
Глава 1. Теоретические основы
Многие, играя в позиционные игры, решая головоломки или задачи на смекалку, вместо алгебраических или геометрических преобразований составляли таблицы, изображали объекты точками, соединяли их отрезками или стрелками, то есть строили некую математическую конструкцию, которая помогала решать поставленные задачи и цели.
Конструкцией в данном случае является граф.
История возникновения теории графов.
Разделом дискретной математики, изучающий свойства графов называется теорией графов.
Родоначальником теории графов считается выдающийся математик, член Петербургской академии наук Леонард Эйлер.
В 1736 году в одном из своих писем он формулирует и предлагает решение задачи о семи кёнигсбергских мостах, ставшей впоследствии одной из классических задач теории графов.
Очень давно среди жителей Кёнигсберга была распространена загадка: как пройти по всем мостам (через реку Преголя), не проходя ни по одному из них дважды? Многие кёнигсбержцы пытались решить эту задачу как теоретически, так и практически, во время прогулок. Впрочем, доказать или опровергнуть возможность существования такого маршрута никто не мог.
В 1736 году задача о семи мостах заинтересовала Леонарда Эйлера, об этом он написал в письме итальянскому математику Мариони от 13 марта 1736 года. В том письме Эйлер пишет о том, что он смог найти правило, с помощью которого легко определить, можно ли пройти по всем мостам, не проходя дважды ни по одному из них. Оказывается, нельзя.
Вот так выглядела схема задачи:
На упрощённой схеме части города (графе) мостам соответствуют линии, а частям города — точки соединения линий (вершины графа). В ходе рассуждений Эйлер пришёл к следующим выводам:
Число нечётных вершин (вершин, к которым ведёт нечётное число рёбер) графа должно быть чётно. Не может существовать граф, который имел бы нечётное число нечётных вершин.
Если все вершины графа чётные, то можно, не отрывая карандаша от бумаги, начертить граф, при этом можно начинать с любой вершины графа и завершить его в той же вершине.
Граф с более чем двумя нечётными вершинами невозможно начертить одним росчерком.
Граф кёнигсбергских мостов имел четыре (синим) нечётные вершины (то есть все), следовательно, невозможно пройти по всем мостам, не проходя ни по одному из них дважды.
Вначале теория графов казалась довольно незначительным разделом математики, так как она имела дело в основном с математическими развлечениями и головоломками. Однако дальнейшее развитие математики и особенно её приложений дало сильный толчок развитию теории графов.
В XIX веке возродился интерес к теории графов. Графы начали использовать при построении схем. Широкое развитие теория графов получила с 50-х гг. 20 в. В связи со становлением кибернетики и развитием вычислительной техники.
Граф. Понятие графа.
Граф - геометрическая фигура, состоящая из точек и соединяющих их линий.
Графы можно увидеть не только в задачах или при прохождениях каких-либо игр. Их также можно увидеть и в повседневной жизни. Например, когда нужно добраться из одной точки до другой, а дороги мы не знаем. В этом случае мы посмотрим на карту, которая составит граф (из точки A до точки B с помощью линий). Другой пример, граф мы можем увидеть, когда смотрим маршрут нужного нам транспорта. В этом случае мы тоже сможем разглядеть граф, соединяющий точки прибывания (A, B, C и т.д.) линиями.
Эти самые “точки” и “линии” в графе имеют свое определение.
Точки в графе называют вершинами графа.
Линии в графе называют ребрами графа.
В графе не важно расположение точек, они могут быть расположены, как угодно. В графе важно то, как соединены вершины. Например, графы 1 и 2 одинаковые, потому что все вершины соединены одинаково. А граф 3 уже отличается, потому что вершины соединены по-другому.
Степень вершины графа. Изолированная вершина.
От того, как расположена вершина графа зависит степень вершины графа.
Степень вершины графа - количество рёбер, выходящих из вершины графа.
Например, в данном графе из вершины A выходит два рёбра, значит степень вершины А - 2.У точки В степень - 2, т.к. вершина В имеет два выходящих ребра, соответственно степень вершины D тоже 2, а степень вершины С равна 1. Такая вершина, которая имеет степень 1 называется конечной.
Рассмотрим еще один граф и определим степени его вершин.
В данном графе у вершин А и С степень будет 1, потому что из них выходит одно ребро. А вершина В не имеет таких рёбер. То есть степень этой вершины равна 0.
Такая вершина называется изолированной.
Определив степень вершины, можно понять, какая она. Вершина графа, имеющая нечетную степень, называется нечетной, а четную степень - четной.
Зная степень каждой вершины, можно вычислить сумму степеней.
Приведем пример. В данном графе 2 вершины, степень которых будет равна 1.
Чтобы вычислить сумму степеней можно просто сложить значения степеней. А можно вычислить сумму степеней по теореме: сумма степеней вершин графа равна удвоенному числу рёбер.
Соответственно, решая по теореме: число рёбер умножить на 2 = 1*2= 2. Мы решили и выявили, что сумма степеней вершин данного графа равна 2.
Из этой теоремы можно выявить несколько следствий:
-
Сумма степеней вершин графа - четное число.
Да, это так, потому что сумма степеней равна удвоенному числу рёбер. А как мы знаем, любое число при умножении на 2 даем чётное число.
-
В любом графе число вершин нечетной степени - четно.
Кратные рёбра графа. Петля.
Давайте рассмотрим данный граф:
B
A
Заметим, что два ребра соединяют одни и те же вершины, такие ребра называются кратными.
Кратные рёбра (так называемые параллельными рёбрами или мультирёбрами) — это два и более рёбер, инцидентных одним и тем же двум вершинам.
Но помимо кратных рёбер на данном графе видно ребро, которое выходит из вершины А и входит в неё же. Такое ребро, которое выходит из вершины и входит в неё же называется петлёй.
Граф с такой конструкцией называется псевдографом.
Виды графов.
Ориентированный граф (кратко орграф) — рёбрам которого присвоено направление. Например,
Неориентированный граф - это граф, в котором нет направления линий.
В звешенный граф – дуги или ребра имеют вес. Т. Е обозначены числом.
Связный граф
Две вершины А и В графа называются связными, если в графе существует путь с концами А и В.
Две вершины графа называются несвязными, если в графе не существует ни одного пути, связывающего их.
Про граф, изображенный на рисунке, говорят, что он связный, так как из каждой вершины по ребрам можно попасть в любую другую.
Про граф, изображенный на рисунке, говорят, что он связный, так как из каждой вершины по ребрам можно попасть в любую другую.
Н есвязный граф имеет вид нескольких “кусков”, каждый из которых – либо отдельная вершина без ребер, либо связный граф.
Пустой граф- граф, который не имеет рёбер, но есть вершины.
Полный граф-граф без петель, в котором две любые вершины соединены только одним ребром.
Области практического применения графов
Существует огромное разнообразие вариантов применения графов.
Типичными графами на картах города являются схемы движения городского транспорта, изображения железных дорог, схемы авиалиний, которые часто вывешивается в аэропортах. Графом является и система улиц города. Его вершины – площади и перекрестки, а ребра – улицы. Графы есть и на картах звездного неба. Не менее известным примером графа в гуманитарных науках является родовое дерево.
С помощью графов часто упрощается решение задач, сформулированных в различных областях знаний: в физике, химии, электронике.
Помогают графы в решении огромного количества математических и экономических задач.
Теория графов сегодня одна из наиболее развиваемых частей математики, так как современная жизнь требует максимально простых и доступных вариантов решения возникающих запросов. В связи с этим появляются новые профессии. Одна из них – специалист по логистике. Менеджер по логистике занимается организацией доставки товаров, грузов, планирует транспортные маршруты, и т.д. Одна из главных задач специалиста по логистике – анализ исходных данных, поэтому он должен уметь хорошо считать, владеть теорией графов. Другая профессия, в которой сталкиваются с графами – инженер, который готовит схемы электрических цепей. Современные биохимики, молекулярные химики, биотехнологи рисуют структурные формулы, чтобы показать, как в сложной молекуле с помощью валентных связей соединяются друг с другом атомы. Историки прослеживают родословные связи по генеалогическому дереву. Социологи по сложнейшей диаграмме демонстрируют, как подчиняются друг другу различные отделы одной огромной корпораций.
Таким образом, графы применяются в различных отраслях науки и в огромном множестве профессий. В последние десятилетия теория графов находит все новые области применения (физика, биохимия, генетика, биотехнология, психология, социология, экономика, лингвистика, электроника, теория планирования и управления). Именно запросы практики способствуют интенсивному развитию теории графов.
Глава 2. Применение теории графов при решении задач.
Систематическое овладение основными понятиями теории графов невозможно без практического применения знаний на примере решения задач. Решение задач – практическое искусство, научиться ему можно, только подражая хорошим образцам и постоянно практикуясь.
Графы широко применяются при решении математических логических и олимпиадных задач.
Главное понять, что граф – абстрактный математический объект. Следовательно, интерпретировать его возможно по-разному, в зависимости от конкретной задачи.
Рассмотрим примеры задач, для которых наилучшим из возможных способов решения является граф.
Практические задания:
-
Нарисуйте граф, который содержит 2 изолированные вершины и вершины, у которых степень сравнения равна 3.
-
Нарисуйте граф, у которого 3 вершины имеют степень 3. Напишите сумму степеней этого графа.
Задача 1. В некотором государстве 40 городов и из каждого выходит по 3 дороги. Сколько всего в государстве дорог? (Каждая дорога соединяет какие-то два города.)
Решение: Из каждого города выходит 3 дороги, значит всего выходов на дороги во всех городах 40*3 = 120, но т. к. одна дорога соединяет 2 города, то дорог будет вдвое меньше, чем выходов на дороги, т. е. 120/2 = 60.
Ответ: 60 дорог.
Задача 2. (Поиск степени вершины по известным степеням остальных вершин и количеству рёбер.)
В государстве есть 21 город: 10 малых городов, 10 средних городов и столица. Между городами построено 25 дорог. Известно, что из каждого малого города выходит ровно по одной дороге, а из каждого среднего — ровно по две. Сколько дорог может выходить из столицы?
РЕШЕНИЕ.
Города – это вершины графа, а количество дорог – это степени вершин (количество исходящих из них рёбер).
Тогда у нас имеется:
10 вершин степени 1,
10 вершин степени 2,
1 вершина (столица) степени х.
Всего имеется 25 дорог, т.е. общее количество рёбер Е = 25.
Требуется найти количество дорог, выходящих из столицы, т.е. найти х.
Составим и решим уравнение:
(10 ∙ 1 + 10 ∙ 2 + 1 ∙ х) : 2 = 25.
(10 + 20 + х) : 2 = 25,
30 + х = 50,
х = 20.
ОТВЕТ: 20 дорог.
Задача 3. Архипелаг состоит из 20 островов, между некоторыми из которых построены мосты. Могло ли так оказаться, что из пяти островов выходит по 3 моста, из семи островов — по 4 моста, а из восьми островов — по 5 мостов?
РЕШЕНИЕ.
20 островов – это 20 вершин графа.
У этого графа имеется:
5 вершин – степени 3,
7 вершин – степени 4,
8 вершин – степени 5.
Первый способ.
По лемме о рукопожатиях количество вершин с нечётными степенями должно быть числом чётным.
А у нас таких вершин 5 + 8 = 13 – нечётное число.
Значит, это невозможно.
Второй способ.
Посчитаем количество рёбер этого графа:
Е = (5 ∙ 3 + 7 ∙ 4 + 8 ∙ 5 ) : 2 = 83 : 2 = 41,5 – нецелое количество рёбер в графе.
Но такого быть не может, т.к. число рёбер должно быть целым.
ОТВЕТ: нет.
Задача 4. (Задачи, подобные данной, часто встречаются во всероссийских проверочных работах и в работах по функциональной грамотности)
На пришкольном участке растут 8 деревьев: яблоня, тополь, береза, рябина, дуб, клен, лиственница и сосна. Рябина выше лиственницы, яблоня выше клена, дуб ниже березы, но выше сосны, сосна выше рябины, береза ниже тополя, а лиственница выше яблони. Расположите деревья от самого низкого к самому высокому.
Решение:
Вершины графа – это деревья, обозначены их первой буквой названия дерева. В данной задача два отношения: «быть ниже» и «быть выше». Рассмотрим отношение «быть ниже» и проведем стрелки от более низкого дерева к более высокому. Если в задаче сказано, что рябина выше лиственницы, то стрелку ставим от лиственницы к рябине и т.д. Получаем граф, на котором видно, что самое низкое дерево – клен, затем идут яблоня, лиственница, рябина, сосна, дуб, береза и тополь.
Я Т Б
Р Д К
Л С
Задача 4.
На рисунке представлена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, И, К, Л. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город Л?
Рисунок «Схема дорог» Граф к задаче 4.
Решение: Условие данного задания представим в виде ориентированного графа, вершинами которого являются названия городов, а дороги, соединяющие эти города, являются дугами графа. Для того, чтобы решить данную задачу, построим еще один ориентированный граф, но с учетом того, по каким дорогам можно будет попасть в пункт Л. По графу легко подсчитать количество дорог, ведущих из города А в город Л.
Проанализировав выше предложенный практический материал по решению задач при помощи теории графов, можно составить алгоритм и выделить следующие этапы:
1. Анализ условия задачи и перевод ее на язык графов;
2. Геометрическая интерпретация условия, непосредственно построение графа. Именно на этом этапе очень важно воображение, логика и даже элемент творчества, потому что необходимо найти соответствия между элементами условия и переложить их на соответствующие элементы графа. Точками обозначают объекты задачи, то, о чем или о ко говорится в задаче (вершины графа). Если в задачах дается несколько групп объектов, то их будет целесообразнее изображать в разных плоскостях и различными цветами. Линиями (отрезками, дугами) обозначают те отношения между объектами, о которых говорится в задаче (рёбра графа). Отношения могут быть двух типов: принадлежит и не принадлежит. Если отношение «принадлежит», то линии сплошные, если отношение «не принадлежит» - пунктирные;
3. Внимательно читая условие задачи, выделяем основные, ключевые фразы задач и на основании анализа проводим ребра между вершинами графа;
4. Если ключевых фраз не хватает нам для решения задачи, то необходимо проанализировать граф и провести недостающие ребра-отношения;
5. Выбираем нужные отношения (сплошные линии) и записываем ответ.
Тем самым, использование графов в качестве дополнительного визуального средства позволяет достаточно облегчить понимание задач.
«Графовые» задачи нужно широко использовать на уроках математики, алгебры, геометрии, информатики для повышения качества обучения. Таким образом, применяя теорию графов в школьном курсе математики, решение многих математических задач и доказательств упрощается, придает им наглядность и простоту
Рабочий лист по теме: «Графы. Вершины и ребра. Степень вершины. Виды графов»
РАБОЧИЙ ЛИСТ по теме:
«Графы. Вершины и ребра. Степень вершины. Виды графов»
« Граф» - это изображение объектов и связей между ними с помощью точек и линий. Точки в графе называются вершинами графа. Некоторые (не обязательно все) вершины соединены линиями. Эти линии называются ребрами графа.
Нарисуйте три разных графа, в каждом из которых 3 вершины
Количество рёбер, выходящих из вершины графа, называется степенью вершины. Вершина графа, имеющая нечётную степень, называется нечетной, а чётную степень – чётной.
С тепень вершин:
А – ___; В – ___; С – ___; D – ___; E – ___.
Сумма степеней: _______________________________________________
Теорема: Сумма степеней вершин графа равна удвоенному числу ребер.
Следствие 1: Сумма степеней вершин графа – четное число.
Следствие 2: В любом графе число вершин нечетной степени – четно.
Реши задачу: В некотором государстве 40 городов и из каждого выходит по 3 дороги. Сколько всего в государстве дорог? (Каждая дорога соединяет какие-то два города.)
Реши задачу: В государстве есть 21 город: 10 малых городов, 10 средних городов и столица. Между городами построено 25 дорог. Известно, что из каждого малого города выходит ровно по одной дороге, а из каждого среднего — ровно по две. Сколько дорог может выходить из столицы?
Реши задачу: Архипелаг состоит из 20 островов, между некоторыми из которых построены мосты. Могло ли так оказаться, что из пяти островов выходит по 3 моста, из семи островов — по 4 моста, а из восьми островов — по 5 мостов?
В иды графов:
Ориентированный граф(кратко орграф) — рёбрам которого присвоено направление.
Неориентированный граф- это граф, в котором нет направления линий.
С вязный граф - в графе существует путь с концами А и В.
Несвязный граф - в графе не существует ни одного пути, связывающего их.
Реши задачу: Таблица стоимости перевозок устроена следующим образом: числа, стоящие на пересечениях строк и столбцов таблиц, означают стоимость проезда между соответствующими соседними станциями. Если пересечение строки и столбца пусто, то станции не являются соседними. Укажите таблицу, для которой выполняется условие: “Минимальная стоимость проезда из А в B не больше 6”.
Стоимость проезда по маршруту складывается из стоимостей проезда между соответствующими соседними станциями.
Эйлеров граф - граф, который можно нарисовать, не отрывая карандаша от бумаги.
Решая задачу о кенигсбергских мостах, Эйлер сформулировал свойства графа:
-
Число нечётных вершин (вершин, к которым ведёт нечётное число рёбер) графа должно быть чётно. Не может существовать граф, который имел бы нечётное число нечётных вершин.
-
Если все вершины графа чётные, то можно, не отрывая карандаша от бумаги, начертить граф, при этом можно начинать с любой вершины графа и завершить его в той же вершине.
-
Граф с более чем двумя нечётными вершинами невозможно начертить одним росчерком.
-
Е сли все вершины графа четные, то можно не отрывая карандаш от бумаги («одним росчерком»), проводя по каждому ребру только один раз, начертить этот граф. Движение можно начать с любой вершины и закончить его в той же вершине.
Попробуй построить одним росчерком
Заключение
В данной исследовательской работе была представлена теория графов. В повседневной жизни графы можно применить практически ко всем аспектам жизни. Они выступают инструментом осмысления информации, наглядно показывают взаимосвязь между различными объектами. Метод графов прост и удобен в работе, поэтому так распространен.
В ходе работы были изучены виды графов, продемонстрированы способы решения задач по математике и их представления для лучшего структурирования материала.
Мы показали, как изучение графов может помочь обучающимся в решении задач из школьного курса математики, олимпиадных заданий и заданий итоговой аттестации.
Литература
-
ВикипедиЯ [Электронный ресурс]. Режим доступа: https://ru.wikipedia.org/wiki
-
Высоцкий И.Р. Математика. Универсальный многоуровневый сборник задач. 7-9 классы. Учеб. Пособие для общеобразоват. организаций. В 3 ч. Ч. 3. Статистика. Вероятность. Комбинаторика. Практические задачи / И.Р. Высоцкий, И.В. Ященко. – М.: Просвещение, 2020. – 238 с. : ил. – С. 34-45.
-
Высоцкий И.Р., Ященко И.В. Математика. Вероятность и статистика. 7-9 классы. В 2 ч. Ч.1 / И.Р. Высоцкий, И.В. Ященко. – М.: Просвещение, 2023. – 177 с. : ил. – С. 76-92.
-
Данькова В. «Факультативный курс по математике «Графы» для 5-6 классов,» 2018. [Электронный ресурс]. Режим доступа: https://multiurok.ru/files/fakultativnyi-kurs-po-matematike-grafy-dlia-5-6kl.html
-
Мельников О.И. Теория графов для учителей, для школьников…И не только! Книга, которая научит вас теории графов и поможет обучать ей других / О.И. Мельников. Под ред. Ю.М. Метельского. – М.: Ленанд, 2017. – 240 с.
-
Оре О. Графы и их применение. Перевод с англ. Л.И. Головиной. Под ред. И.М. Яглома / О. Оре. – М.: Мир, 1965. – 176 с.