Графы в обучении математике
Дипломная работа - Педагогика
Другие дипломы по предмету Педагогика
цидентна какому-либо из ребер е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 IVI, II, III, IV II, IV III, IV IVI I, II I, III I, II, III, IV
Глава II. ГРАФЫ В ОБУЧЕНИИ МАТЕМАТИКЕ
1. Моделирование в обучении математике
Исследуя проблему наглядности, В.В. Давыдов приходит к следующему весьма важному выводу: тАжтам, где содержанием обучения выступают внешние свойства вещей, принцип наглядности себя оправдывает. Но там, где содержанием обучения становятся связи и отношения предметов, - там наглядность далеко не достаточна. ЗдесьтАж вступает в силу принцип моделирования.
А так как в курсе математики основным содержанием как раз являются разного рода отношения, то, следовательно, основным для этого курса является не принцип наглядности, а принцип моделирования.
В чем состоит принцип моделирования, Принцип моделирования не противопоставляется принципу наглядности - он лишь является его высшей ступенью, его развитием и обобщением, связанным с принципиальными изменениями в целях обучения и типах учебного процесса.
Необходимо, в частности, чтобы учащиеся в процессе обучения овладели общими методами познания, общими способами учебной познавательной деятельности. А для этого нужно, очевидно, выделить, отделить эти методы и способы от тех понятий и явлений, для изучения которых они используются, и сделать их самостоятельным предметом изучения.
Как это можно сделать? Простой рассказ об этих весьма абстрактных вещах будет неэффективен, ибо мышлению ребенка в таком случае не на что опираться: у него нет чувственного образа этих методов и способов познания, они для него неотделимы от самого опыта познания. Обычная наглядность также здесь помочь не может, ибо в реальной действительности, в окружающем предметном мире нет этих методов и способов. В то же время без опоры на какой-то чувственный образ овладение этими методами и способами как самостоятельными предметами содержа