Графы в обучении математике

В настоящее время обучение математике в школе традиционно опирается на непрерывную математику. Дискретная (от лат. discretus – разделенный, прерывистый) математика – раздел математики, занимающийся изучением свойств объектов конечного характера. К их числу могут быть отнесены, например, конечные группы, конечные графы, некоторые математические модели преобразователей информации. В то же время дискретная математика является весьма интенсивно развивающейся частью математики. Дискретная математика состоит из многих разделов: теория множеств, комбинаторика, теория графов, теория вероятностей.

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

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

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

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

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

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

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

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

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

Неориентированный граф (соответственно ориентированный граф, или орграф) G – система G = (V, E, Г), состоящая из множества элементов V = {V}, называемых ребрами, и отображения Г: Е → V, ставящего в соответствие каждому элементу е є Е неупорядоченную (соответственно упорядочную) пару элементов V1, V2 є V, называемых концами ребра е.

V u Е образует множество элементов графов; при этом предполагается, что Е ∩ V = Ø Отображение Г определяет отношение инцидентности ребра с каждым из своих концов. Для графа G = (V, Е, Г) употребляется также более короткое обозначение G = (V, E) без указания инцидентностей, которые определяются контекстом. По количеству элементов графы делятся на конечные и бесконечные. Здесь мы будем рассматривать, в основном, конечные графы, не оговаривая этого специально.

Если Г (е) = (V1, V2) – упорядоченная пара (т.е. (V1, V2) ≠ (V2, V1) при V1 ≠ V2), то ребро е называется ориентированной дугой, исходящей из вершины V1 и входящей в вершину V2; V1 называется началом, а V2 – концом дуги е. Если Г(е) = (V1, V2) – упорядоченная пара, то ребро е называется неориентированным. Всякому графу G можно поставить в соответствии соотнесенный неориентированный граф G. С теми же множествами V и Е и инцидентностями, но все пары неупорядоченные.

Так, на ребра <V1, V5> и <V2, V6> являются дугами графа G (V, Е) = {{V1, V2…V6}, <V1, V5>, <V2, V6>, {V1, V6}, {V2, V3}, {V6, V6}}}.

Ребра {V1, V6}, {V2, V3} неориентированы. Для любого неориентированного ребра полагают, что {Vi, Vj} = {Vj, Vi} также, как и в случае неупорядоченных множеств. Ребро {Vi, Vi} называется петлей. На рис.1 имеем петлю {V6, V6}. Петли обычно ориентированы. На рис.1 приведен смешанный граф, т.е. содержащий как ориентированные, так и неориентированные ребра и петлю.

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

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

Антиподом нуль-графа является полный граф. Ребрами полного графа являются все возможные пары его вершин.

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

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

Граф Н называется частью графа G или частичным графом Н С G, если множество его вершин V (Н) содержится в множестве вершин V (G) графа G и все ребра Н являются ребрами G. Частным, но важным типом частичных графов являются подграфы.

Пусть А – подмножество множества вершин V графа G. Подграф G (A) графа G есть такая часть графа, множеством вершин которого является А, а ребрами – все ребра из G, оба конца которых лежат в А.

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

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

Дополнением простого графа G называется граф , имеющий те же вершины, а его ребра являются дополнением G до полного графа.

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

• Маршруты, циклы в графах
• Графы деревья. Лес
• Двудольные графы
• Моделирование в обучении математике
• Использование графов в формировании понятия функции
• Применение графов при построении алгоритма решения задач
• Граф-схемы доказательства теорем
• Поиск решения геометрических задач с помощью графов