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

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

ВЫПУСКНАЯ КВАЛИФИКАЦИОННАЯ РАБОТА

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

2010 г.

СОДЕРЖАНИЕ

Введение

Глава I. Основные понятия теории графов

§1. Основные понятия и определения

§2. Маршруты (пути), циклы в графах

§3. Графы деревья. Лес

§4. Двудольные графы

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

§1. Моделирование в обучении математике

§2. Использование графов в формировании понятия функции

§3. Применение графов при построении алгоритмов решения задач

§4. Граф-схемы доказательства теории

§5. Поиск решения геометрических задач с помощью графов

Заключение

Литература

ВВЕДЕНИЕ

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

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

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

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

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

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

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

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

Глава I. ОСНОВНЫЕ ПОНЯТИЯ ТЕОРИИ ГРАФОВ

§1. Основные понятия и определения

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

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

Неориентированный граф (соответственно ориентированный граф, или орграф) 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 до полного графа.

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

§2. Маршруты, циклы в графах

Пусть G - конечный граф. Маршрутом S в G называется последовательность ребер, S = (U1, U2, …Un), * в которой любые соседние два ребра Ui-1, Ui, (i=2, n) имеют общую вершину.

На графах допускаются маршруты, в которых не принимаются во внимание направления ребер. Такие маршруты называются неориентированными.

Пусть на графе определен маршрут (*). Та вершина ребра U1, которая не является общей с вершиной ребра U2, называется начальной вершиной маршрута S.

Аналогично вводится понятие конечной вершины маршрута: та вершина ребра Un, которая не является общей с вершиной Un-1, называется конечной вершиной маршрута S. Остальные вершины маршрута S называются внутренними.

Нуль-маршрутом называется маршрут, не содержащий ребер.

Вершина Ui называется достижимый из вершины Ui, если существует маршрут из Ui в Uj. Для определенности считают, что любая вершина Ui достижима из себя нуль-маршрутом независимо от наличия петель.

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

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

Маршрут называется циклом, если начальная и конечная вершины цепи равны. Другое определение цикла - замкнутая цепь, которое понимается в первоначальном определении. Цикл называется простым, если все его вершины различны.

Цепь называется циклом, если начальная и конечная вершины цепи равны. Другое определение цикла - замкнутая цепь, которое понимается в первоначальном определении. Цикл называется простым, если все его вершины различны.

Началом (концом) цикла можно считать любую из его вершин.

На ориентированном графе аналогично понятию цепи вводится понятие пути, а аналогично понятию цикла - понятие контура.

Путь - это ориентированная цепь. Контур - это замкнутый путь. Рассмотрим примеры различных маршрутов на графе G.

Маршрут (U4, U1, U2) является простой цепью.

Маршрут (U4, U1, U2, U3, U7, U1) цепью не является. поскольку ребро U1 встречается в нем дважды. Маршрут (U4, U3, U2, U1) представляет цепь, но не простую, поскольку вершина V3 встречается на ней дважды: как начало ребра U1 и как конец ребра U3. Такая цепь содержит в себе цикл. В данном случае в цепи (U4, U3, U2, U1) имеем цикл (U3, U2, U1). Этот цикл простой. Примером не простого цикла может служить маршрут (U1, U2. U3, U7, U6, U5).

Решим задачу 1.3. Может ли так случиться, что в одной компании из шести человек каждый знаком с двумя и только с двумя другими.

Решение. Участника этой компании изобразим вершиной графа, а отношение знакомства между двумя участниками ребром. Изобразим графы, которые могут соответствовать такой компании.

Итак, ситуация, рассмотренная в задаче, вполне возможна. Но случай соответствует не одной, а двум компаниям, участники одной из них не знакомы с участниками другой.

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

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

Две вершины А и В графа называются связными, если в графе существует путь с концами А и В.

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

Пример. В графе Г вершины А и В - связные, а вершины А и Н - несвязные.

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

Граф называется несвязным, если хотя бы две вершины его несвязные.

§3. Графы деревья. Лес

Ребро и произвольного графа G называется циклическим, если оно принадлежит хотя бы одному элементарному циклу в графе и ациклическим в противном случае. Примером ациклического ребра является висячее справедливы два простых утверждения:

1) при удалении из связного графа циклического ребра граф остается связным;

2) при удалении ациклического ребра граф становится несвязным.

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

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

Дерево - это граф, все ребра которого ациклические. Имеется несколько эквивалентных определений дерева, устанавливающих ряд его характеристических свойств:

1) связный граф, который становится несвязным при удалении любого ребра;

2) связный граф, у которого число ребер на единицу меньше числа вершин;

3) граф, любые две вершины которого связаны единственной элементарной цепью;

4) граф без циклов, в котором после добавления ребра, связывающего две любые вершины, появляется цикл.

Выберем в дереве произвольную вершину б0 и назовем ее корнем, или вершиной нулевого яруса. Соседние вершины назовем вершинами первого яруса и т.д., вершины, соседние вершинам (i-1)-го яруса не отнесенные еще ни к одному ярусу, назовем вершинами i-го яруса. Каждая вершина дерева принадлежит ровно одному ярусу. Очевидно, что номер яруса совпадает с расстоянием между его вершинами и корнем дерева. В силу свойства (3) каждая вершина i-го яруса связана ребром ровно с одной вершиной (i-1)-го яруса и не связана ребром ни с какой вершиной i-го яруса.

Такое представление дерева часто является удобным. Оно показывает, в частности, что в конечном дереве всегда существуют концевые вершины (например, вершины последнего яруса, но, возможно, и другие).

Выделение корня в дереве Д определяет на множестве его вершин частичный порядок: б < в, если б ? в и элементарная цепь из корня в вершину в содержит б. Корень б0 является частично упорядоченном множестве вершин, а все концевые вершины (исключая корень: он может быть, но может и не быть концевой вершиной) - максимальными. Каждая вершина б однозначно определяет корневое поддерево Дб, натянутое на множество таких вершин в, что б ? в. В каждом таком поддереве Дб (в том числе в Дб0 = Д) можно выделить вершины, непосредственно подчиненные корню поддерева, т.е. такие вершины г1, что б < г, и не существует промежуточных вершин дi, для которых б < дi < гi. Для каждой такой вершины гi определяем ветвь Дб г; дерева Дб как корневое поддерево с корнем б, натянутое на множество вершин {б} u {д : д ? г}. Все поддерево Дб получается из своих ветвей склеиванием в корне б.

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

Пример. Формула (Х V ( ¬ Y + Z)) > (¬ X& (1 ~ Y)) изображаемая деревом.

Теорема. Дерево с n вершинами содержит n-1 ребро.

Доказательство. Проведем индукцией по n. При n=2 утверждение очевидно. Пусть дерево G содержит n вершин. Удалим из него какую-нибудь концевую вершину и инцидентное ей концевое ребро. Получим новое дерево, содержащее n-1 вершину и, по предположению индукции, n-2 ребра. Следовательно, исходное дерево содержит (n+2)-1 = n - 1 ребро.

Турнир по олимпийской системе (с выбыванием проигравшего) изображается корневым дихотомическим деревом: корень соответствует победителю.

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

В связном графе G будем последовательно удалять циклические ребра до тех пор, пока это возможно, т.е. пока не останется ни одного циклического ребра. Мы приведем к связному подграфу графа G с тем же множеством вершин, но без элементарных циклов, т.е. к дереву, называемому остовом графа G. Остов выбирается, вообще говоря, неоднозначно, однако все ациклические ребра обязательно входят в любой остов, относительно остова Д все ребра подграфа G/Д называется хордами. Каждая хорда связывает две вершины остова.

Удобнее строить остов графа следующим образом. Упорядочив произвольно множество ребер графа, будем, начиная с первого из них, последовательно добавлять ребра, не образующие цикла вместе с какими-нибудь из ранее выбранных. Для этого достаточно выбирать очередное ребро еi так, чтобы одна из его вершин была инцидентна какому-либо из ребер е1, …, еi-1, а другая - не индидентна никакому из них. При этом всякий раз мы будем добавлять к строящемуся дереву новое концевое ребро.

Последовательность присоединяемых ребер, составляющих в конечном счете остов, - в первом столбце таблицы 1. Во втором столбце - ребра, не включаемые в остов на данном этапе построения: комментарий - в третьем столбце. Обратив внимание на то, что ребра, первоначально не присоединенные, могут впоследствии войти в остов (таковы ребра 5, 6, 7).

Ребро 8 отвергается дважды по разным причинам. Ребра 4, 8, 10, 11, 12, 13, 14, 18 - хорды.

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

Таблица 1

Ребра остова	Комментарий
1 2 3 9 5 6 7 15 16 17	4 5 6 7 8 8 10 11 12 13 14 18	образует цикл с ребрами 1, 2, 3 не смежно ни одному из ранее выбранных ребер - « - - « - - « - образует цикл с ребрами 5, 6, 7 образует цикл с ребрами 6, 7 образует цикл с ребрами 2, 3, 6, 7, 9 образует цикл с ребрами 2, 3, 5, 9 образует цикл с ребрами 1, 9, 5 образует цикл с ребрами 1, 9 образует цикл с ребрами 16, 17

Обратно, пусть связный граф G c b вершинами содержит (b-1) ребер. Докажем, что G-дерево в соответствии с характеристическим свойством (2). Действительно, в противном случае, удалив некоторое число q циклических ребер, мы получили бы остов с b вершинами и (b-1 - q) ребрами, что невозможно (так как остов дерево).

Если к дереву Д добавить ребро (б, в), где б, в є Д, то в графе появится (единственный!) элементарный цикл, составленный из этого ребра и (единственной) элементарной цепи [б, в] є Д. Если удалить из дерева Д произвольное ребро (г, д), не удаляя вершин, то получится состоящий ровно из двух компонент связности (так как восстановление этого ребра превращает граф в связный). Любой подграф Н дерева не содержит элементарных циклов, поэтому все компоненты связности подграфа Н-деревья.

§4. Двудольные графы

Двудольным графом называется граф, вершины которого разбиты на два непересекающихся класса: V = V1 u V2, а ребра связывают вершины только из разных классов - не обязательно все пары (рис.15). Соответствие Г между непересекающимися множествами М и N можно представлять как двудольный граф с множеством вершин М u N и ребрами, связывающими каждый элемент множества М с его образом при соответствии Г. Так, соответствие между билетами теста и содержащимися в них задачами изображается графом со 150 вершинами в одном классе и 40 вершинами в другом. Каждая из вершин второго класса соединена с 25 различными вершинами первого класса. Если же каждая из вершин класса V1 связана ребром с каждой вершиной класса V2, то граф называется полным двудольным и обозначается Кm, n, где m = |V1|, n = |V2|.

Очевидно, граф Кm, n содержит (m+n) вершин и полный граф Кm, n т.п. ребер.

Задание. Изобразите граф К3,3 с минимально возможным числом пересечений.

Двудольный граф представляет возможные варианты 4 групп крови у ребенка супругов, один из которых имеет кровь II группы (тип АО), а второй произвольного типа Х. Изолированная вершина ВВ означает невозможность появления такого типа крови ни при каком Х.

Таблица 2

		Может отдавать кровь группа	Может принимать кровь группы
ОО - I группа АА и АО - II группа ВВ и ВО - III группа АВ - IV группа	I II III IV	I, II, III, IV II, IV III, IV IV	I I, II I, III I, II, III, IV

Глава II. ГРАФЫ В ОБУЧЕНИИ МАТЕМАТИКЕ

§1. Моделирование в обучении математике

Исследуя проблему наглядности, В.В. Давыдов приходит к следующему весьма важному выводу: «…там, где содержанием обучения выступают внешние свойства вещей, принцип наглядности себя оправдывает. Но там, где содержанием обучения становятся связи и отношения предметов, - там наглядность далеко не достаточна. Здесь… вступает в силу принцип моделирования». Давыдов В.В. Виды обобщения в обучении. М., 1972, с.385.

А так как в курсе математики основным содержанием как раз являются разного рода отношения, то, следовательно, основным для этого курса является не принцип наглядности, а принцип моделирования.

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

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

Как это можно сделать? Простой рассказ об этих весьма абстрактных вещах будет неэффективен, ибо мышлению ребенка в таком случае не на что опираться: у него нет чувственного образа этих методов и способов познания, они для него неотделимы от самого опыта познания. Обычная наглядность также здесь помочь не может, ибо в реальной действительности, в окружающем предметном мире нет этих методов и способов. В то же время без опоры на какой-то чувственный образ овладение этими методами и способами как самостоятельными предметами содержания обучения невозможно. Единственный выход состоит в том, чтобы дать учащимся модели этих методов и способов в виде наглядных и легко обозримых схем, графиков или в каком-то другом виде. Тогда, непосредственным предметом изучения станут эти чувственно-воспринимаемые модели, а через них - опосредственно - и сами методы и способы.

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

П.Я. Гольперин выделил три различных типа ориентировки в процессе учения. Мы коснемся только третьего типа. При этом типе учащимся дается метод анализа объектов для самостоятельного составления полной ориентировочной основы действию.

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

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

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

Кроме того, моделирование в обучении математике необходимо еще и для формирования научно-теоретического стиля мышления.

Моделирование следует использовать в обучении математике и для развития рефлексирующей деятельности учащихся. Ведь очень важно, чтобы учащиеся не только умели произвести те или иные умственные действия, но и могли проанализировать эти действия, а главное - имели потребность в таком анализе, имели привычку к нему. К такому анализу надо постепенно приучать учащихся. Этому будут способствовать задания на составление различных схем-моделей изученного материала, составление схем действий по решению задач определенного вида и пр.

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

Математика и химия - обе науки - считаются точными науками, моделирование химии и математики взаимосвязаны и дополняют друг друга.

Решим одну задачу по химии: «Насыщенным углеводородом называется соединение углевода С, имеющего валентность 4, и водорода Н, имеющего валентность 1, в котором при заданном числе атомов углерода содержится наибольшее число атомов водорода. Найдите формулу насыщенного углеводорода, содержащего n атомов углерода».

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

А) С2Н6 = С2Н2·3 = С2Н2·2+2

Б) С3Н8 = С3Н2·3+2

В) С4Н10 = С4Н4·2+2

Вывод: СnH2n+2

В построенном графе можно перейти по ребрам от любой вершины к любой другой, и в нем нет циклов. Такой граф называется деревом. Пусть молекула содержит n атомов углерода и m атомов водорода, тогда граф будет содержать n + m вершин. Далее, при решении задачи воспользуемся легко доказываемым соотношением: в дереве число ребер на единицу меньше числа вершин. Следовательно, в графе n + m - 1 ребер. Из вершин графа, обозначающих атомы углерода, выходит по 4 ребра, а из вершин, обозначающих атомы водорода, - одно. Используя простой факт, что сумма степеней вершин, т.е. сумма числа ребер, можно написать соотношение: 4n + m = 2 (n + m - 1). Отсюда получаем, что m = 2n + 2. Следовательно, формула насыщенного углеводорода, имеющего n атомов углерода: Сn H2n+n. Эта задача часто вызывает удивление у школьников: оказывается, можно получить формулу вещества с помощью математики, используя только определение и не проводя химических опытов.

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

Во-вторых, точность модели зависит от точности решения задачи. Более подробная модель будет лучше описывать объект, но и будет более сложной для исследования. Можно подчеркнуть, что часто нам нужно решить некоторую задачу, но из-за сложности построенной модели мы не можем этого сделать и вынуждены упрощать модель.

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

§2. Использование графов в формировании понятия функции

Особенно помогают графы при введении понятия функции и при ее изучении. Функция - это некоторое соответствие между заданными множествами. С помощью графов можно объяснить ученику, когда введенное соответствие является функцией, а когда нет, что такое обратная функция и когда она существует, что такое множество определения и множество значений функции. На факультативах графовые рисунки помогут школьнику понять, что такое биективное, сюрьективное и инъективное отображение, суперпозиция (умножение) функций и т.д. Например, соответствие между множествами Х и У, не является функцией.

На одном из уроков алгебры было сделано следующее. Рассматривались 5 соответствий, заданных с помощью ориентированных стрелок, между множествами Х = {a, b, c, d} и У = {1, 2, 3, 4}.

Каждое из соответствий анализировалось в ходе беседы, нужные сведения были записаны в виде таблицы на доске и в тетрадях учеников.

С помощью таблицы было выяснено, что соответствия f и k обладают весьма интересным свойством: каждому элементу множества Х соответствует один и только один элемент множества У. Остальные три соответствия таким свойством не обладают. Затем учитель сообщил, что такие соответствия называются функциями.

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

§3. Применение графов при построении алгоритма решения задач

С помощью графов (блок-схем) естественно задавать алгоритмы решения различных задач. В алгоритмы могут быть встроены как арифметические, так и логические операции. Такое задание имеет большую наглядность и облегчает школьнику понимание работы алгоритма. Ему становится ясно, почему он должен выполнять те или иные действия при различных возникающих ситуациях. Кроме того, такая форма задания дисциплинирует мышление школьника, позволяет описать все возможные случаи, не пропустив ни одного из них и не рассмотреть никакой случай дважды. Результаты выполнения действий будут меняться в зависимости от начальных условий, и школьнику станет ясно, что алгоритм нацелен на решение не конкретной, а массовой задачи, т.е. такой задачи, в которой исходные параметры могут принимать различные значения.

Рассмотрим на примере модель поиска рационального решения задачи.

Задача. Из двух точек, расстояние между которыми 1320 м, выходят навстречу друг другу 2 тела. Одно из них может пройти это расстояние за 12 минут; скорость другого в 2 раза больше скорости первого. Через сколько минут тела встретятся?

Решение.

Покажем модель поиска некоторых уравнений к данной задаче, именно тех, которые расположены в ближайших строках графа, т.е. наиболее рациональных. Вершины 1, 2, 3, 4 расположены в первой строке и моделируют данные искомые задачи.

На рисунке указаны краткие обозначения моделируемых ими объектов. Так, вершина 1 моделирует расстояние АВ (1320 м); вершина 2 - время движения первого тела на пути АВ (12 мин.); вершина 3 - соотношения: «скорость второго тела больше скорости первого в 2 раза» или «время движения первого тела на каком-то пути больше времени движения второго на том же пути в 2 раза»; вершина 4 - искомое время движения первого тела на участке АС или второго на участке ВС.

Во второй строке графа расположены вершины 5 - 9, моделирующие первую группу следствий условия задачи, полученных путем возможных операций между данными и искомыми. Так, вершина 1 соединена единственным ненаправленным ребром с вершиной 2. Это значит, что возможна единственная операция между данными 1 и 2. Операция (1, 2) определяет следствие 5 (скорость первого тела). Из вершины 2 исходят два ненаправленных ребра к вершинам 3 и 4. Операция (2, 3) определяет следствие 6 (возможное время движения первого тела на участке ВС). Между объектами 3 и 4 можно произвести две операции и получить следствие 8 (время движения второго тела на участке АС) и 9 (время движения первого тела на участке ВС). Следствие 10 есть результат операции между объектами 4 и 9 (первой и второй строк графа) и помещено в третью строку.

Ребра «равно» соединяют вершины 7 и 9 второй строки, вершины 2 первой и 10 третьей строк. Значит, можно составить уравнения:

2 х = 12 - х (1)

и

3 х = 12(2)

Уравнение (1) 2 + 2 - 2 = 2-й сложности, уравнение (2) 3 + 1 - 2 = 2-й сложности, т.е. оба пути получения уравнений (1) и (2) одинаковой сложности. Если же продолжить граф поиска решений и дальше, то найдем иные пути решения задачи той же или большей сложности. Так, традиционное арифметическое решение, выраженное числовой формулой

будет решением 1 + 6 - 2 = 5-й сложности.

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

Например, с помощью блок-схемы естественно задать алгоритм решения квадратного уравнения и системы линейных уравнений с двумя переменными (рис.1, 2).



Рис.1

Рис.2

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

Рассмотрим следующую задачу. «Среди 6 монет находится одна фальшивая, но неизвестно, легче она настоящих или тяжелее. Среди этих монет известная также настоящая монета. Необходимо с помощью двух взвешиваний на чашечных весах определить фальшивую монету». Занумеруем монеты, и пусть монета 6 - настоящая. Обозначим через F(А) вес монет, принадлежащих множеству А. Процесс определения фальшивой монеты с помощью двух взвешиваний изображен на рис.3. Из рисунка видно, что в любом случае можно найти фальшивую монету за 2 действия (взвешивания), т.е. сложность алгоритма будет равна двум.

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

Рис.3

§4. Граф-схемы доказательства теорем

Методически ценно то, что понятие «обратная задача» позволяет с некоторой общей позиции подойти к распределению материала по классам.

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

Рассмотрим следующие взаимно обратные теоремы.

ПРЯМАЯ ТЕОРЕМА	ОБРАТНАЯ ТЕОРЕМА
В равнобедренном треугольнике высоты, проведенные к боковым сторонам, конгруэнтны.	Если в треугольнике конгруэнтны три высоты, то этот треугольник равнобедренный.
Рассмотрим внимательно особенности доказательства данных взаимообратных теорем. В этих целях построим цепь силлогизмов, т.е. умозаключений, имеющих следующую структуру: А). Большая посылка: Месть Р М>Р Б). Малая посылка: Ресть К Р>К В). Заключение: значит, Месть К М>К
Доказательство прямой теоремы (читать по схеме сверху вниз по направлению сплошных стрелок на схеме, в последовательности силлогизмов X>Y>Z; римскими цифрами обозначены строки на граф-схеме). А). В треугольнике, против конгруэнтных сторон лежат конгруэнтные углы. Б). В ДАВС против стороны АВ лежит LС; против конгруэнтной ей стороны ВС лежит LА. В). Значит, a). Если гипотенуза и острый угол одного треугольника конгруэнтны гипотенузе и острому углу другого треугольника, то треугольники конгруэнтны. б). В Д АСА1 и Д САС1 отрезок АС - общая гипотенуза; в). Значит, а). В конгруэнтных треугольниках против конгруэнтных углов лежат конгруэнтные стороны. б). Против в Д САС1 лежит сторона СС1 , а против конгруэнтного ему Д АСА1 лежит сторона АА1. в). Значит,	Доказательство обратной теоремы (читать по схеме снизу вверх по направлению заштрихованных стрелок на схеме, в последовательности силлогизмов Z'>Y'>X';) А). В треугольнике против конгруэнтных углов лежат конгруэнтные стороны. Б). В ДАВС против лежит сторона ВС, а против конгруэнтного ему лежит сторона АВ. В). Значит, а). В конгруэнтных треугольниках против конгруэнтных сторон лежат конгруэнтные углы. б). Против стороны АА1 в Д АСА1 лежит, а против конгруэнтной ей стороны СС1 в Д САС1 лежит В). Значит, a). Если гипотенуза и катет одного треугольника конгруэнтны гипотенузе и катету другого, то эти треугольники конгруэнтны. б). В прямоугольных треугольниках АСА1 и САС1, АС - общая гипотенуза; (по условию) в). Значит,

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

Сходство. В обоих используется одна и та же совокупность понятий и высказываний (конгруэнтные треугольники, отрезки и углы).

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

Между тем метод обратных задач в нашем опыте доказал свою приложимость в практике обучения даже высшей алгебре, аналитической геометрии, математическому анализу… Так, например, для начинающих нелегко вывести формулу производной обратной функции. Использование граф-схемы в записи делает вывод зримым, а потому более наглядным и убедительным.(рис 4).

Рис. 4

Построив на доске такую граф-схему вычисления производной функции arcsin x, учитель может поручить студенту вывести по той же схеме кратчайшим способом производную сходной функции arcos x. В этих целях, оставив все записи неизменными, цветным мелом (в тетрадях - цветной пастой) следует подписать под символом sin другой символ cos (и наоборот), изменив в соответствующих местах и знаки перед выражениями.

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

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



Свойство параллелограмма (прямая теорема) (а > в) Если четырехугольник является параллелограммом, то в нем противоположные стороны попарно конгруэнтны.	Признак параллелограмма (обратная теорема) (а < в) Если в четырехугольнике противоположные стороны попарно конгруэнтны, то он является параллелограммом.

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

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

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

Стрелки ведут мысль ученика: научиться «одевать» каждую из них в словесную форму - вот в чем состоит задача для школьника.

Использование граф-схем делает процесс доказательства как бы видимым. Рассмотрим случай, когда по одной граф-схеме истолковываются три процесса: два разных способа доказательства прямой теоремы и одно доказательство обратной теоремы.

Пусть доказывается теорема (прямая) о свойстве биссектрисы внутреннего угла треугольника.

Биссектриса внутреннего угла треугольника делит основание на части, пропорциональные принадлежащим сторонам.



Доказательство (I способ) (читать по граф-схеме снизу вверх по направлению сплошных тонких стрелок) 1) Проведем СС1 || ВВ1 2) , как накрест лежащие при тех же параллельных ВВ1 и СС1. 3) , как соответственные при тех же параллельных. 4). В этих двух соотношениях конгруэнтны левые части ; значит, конгруэнтны и правые части: 5). В Д ВСС1 против конгруэнтных углов лежат конгруэнтные стороны: 6). стороны , пересеченные параллельными прямыми, пропорциональны. 7). Заменив равным ему числом , имеем , что и требовалось доказать.	Доказательство (II способ) (читать по граф-схеме снизу вверх по направлению штриховых стрелок). Рассмотрим теперь другое доказательство, которое сводится в первом своем шаге не к проведению прямой СС1, параллельной ВВ1, а к построению отрезка ВС1, конгруэнтного отрезка ВС. I. Проведем II. Д ВСС1 -равнобедренный III. В Д ВСС1 против конгруэнтных сторон лежат конгруэнтные углы: IV. -смежные, по АВС=2•1(по условию). ПоэтомуСВС1 +2•1=180є V. Сравнивая равенства (IV) и (V), получим: . Значит VI. Из равнобедренного Д СВС1 имеем: СВС1 +2•3=180є. VII. Однако, конгруэнтные углы() суть накрест лежащие при прямых ВВ1 и СС1 по признаку параллельности ВВ1¦¦СС1. VIII. Из последнего следует: , или Что и требовалось доказать.

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

Сплетая два взаимно дополнительных доказательства, мы «приводим в движение» много новых теорем, ходов, мыслей, а главное - оживляем в психике прежние связи между знаниями, которые не проявляются при ограничении одним способом доказательства.

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

Примечательно здесь еще и то, что та же самая схема облегчает нахождение доказательства обратной теоремы (толстыми стрелками):

«Если прямая ВВ1, проведенная из вершины А к основанию ВС, делит его на части, пропорциональные прилежащим сторонам, то она является биссектрисой А”.

Доказательство обратной теоремы начинается с пропорции отрезков и с построения конгруэнтных отрезков: [ВC] = [BC1].

На граф-схеме доказательство обратной теоремы показано толстыми стрелками.

Обратим внимание на чрезвычайно плотную «упаковку» информации в подобной граф-схеме: в самом деле, второй способ доказательства прямой теоремы и доказательство обратной теоремы зафиксированы с помощью лишь нескольких штриховых (соответственно толстых) стрелок.

В методике обучения математике под анализом и синтезом понимают два противоположных по ходу рассуждения, применяемых при решении задач и доказательстве теорем. Под анализом понимают рассуждение, идущее от искомого к тому, что дано. Синтез - это рассуждение, идущее в противоположном направлении. Анализ есть поиск решения задачи, доказательства теоремы.

обучение математика граф

Анализ и синтез неотделимы друг от друга, они сопутствуют друг другу, дополняют друг друга, составляя единый аналитико-синтетический метод.

Рассмотрим пример применения анализа к поиску решения задачи.

Задача. Определить радиус окружности, описанной около равнобедренного треугольника, если основание и боковая сторона треугольника соответственно равны 6 см и 5 см.

Дано: Д АВС, АВ = ВС = 5 см, АС = 6 см,

ОВ - радиус описанной окружности.

Найти: ОВ.

Анализ: Выполненный чертеж по условию и требованию задачи позволяет выдвинуть предположение о том, что радиус ОВ описанной около равнобедренного треугольника окружности целесообразно искать, исходя из подобия прямоугольных треугольников АВД и ОВЕ (ОВЕ общий).

Так как ДОВЕ ~ ДАВД, то откуда:

1) где ВЕ и ВД неизвестны;

2) ВЕ = Ѕ АВ, где АВ известно;

3) где АД неизвестно;

4) АД = Ѕ АС, где АС известно.

Поиск решения данной задачи закончен. Здесь не были выполнены обоснования каждого шага поиска, так как они очевидны. Было обращено внимание на другое, а именно на то, что неизвестно в каждой формуле, что надо искать. Действительно, обнаружив на первом шаге анализа, что величины ВЕ и ВД неизвестны, мы подбираем для их отыскания необходимые формулы. Этот процесс продолжается до тех пор, пока эти неизвестные величины не будут выражены через известные. Для того, чтобы решить задачу, достаточно осуществить обратный (противоположный) переход от четвертого действия к первому. Для облегчения выполнения указанных в поиске решения действий можно последовательно выполнять соответствующие вычисления.

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

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

Схема метода проста. Она сводится к выяснению двух вопросов: что требуется найти, доказать и что для этого достаточно знать?

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

Аналитико-синтетический поиск решения геометрических задач позволяет, как и в случае других типов задач, получить механизм выявления их структуры (внутренней структуры) как сложных объектов.

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

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

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

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

В поиске решения задачи равенство

(1)

является следствием указанного свойства. Величина АВ в задаче имеет фиксированное значение (АВ = 5), поэтому ее можно рассматривать как коэффициент пропорциональности k. Отношение неизвестных величин ВЕ и ВД обозначим через х, т.е. ВЕ / ВД = х, а искомую величину ОВ - через у. Тогда равенство (1) примет вид у = kх. Это и есть основное отношение, реализованное в задаче, которое имеет вид ав = с. В равенствах ВЕ = Ѕ АВ (2) и АД = Ѕ АС (4) коэффициент Ѕ не является константой, так как он выражает лишь одно из значений величин соответственно ВЕ и АД, не зафиксированное в задаче. Поэтому равенства (2) и (4) выражают в частных случаях основное отношение ав = с.

Таким образом, в граф-схеме поиска решения задачи имеются только три вершины, на которых выполняется основное отношение, реализованное в задаче. Этими вершинами являются ОВ, ВЕ и АД (они обведены кружочком). Остальные вершины графа являются либо данными величинами (АВ и АС), либо вспомогательными (число Ѕ), либо такой, которой соответствует другое отношение, не являющееся основным (ВД).

Следовательно, вершины ОВ, ВЕ и АД графа поиска решения как минимальные компоненты задачи, на которых выполняется основное отношение ав = с, реализованное в задаче, являются ее элементами. Элемент (ситуация) задачи есть не что иное, как ее структурная единица.

Теперь необходимо установить связи между выделенными элементами структуры задачи. С этой целью используется граф поиска решения и чертеж к задаче. Из граф-схемы следует, что вершины ОВ и ВЕ взаимосвязаны. Действительно, они являются элементами треугольника ОВЕ и их взаимосвязь учитывалась в процессе поиска решения. Что касается вершины АД, то следует признать, что она не имеет явной связи с вершинами ОВ и ВЕ графа: вершины ОВ и АД разделяет вершина ВД, не являющаяся, как было показано выше, элементом структуры задачи, а вершины ВЕ и АД принадлежат различным ветвям графа. Чертеж к задаче подтверждает сделанный вывод.

§5. Поиск решения геометрических задач с помощью графов

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

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