Применение теории графов в школьном курсе математики
Обновлено: 02.07.2024
В соответствии с вышесказанным, в данном параграфе будут рассмотрены задачи, которые используются в школе на уроках математики.
Условно их можно классифицировать, подразделив на несколько групп:
2. Логические задачи
3. Задачи о "правильном" раскрашивании карт
4. Задачи на построение уникурсальных графов
Рассмотрим несколько типичных примеров решения задач каждого вида.
Одной из наиболее известных задач о мостах является эйлерова задача; все остальные сформулированы похожим образом и решаются по тому же принципу. Поэтому в данном параграфе мы не будем подробно останавливаться разборе этого типа задач.
Основой применения графов для решения логических задач служит выявление и последовательное исключение возможностей, заданных в условии. Это выявление логических возможностей часто может быть истолковано с помощью построения и рассмотрения соответствующих графов.
Задача 5.1. Из трех человек, стоящих рядом, один всегда говорит правду (правдолюб), другой всегда лжет (лжец), а третий, смотря по обстоятельствам, говорит либо правду, либо ложь (дипломат). У стоящего слева спросили: "Кто стоит рядом с тобой?". Он ответил: "Правдолюб". Стоящему в центре задали вопрос: "Кто ты?", и он ответил: "Я дипломат". Когда у стоящего справа спросили: "Кто стоит рядом с тобой?", он сказал: "Лжец". Кто где стоял?
Решение: Если в данной задаче ребро графа будет соответствовать месту, занимаемому тем или иным человеком, то нам могут представиться следующие возможности (рис 5.1).
Рассмотрим первую возможность. Если "правдолюб" стоит слева, то рядом с ним, судя по его ответу, также стоит "правдолюб". У нас же стоит "лжец". Следовательно, эта расстановка не удовлетворяет условию задачи. Рассмотрев таким образом все остальные возможности, мы придем к выводу, что позиция "дипломат", "лжец", "правдолюб" удовлетворяет задаче.
Действительно, если "правдолюб" стоит справа, то, по его ответу, рядом с ним стоит "лжец", что выполняется. Стоящий в центре заявляет, что он "дипломат", и, следовательно, лжет (что возможно из условия), а стоящий справа также лжет. Таким образом, все условия задачи выполнены.
Задача 5.2. В обеденный перерыв члены строительной бригады разговорились о том, кто сколько газет читает. Выяснилось, что каждый выписывает и читает две и только две газеты, каждую газету читает пять человек, и любая комбинация читается одним человеком. Сколько различных газет выписывают члены бригады? Сколько человек в бригаде?
Решение: Решение этой задачи достигается построением следующего графа (рис 5.2), где каждая вершина обозначает соответствующую газету и соответственно 5 подписчиков, а каждое ребро будет соответствовать одному подписчику.
Иными словами, суть метода решения этой и подобных ей задач состоит в установлении связей между множеством вершин и множеством ребер графа.
Любая географическая карта является многоугольным графом, в котором страны будут гранями, границы – ребрами, а окружающий страны Мировой океан – бесконечной гранью.
Для лучшего зрительного восприятия необходимо, чтобы страны с общей границей были раскрашены в разные цвета. Такую карту называют "правильно" раскрашенной.
Широко известное предположение состоит в том, что каждая карта может быть раскрашена с соблюдением требуемых условий при помощи четырех красок. Этому вопросу уделяется большое внимание в популярной литературе, и здесь мы не будем останавливаться на его рассмотрении.
Задачи на проведение эйлеровых линий без повторений и без отрыва карандаша от бумаги являются одним из математических развлечений. При решении подобных задач необходимо помнить следующее положение. Для того, чтобы на графе имелась цепь, соединяющая АА и ВВ, содержащая все его ребра в точности по одному разу, необходимо и достаточно, чтобы АА и ВВ были единственными нечетными вершинами, т. е. вершинами с нечетной степенью.
В работе рассматривается проблема использования элементов теории графов в школьном курсе математики, а также описаны интеграционные связи математики с другими науками.
Ключевые слова: теория графов, интеграция в образовании, интеграционные связи.
Одной из актуальных проблем последнего времени является проблема введения в школьный курс математики теории графов. Эта теория находит свое применение практически во всех областях знания, являясь одним из средств реализации интеграционных связей математики, поэтому методически целесообразно не только познакомить школьников с понятиями данной теории на уроках математики, но и рассмотреть примеры ее использования в других науках: информатике, химии, биологии, экономике. Часто ли учителя математики и информатики используют элементы теории графов на своих уроках? Знают ли учащиеся о теории графов? Понимают ли они, что графы — мощное средство моделирования? Для исследования отношения к теории графов у всех участников учебного процесса нами был проведен опрос среди учителей и учащихся г. Москвы. Было опрошено 90 учителей математики и информатики и 120 учащихся 5–6 классов.
Опрос учителей математики показал, что основной причиной редкого использования теории графов на уроках математики в основной школе является отсутствие эффективной методики обучения данной теме(45 %), отсутствие мотивации к обучению(25 %) и отсутствие времени на изучение (30 %).
У большинства опрошенных нами учителей теория графов вызывает интерес (73 %), и они хотели бы углубить свои знания в этой области. Они понимают всю необходимость изучения теории графов. Действительно, школьникам среднего звена весьма полезно будет изучить основы теории графов, поскольку они помогут им в освоении базового курса математики, и особенно — в решении олимпиадных задач по комбинаторике и теории вероятностей.
Вопросы, предлагавшиеся учащимся, были связаны с отношением обучающихся к использованию интеграционных связей в процессе обучения. Количество респондентов составило 120 человек.
Наибольшее количество респондентов указали, что многие школьные предметы изучаются в тесном единстве. В частности, опрос показал, что основной составляющей интеграции является математика. Действительно, именно математика является аппаратом естественнонаучных дисциплин, математические методы используются во многих гуманитарных областях (социология, психология и пр.), поэтому сюжеты учебных математических задач связаны с самыми разнообразными аспектами реальной жизни и учебной деятельности школьника основной школы.
Но при этом большинство учащихся не знакомы с элементами теории графов и не представляют, зачем необходимо их изучать, учащиеся не знают, что графы применяются не только в математике, но и окружают нас в повседневной жизни.
Теория графов нашла свое применение во многих областях науки, техники и повседневной жизни. Однако, несмотря на ее широкое применение в разных областях, в школьном курсе математики ей уделяется лишь поверхностное внимание. В то же время различные эксперименты в сфере образования показывают, что элементы теории графов имеют высокую образовательную ценность, поэтому могут быть включены в школьную программу.
Использование элементов теории графов может познакомить учащихся с важнейшими разделами математики и ее применением в различных областях человеческой деятельности, что может способствовать культурной, профессиональной и гражданской самоидентификации личности.
Тем не менее, на уроках математики графы практически не используются. Это связано как с нехваткой учебного времени, так и с тем, что в учебниках математики графы не рассматриваются. Планомерная работа по изучению элементов теории графов позволит учащимся научиться находить и решать проблемы, используя для этого знания из разных областей, а учителю — эффективнее организовать учебный процесс, реализуя одну из прогрессивных методических концепций — осуществление интеграционных связей между различными учебными предметами.
В последнее время интеграция занимает особое место в развитии образования и науки. Она позволяет создать единую систему знаний об окружающем мире, обеспечивая понимание жизненных явлений, места и роли человека в познании и преобразовании мира. Интеграция является одним из направлений реализации личностно-ориентированного, деятельностного образования.
Интеграционные связи способствуют реализации всех функций обучения: образовательной, развивающей и воспитывающей, которые осуществляются во взаимосвязи и взаимозависимости.
Использование интеграционных связей ― одна из наиболее сложных методических задач учителя математики. Она требует знаний содержания программ и учебников по другим предметам, постановки проблем, решение которых можно найти только во взаимосвязи различных областей научных знаний. Реализация интеграционные связей предполагает сотрудничество учителя математики с учителями информатики, физики, экономики, посещение открытых уроков, совместное планирование уроков, проведение бинарных уроков и т. д.
Поскольку теория графов, использующаяся во многих областях науки, является одним из ярких примеров интеграции, было проведено исследование отношения к интеграционным связям математики учителей. Опросный лист для учителей математики содержал вопросы, позволяющие решить следующие задачи:
1) выявление мнения учителей о том, ориентируют ли Федеральные государственные Образовательные стандарты (ФГОСы), используемый учителями учебник, наконец, сам учитель, на использование интеграционных связей;
2) определение уровня самооценки эффективности работы учителей по использованию интеграционных связей на уроках математики;
3) выявление причин, по которым интеграционные связи на уроках математики присутствуют не всегда.
Большинство опрошенных нами учителей (56 %) уделяют внимание использованию интеграционных связей на уроках математики, но лишь 10 % опрошенных делают это систематически. Всех опрошенных учителей попросили указать причины, по которым им не удается уделять постоянное внимание использованию интеграционных связей при проведении уроков математики. По мнению учителей, основные причины — это нехватка времени (45 %) и отсутствие эффективной методики обучения учащихся на основе интеграционных связей (30 %).
По мнению учителей, стандарты и программы в достаточной мере направлены на использование в обучении математике интеграционных связей, тогда как действующие учебники математики слабо ориентированы на реализацию интеграционных связей. Особенное внимание учителя обращали на отсутствие в учебной и методической литературе интеграционных задач и методов. С этой точки зрения, использование элементов теории графов в обучении позволяет реализовать интеграционную функцию математики с наибольшей полнотой, что делает проблему введения элементов теории графов в школьное образование особенно актуальной.
- Бреус И.А, Жмурова И. Ю., Князева Л. Е., Полякова Т. С. Диагностика состояния актуальных проблем математического образования: коллективная монография / Ростов н/Д: издательство Южного федерального университета, 2014.
- Далингер В. А. Методика реализации внутрипредметных связей при обучении математике. — М.: Просвещение, 1991
- Мельников О. И. Современные аспекты обучения дискретной математике.- Минск БГУ, 2002
Основные термины (генерируются автоматически): теория графов, связь, урок математики, учитель математики, элемент теории графов, интеграционная связь математики, основная школа, повседневная жизнь, последнее время, учебный процесс.
Автор: Волобуева Кира Сергеевна
Должность: учитель математики
Учебное заведение: МБОУ СОШ № 92
Населённый пункт: город Новокузнецк, Кемеровская область
Наименование материала: статья
Тема: "Графы в школьном курсе математики"
Раздел: среднее образование
Графы в школьном курсе математики.
Тема графов очень интересна при изучении, что позволяет привлечь школьников к
активной познавательной деятельности. Графы, как никакая другая модель, позволяет
логических задач делает этот процесс более наглядным. С помощью графов решать задачи
очень удобно, интересно, увлекательно, можно рассмотреть несколько вариантов решения
одной и той же задачи и выбрать наиболее легкое, удобное, красивое, интересное решение.
Начальные сведения о графах как геометрических схемах, состоящих из точек
(вершин) и соединяющих их линий (ребер), достаточно просты, а работа с ними вызывает
у детей большой интерес.
В школьном курсе математики теория графов не рассматривается, но в учебниках
начальных классов и основной школы, можно встретить задачи, которые намного проще
решить с помощью графов, нежели другими способами. Олимпиадные задачи и некоторые
задачи ЕГЭ тоже наполнены заданиями, которые легче решить, применяя графический
способ. Но что мешает учителю включить в факультативный курс теорию графов и
некоторый теоретический материал доступен для понимания детей уже даже начальной
Задачи по теории графов можно предлагать не только детям, посещающим
факультативы, но и на некоторых уроках математики для развития логического мышления.
Но вводить такие задачи нужно постепенно, начиная с элементарных заданий, даже почти
с устных, и постепенно повышать уровень их сложности. Конечно, для неподготовленных
детей, такие задачи сначала вызовут затруднения в решении, и поиск решения может
занимать достаточно долгое время. Поэтому на первых этапах задачи по графам лучше
всего задавать, как дополнительное домашнее задание, но не обязательное для всех
учащихся. При первом знакомстве с такими упражнениями учителю не обязательно
сообщать детям, что при их решении применяется теория графов. Новый неизвестный
термин может психологически оттолкнуть детей от поиска решения: «я не решу, ведь мы
только когда дети почувствуют силу при решении задач, можно сказать детям, что эти
задания выделяют в особый раздел математики – топологию, теорию графов. Особенно
важно, на этом этапе, похвалить тех детей, которые решали или пытались решать задачи, и
сказать всему классу, что в их силах решать даже некоторые задачи по неизвестной теме. В
дальнейшем можно раз в неделю уделять по 5 минут в конце уроке для дальнейшего
изучения теории графов. Но более детальное рассмотрение темы, всё же, надо вынести на
Для школьника не обязательно давать строгое определение графа, как
математического объекта. Им вполне достаточно будет сформулировать несколько
определений и теорем и показать, как они работают при решении задач.
Итак, сформулируем основные определения и теоремы на которых можно
построить факультативный курс по графам.
Граф – это набор точек, некоторые из которых соединены линиями.
Особо важно обратить внимание детей в определении на том, что могут
соединяться не все точки друг с другом и соединяются не обязательно отрезками, а
произвольными линиями-дугами. Далее целесообразно подкрепить новое определение
примерами – наглядными рисунками.
рис.1 рис.2 рис.3 рис.4 рис.5
На вышеприведенных примерах очень удобно ввести следующие понятия:
вершины (точки) и ребра (линии, соединяющие вершины) графа и закрепить эти понятия
на примерах. Четкого, строгого обозначения вершин не существует, обозначают из
контекста задачи: или буквами (русскими, латинскими) или цифрами. Причем нужно
особо подчеркнуть, что бывают графы, состоящие только из одних вершин (рис.5), что две
вершины могут быть соединены несколькими ребрами одновременно (рис.4) и что ребро
Можно рассказать детям, что графы используются не только в математике и
графами, не догадываясь об этом, когда изображают различные объекты: населенные
пункты, карты городов, схемы электроприборов, атомы. Схема метро это тоже граф:
вершины конечные станции и станции пересадок, ребра – пути, соединяющие эти
станции. Дворянство тоже применяло графы для создания генеалогического дерева. В них
вершины – это члены рода, а связывающие их линии - отношения родственности,
ведущие от родителей к детям. Ниже приведен фрагмент родословной А.С. Пушкина.
Графы бывают конечные (число его ребер конечно) и бесконечные (число его ребер
бесконечно). В начальной школе и 5-6 классах задачи на бесконечные графы не
предлагают, но для детей постарше можно привести пример такого графа. Например, когда
каждой вершине графа соответствует натуральное число, т.е. вершины графа нумеруются
числами 1, 2, 3… Но так как ряд натуральных чисел бесконечен, то и граф тоже
бесконечный. Конечно, полностью изобразить бесконечный граф нельзя, но можно
изобразить его частично.
Степень вершины – число ребер выходящих из вершины графа. Если ребро
является петлей, то его считают дважды. Закрепляем определение примерами (см. рис.1-
Иногда степень вершины записывают в виде таблицы, а иногда пишут рядом с
самой вершиной. Важно подчеркнуть, что одно и тоже ребро считается дважды (один раз –
для одной вершины, второй – для другой), так как оно соединяет две вершины.
Вершины бывают четные (степень вершины четна) и нечетные (степень вершины
Первые задания, которые можно предлагать по теме графы, связаны как раз с этими
понятиями: построить граф, определить по рисунку, сколько вершин, ребер у граф, какова
степень вершины графа, посчитать сколько четных и нечетных вершин и тому подобные
задания. Такие задания можно предлагать и в начальной школе, так как они вполне
доступны детям 3-4 классов.
Задание: По рисунку определить: сколько вершин, ребер у графа и какова степень
каждой вершины графа?
Решение: Сначала посчитаем количество вершин. Для наглядности на первых порах
их можно выделить другим цветом – 8 вершин (рис.8). Для подсчета ребер удобно
посчитанное ребро выделять черточкой, чтобы не посчитать его дважды – 9 ребер (рис.9)
Для определения степени вершины графа лучше все вершины обозначить буквами
(рис.10), а потом результаты записать в таблицу.
Первое свойство, которое вводим детям без доказательства: «Число нечетных
доказательства. Закрепление данного свойства происходит так же на решении задач.
Задание: Построить граф, у которого вершины имеют следующие степени:
а) А – 7, Б – 3, С – 1; б) А – 5, Б – 1, С – 4.
Решение: При решении задач на построение графов, надо объяснить детям, что
сначала необходимо проверить, возможно ли вообще построение заданного графа. Для
этого учащиеся должны применить первое свойство. Сколько бы дети не пытались
построить граф а), у них ничего не получится. Построение графа а) невозможно, так как
все его вершины нечетные, и число их нечетно. А вот граф б) построить можно, так как у
него две нечетных вершины. Причем у детей могут получаться различные по
конфигурации графы (рис.11-13). Именно на таких заданиях и закрепляется, что число
нечетных вершин графа – четно.
Поучительная сторона этих задач состоит в исследовании, возможно или нет
решение данной задачи, прежде чем приниматься за само решение.
Обратите внимание детей, что построение графа следует начинать с изображения
всех его вершин, и лишь потом соединять их ребрами. Причем лучше всего начинать
соединять ребрами вершины с наименьшей и наибольшей степенью.
рис.11 рис.12 рис.13
Далее лучше всего дать задания такого плана: «без построения графа, определить
Свойство 2: Для того чтобы найти количество ребер в графе, надо просуммировать
степени вершин и результат разделить пополам.
Задание: Даны степени вершин графа: А – 2, Б – 5, С – 1, Д – 4. Без построения
графа, определить число ребер графа.
Решение: Первое, что должны проверить дети: возможно ли построение такого
графа. Чтобы проверить это, надо сосчитать число нечетных вершин – их должно быть
четно. По условию задачи 2 нечетных вершины Б и С, значит построение возможно.
Теперь можно ответить на вопрос задачи, используя второе свойство: (2+5+1+4):2=6.
После решения задачи можно предложить детям построить этот граф и проверить
решение. Причем рисунки могут получиться совершенно разные, в зависимости от того,
какие вершины будут соединены (рис.14-16). Самое главное, чтобы степени вершин
соответствовали условию задачи. Эти задания не сложные и доступны учащимся 5
рис.14 рис.15 рис.16
Связный граф – граф, у которого любые две его вершины можно соединить
непрерывной последовательностью ребер. Другими словами: из любой вершины можно
пройти в другую вершину по ребрам (рис.17-18).
Несвязный граф – граф, который состоит из нескольких частей, каждая из которых
или связный граф, или отдельные вершины (рис.19).
Предложенный выше теоретический материал по графам вполне доступен детям 5-
6 классов. Рассмотрим ниже основные задачи, опираясь на которые можно построить
факультативный курс по математике. Такие задачи, как правило, встречаются в
математических олимпиадах или в разделе задач со звездочками.
Десять человек приветствовали друг друга рукопожатиями. Пять человек
сделали по семь рукопожатий, трое – по пять, двое – по четыре. Сколько всего было
Решение: Вначале надо разобраться с детьми, правильно ли они понимают понятие
рукопожатие на языке графов. Одно рукопожатие – это две вершины соединены одним
ребром. То есть, два человека и у них одно рукопожатие на двоих. Данную задачу можно
переформулировать на язык графов следующим образом: дано 10 вершин, известны
степени каждой вершины и нужно узнать, сколько ребер в этом графе. Чтобы узнать
количество ребер в графе надо сложить степени каждой вершины и разделить пополам –
применить второе свойство . Так как пять человек сделали по семь рукопожатий, то это
значит, что из пяти вершин выходят по семь ребер, а всего ребер: 5+5+5+5+5+5+5=5
- Для учеников 1-11 классов и дошкольников
- Бесплатные сертификаты учителям и участникам
Муниципальное бюджетное общеобразовательное учреждение
"Средняя школа №4"
муниципального образования "город Десногорск" Смоленской области.
Исследовательская работа на тему:
Сологубов Николай Геннадьевич
Сегодня понятия и утверждения теории графов широко применяется практически во всех научных дисциплинах, экономике, технике. Являясь частью дискретной математики, теория графов используется в программировании для создания эффективных алгоритмов. В целом, анализируя учебные программы университетов, можно с уверенностью говорить, что учащиеся физико-математических, механико-математических и других факультетов связанных с изучением математики, активно изучают теорию графов как отдельный курс. Данные курсы помогают освоить многочисленную теорию, связанную с графами , но самое главное они показывают все разнообразие применения графов при решении конкретных задач из реальной жизни. Не смотря на то, что в школьной программе изучение теории графов явно не предусмотрено, некоторые положения теории графов могут и должны быть отражены при обучении математике и информатике.
Проблема исследования: каким образом можно применить теорию графов при решении конкретных задач школьного курса информатики?
Цель исследования: изучение графов как средства обучения учащихся поиску решения задач.
Объект исследования: процесс обучения в старшем и среднем звене общеобразовательных школ.
Предмет исследования: теория графов как средство при решении конкретных задач.
Гипотеза исследования: использование графов, при решении конкретных задач на уроке способствует:
Формированию математического мировоззрения, расширению и углублению теоретических и практических основ информатики;
Развитию логического мышления учащихся, культуры математической речи;
Побуждению к применению полученных знаний, умений на практике;
Задачи исследования:
Изучить учебную, методическую литературу по данной теме;
Проанализировать образовательные программы 8 —11 классов, задание ОГЭ и ЕГЭ;
Разобрать некоторые практические задачи, сравнить подходы к решению задач без использования и с использованием графов.
Подобрать задачный материал по данной теме.
Методологическую основу данного исследования составляют:
работы российских и зарубежных математиков по теории графов: Эйлера Л. , Березиной Л.Ю. , Носова В. А., Мельникова О.И., Берж К. , Кристофидес Н., Зыкова А.А. , Харари Ф., Татт У..
Методы исследования:
Теоретический анализ учебной, методической литературы по теме исследования;
Эксперимент на уроках информатики;
Изучение и обобщение передового педагогического опыта.
Теоретическая значимость: проанализированы и обобщены некоторые теоретические аспекты теории графов , а также изучены различные приемы поиска решения задач с помощью графов, подобраны задачи для разбора на уроках, подготовлена таблица применения графов в реальной жизни.
Научная новизна и практическая значимость :
Полученные в результате работы данные по использованию графов как средства при поиске решения задач в учебном процессе могут быть использованы в работе учителей 8 —11 классов для повышения эффективности занятий, познавательной активности обучающихся на уроках.
Актуальность:
Задача о трех домах и трех колодцах.
Имеется 3 дома и 3 колодца. Провести от каждого дома к каждому колодцу тропинку так, чтобы тропинки не пересекались.
Именно подобный интерес к практическим задачам и стал основой для дальнейшего продвижения графов на уроках информатики.
Задача о Кенигсбергских мостах . Город Кенигсберг расположен на берегах реки Прегель и двух островах. Различные части города были соединены семью мостами. По воскресеньям горожане совершали прогулки по городу. Вопрос: можно ли совершить прогулку таким образом, чтобы, выйдя из дома, вернуться обратно, пройдя в точности один раз по каждому мосту. Благодаря этой задаче была создана теория графов.
Мосты через реку Прегель расположены как на рисунке. ( рис.1 ).
Проблема семи мостов Кёнигсберга.
Суть: можно ли пройти по 7 мостам города Кёнигсберга, не ступив на каждый более одного раза.
Решение: было найдено русско-немецким математиком Леонардом Эйлером в 1736 году.(ПРИЛОЖЕНИЕ №4).
Его рассуждения заключались в следующем:
1) Число нечётных вершин графа должно быть чётно.
2) Если все вершины графа чётные, то можно, не отрывая карандаша от бумаги, начертить граф, при этом можно начинать с любой вершины графа и завершить его в той же вершине.
3) Граф с более чем двумя нечётными вершинами невозможно начертить одним росчерком.
4) Граф кёнигсбергских мостов имел четыре нечётные вершины, следовательно, невозможно пройти по всем мостам, не проходя ни по одному из них дважды.
Задач, которые можно показать на уроке огромное количество, для поиска решения которых целесообразно рисовать графы или пользоваться некоторыми их свойствами. Самое интересное что ученику для их решения порой достаточно базовых знаний из теорий графов. Список некоторых задач с решениями представлен в ПРИЛОЖЕНИИ №5.
Читайте также: