The building of the educational course «the theory of graphs» for the bachelors of the mathematical department

Full Text

На современном этапе развития общества обучение в российской высшей школе осуществляется в соответствии с Государственным образовательным стандартом высшего образования, который призван обеспечить сохранение единства образовательного пространства на всей территории РФ. Государственный образовательный стандарт по направлению подготовки 02.03.01 Математика и компьютерные науки (уровень бакалавриата), утвер- жденный приказом № 949 от 7 августа 2014 г., определяет следующие требо- вания к подготовке бакалавра (выделим некоторые): умение применять мето- ды математического и алгоритмического моделирования при анализе при- кладных проблем; умение использовать базовые математические методы в научных исследованиях; умение производить контекстную обработку об- щенаучной и научно-технической информации, приводить ее к проблемно- задачной форме, осуществлять анализ и синтез информации. В результате освоения программы бакалавриата у выпускника должны быть сформированы (среди прочих) следующие компетенции: готовность ис- пользовать фундаментальные знания в области дискретной математики и математической логики в будущей профессиональной деятельности; способ- ность к самостоятельной научно-исследовательской работе; способность находить, анализировать, реализовывать программно и использовать на прак- тике математические алгоритмы, в том числе с применением современных вычислительных систем; способность к определению общих форм и законо- мерностей отдельной предметной области; способность математически кор- ректно ставить естественнонаучные задачи; знание постановок классических задач математики; способность строго доказывать утверждение, формулиро- вать результат, видеть следствия полученного результата; способность ис- пользовать методы математического и алгоритмического моделирования при решении теоретических и прикладных задач; способность передавать резуль- тат проведенных физико-математических и прикладных исследований в виде конкретных рекомендаций, выраженных в терминах предметной области изу- чаемого явления; способность использовать методы математического и алго- ритмического моделирования при анализе управленческих задач в научно- технической сфере, экономике, бизнесе и гуманитарных областях. Для решения этих задач в программу обучения на указанном и некоторых других направлениях включаются дисциплины, связанные с построением дискретных моделей. Частично или полностью такие курсы посвящены изу- чению теории графов. При построении рабочих программ таких дисциплин возникает ряд проблем, связанных с отбором элементов содержания. На протяжении всей истории педагогики изучается формирование крите- риев отбора учебного материала на основе методологического анализа состо- яния и перспектив развития предметных научных отраслей. Результаты ис- следований позволяют на каждом историческом этапе оптимизировать «ди- станцию» между достижениями науки и их отражением на уровне общего и профессионального образования. Одним из методологических оснований для решения возникающих при этом теоретических и прикладных задач является утвердившееся в педагоги- ке положение о том, что учебный предмет представляет собой не результат проецирования соответствующей отрасли науки на вузовское обучение, а итог дидактической переработки определенной системы знаний, умений и навыков, необходимых для овладения интеллектуальной, материально- практической, социальной или духовной деятельностью [1]. Учебную дисциплину можно представить как структуру, включающую несколько компонентов: идейно-теоретическое ядро, базисное (основное) со- держание, супплетивно-функциональное (дополнительное) содержание и фа- культативную часть [2]. В.И. Гинецинский [2] приводит следующий вариант процедуры построе- ния программы учебной дисциплины: Определить предметную деятельность проектируемой учебно- познавательной деятельности: очертить круг объектов, вовлекаемых в позна- вательную деятельность, и задать перечень понятий, методов и проблем, с позиций которых выделенный круг объектов будет изучаться. Сформулировать закономерности, которые должны быть усвоены в рамках учебной дисциплины. Оценить соотношение между компонентами системы знаний, связан- ными с описанием, объяснением изучаемых явлений, обоснованием форму- лируемых закономерностей, выполнением познавательных действий, предпи- саний. Сформулировать общие положения, на знание которых будет опирать- ся формируемая учебная дисциплина. Сформировать перечень заданий, выполнение которых будет высту- пать критерием усвоения содержания учебной дисциплины. Сформулировать перечень задач, значимых с точки зрения развития конкретной профессионально-педагогической деятельности. Теория и практика разработки учебных программ предоставляет три способа построения учебных программ: линейный, концентрический и спираль- ный [3]. Сущность линейного способа построения учебных программ состоит в том, что отдельные части учебного материала образуют непрерывную по- следовательность тесно связанных между собой и взаимообусловленных зве- ньев, входящих, как правило, только один раз. Таким образом, при линейном способе построения программы новые знания основываются на уже извест- ном материале. Такое построение учебных программ несет в себе как поло- жительные, так и отрицательные явления в обучении. Достоинство линейного способа расположения содержания учебной программы заключается в его экономичности во времени, поскольку исключается дублирование материала. В то же время линейный способ построения программы несет опасность за- бывания пройденного материала. Концентрический способ построения учебных программ позволяет один и тот же материал (вопрос) излагать несколько раз, но с элементами услож- нения, с расширением, обогащением содержания образования новыми ком- понентами, с углублением рассмотрения имеющихся между ними связей и зависимостей. Концентризм замедляет темп обучения, требует больших за- трат учебного времени на изучение учебного материала, порой порождает у учащихся иллюзию знания тех вопросов, с которыми они повторно сталки- ваются, что, естественно, снижает уровень их активности в обучении. Негативных сторон линейного и концентрического способа построения учебных программ в значительной степени удается избежать при составлении учебных программ со спиралеобразным расположением в них учебного мате- риала, благодаря которому удается сочетать последовательность и циклич- ность его изучения. Характерной особенностью этого способа является то, что ученики, не теряя из поля зрения исходную проблему, постепенно расши- ряют и углубляют круг связанных с ней знаний. В отличие от концентриче- ской структуры, при которой к исходной проблеме возвращаются порой даже спустя большой промежуток времени, в спиральной структуре нет перерывов такого типа. Кроме того, в отличие от линейной структуры обучение, обла- дающее спиральной структурой, не ограничивается одноразовым представле- нием отдельных тем [4]. Опыт преподавания дискретной математики на факультете математики и компьютерных наук Кубанского государственного университета позволил сделать вывод, что для гибкого планирования теорию графов как учебную дис- циплину удобно разбить на три модуля. Первый модуль - это основы теории графов: представление графов и изоморфизм, операции с графами, маршруты, метрические характеристики графов, деревья, связность и планарность графов. Второй модуль - это специальные вопросы теории графов: эйлеровы и гамиль- тоновы графы, раскраски графов, независимость и покрытия, паросочетания. Третий модуль - это вопросы, относящиеся к ориентированным графам. По нашему мнению, в курс дискретной математики достаточно включить материал, относящийся к первому и второму модулям, а материал, относя- щийся к ориентированным графам, лучше оформить в специальный курс [5]. Например, на факультете математики и компьютерных наук КубГУ чита- ется курс «Комбинаторные алгоритмы», который посвящен изучению клас- сических алгоритмов решения задач на графах, построению новых алгорит- мов и модификации и комбинации уже известных схем для решения конкрет- ных задач, оценке эффективности указанных алгоритмов. Алгоритмы на ори- ентированных графах изучаются в рамках специальной дисциплины на от- дельных профилях. Остановимся подробнее на дисциплинах, изучающих неориентированные графы. Цель изучения: формирование у студентов теоретических и методологи- ческих основ теории графов. Задачи изучения: расширение сферы компетенции студентов в теории графов; овладение студентами понятийно-терминологическим аппаратом теории графов; овладение приемами применения теории графов к решению прикладных задач. В результате изучения студент должен: - знать основные понятия теории графов (определение графа, виды гра- фов, способы задания графов, раскраска графов, циклы и пути в графах, алго- ритмы на графах), необходимые для успешного изучения математических и теоретико-информационных дисциплин, решения задач, возникающих в про- фессиональной сфере; уметь формулировать и доказывать теоремы, применять методы теории графов для решения математических задач, построения и анализа моделей экономики, физики и информатики, самостоятельно решать классические за- дачи; осуществлять выбор адекватных алгоритмов для решения вышеуказан- ных задач; владеть навыками практического использования современного математического инструментария для решения и анализа задач, предусматриваю- щими знание адекватных алгоритмов. На этапе создания курса были отобраны следующие элементы содержания: Основные понятия (Лемма о рукопожатиях. Теорема о вершинах с оди- наковой степенью. Теорема о вершинах степени 0 или n - 1. Изоморфизм графов. Матричное представление графов). Операции с графами (Удаление ребер и вершин, добавление ребер и вершин, отождествление вершин, расщепление вершин. Объединение, пе- ресечение, произведение графов. Гомеоморфные графы. n-мерные кубы как особый класс графов. Коды Грея). Маршруты, цепи, циклы (Выявление маршрутов с заданным количеством ребер. Теорема о связи количества ребер, вершин и компонент связности в графе. Теорема о связности дополнения графа. Теорема о простом цикле. При- знаки двудольности графа. Распознавание двудольности поиском в ширину). Деревья (Признаки дерева. Три способа построения остова. Алгоритм построения остова обходом графа в ширину. Три способа построения остова. Алгоритм построения остова обходом графа в глубину. Фундаментальные циклы. Теорема о центре дерева. Теорема Кирхгофа о числе остовов. Теорема Кэли о числе помеченных деревьев. Алгоритм перевода дерева в последова- тельность. Теорема Кэли о числе помеченных деревьев. Алгоритм перевода последовательности в дерево. Поиск остова минимального веса. Алгоритм Краскала. Алгоритм Прима. Матричный алгоритм Прима). Связность (Числа вершинной и реберной связности. Теорема о точках сочленения. Алгоритм поиска точек сочленения. Теорема о связи чисел вер- шинной и реберной связности. Свойства двусвязных графов. Теоремы о бло- ках графа). Планарные графы (Теорема Эйлера о связи чисел вершин, ребер и гра- ней. Непланарность графов К5 и К3,3. Критерии планарности. Триангуляция графа. Теорема Фари. Гамма-алгоритм укладки графа на плоскости). Обходы в графах (Уникурсальные графы. Теорема Эйлера. Алгоритм Флёри построения эйлерова цикла. Эйлеров путь в графе. Лабиринты. При- знаки гамильтонова графа). Раскраски (Оценки хроматического числа. Конструирование хромати- ческого полинома. Теорема Кёнига о бихроматических графах. Алгоритм по- строения правильной раскраски. Теорема Хивуда о раскраске планарных гра- фов. Раскраска карт. Теоремы Шеннона и Визинга о хроматическом классе). Независимость и покрытия (Оценки числа независимости. Построение независимого множества вершин. Оценки числа покрытия. Задача о наименьшем покрытии. Оценки кликового числа. Алгоритм выделения клик в графе. Теорема о наибольшем паросочетании. Алгоритм поиска максималь- ного паросочетания. Матричный алгоритм поиска максимального паросоче- тания. Теорема о связи чисел a0 и b0. Теорема Холла о совершенном паросо- четании). При конструировании содержания курса мы стремились отобрать такие эле- менты, которые позволили бы оценить достоинства применения теории графов к решению практических задач в различных областях знаний, предоставить воз- можность обучающимся ознакомиться с постановками наиболее известных за- дач и основными алгоритмами на графах. К каждому элементу содержания необходимо подобрать корпус заданий и упражнений, решение которых позво- лило бы закрепить изученные свойства графов. При этом нужно разделить зада- ния на обязательные (задания в основном репродуктивного характера, для реше- ния которых достаточно знать определения, теоремы, формулы, алгоритмы), без умения выполнять которые невозможно считать курс усвоенным, и задания по- вышенного уровня сложности, в том числе творческие (решение которых состо- ит из нескольких логических шагов и требует более широкого круга знаний, умений и практических навыков), сама постановка которых стимулирует раз- мышления над проблемами теории графов. Однако при попытке выстроить курс в единую линию мы столкнулись с рядом проблем. На первом этапе был выстроен «скелет» курса, включаю- щий минимум сведений из теории графов и позволяющий получить представление о графах «в первом приближении» [6]. Новые понятия при этом опирались на введенные ранее. Затем, при попытке «нарастить этот скелет мышцами», оказалось, что практически каждому новому понятию, свойству, утверждению непросто найти место в установленной линии. Зачастую оказы- валось, что новое понятие тесно увязано с другими, позже вводимыми поня- тиями, или для него в данном разделе, где оно органично появляется, мало или вовсе нет содержательных задач, так как их решение также требует зна- ния фактов из следующих разделов. Простое перемещение понятия в другую главу делало ее сумбурной, лишенной стройности. Приведем несколько примеров. Первый раздел «Основные понятия» начинается с определения графа и договоренности о его обозначении. Здесь логично будет указать устоявшиеся обозначения для некоторых графов: Pn, Cn, Wn. При этом нужно привести и их названия: цепи, циклы, колеса. Но формальное определение этих классов графов будет дано позже, после введения понятия маршрута в графе. Далее в этом же разделе после разбора понятия полных графов, естественно, вво- дится определение дополнения графа. При этом понятие самодополнительно- го графа ввести невозможно, так как пока еще не изучено отношение изо- морфизма. Рассмотреть способы задания графа (перечислением множеств вершин и ребер, рисунком или матричный) логично в начале изучения темы. Но мат- ричный способ годится для помеченных графов. Помеченный граф можно определить как граф, вершинам (или ребрам) которого приписаны метки. То- гда, говоря об изоморфизме, можно привести теоремы об установлении изо- морфизма графов на основе их матриц смежности и инцидентности. Но толь- ко лишь после введения понятия изоморфизма можно определить непомечен- ные графы как класс изоморфных графов. Далее, говоря об операциях над графами, в частности об операции стяги- вания ребра, приводится утверждение о том, что любой непустой связный граф, отличный от тривиального, стягиваем к К2, не не любой связный граф стягиваем к К3. Здесь мы также сталкиваемся с противоречием. Понятие связного графа еще не определено. Приходится довольствоваться интуитив- ным пониманием этого факта. Также можно упомянуть о естественно возни- кающем в этом случае параметре графа - числе Хадвигера, которое связано с проблемой четырех красок. До этой темы (Раскраска графа) еще далеко, по- этому просто «подержим интригу». Непросто обстоит дело и с распределением задач по разделам. Например, задачи, связанные с вышеупомянутыми самодополнительными графами, нашли свое место после стандартных заданий на установление изоморфизма графов, оторвавшись от группы задач о дополнительных графах. Введя несколько основных операций над графами, можно расширить этот список, определив операции степени, композиции, конъюнкции, соединения, модульного произведения. Содержательных задач здесь немного, но ряд тех- нических заданий можно привести, например на построение результата этих операций для конкретных заданных графов [7]. Однако, например, решение задачи нахождения наименьшего числа k, при котором k-я степень связного графа является полным графом (№ 1.4.9 [7]), опирается на понятие диаметра; по нашей классификации, такое задание должно быть включено в следующий раздел, где оно, однако, смотрится «заблудившимся». В таких случаях можно предложить вводить определение, использующееся в одной или нескольких задачах, непосредственно в тексте задачи. Но это нарушает стройность наше- го небольшого учебного пособия [8]. Список подобных примеров можно бы- ло бы продолжить. Все это привело к следующим выводам. Выстроить курс линейно можно, лишь сократив материал до некоторого минимума. При этом можно только поверхностно познакомить учащихся с теорией графов. В условиях ограниченного учебного времени также не представляется возможным выстроить курс концентрически. Такую возможность имеет смысл рассматривать, если до того обучающиеся прослушали некоторый пропедевтический курс, в рамках которого были введены основные термины и утверждения. Но так как студенты вуза обладают разной подготовкой, этот вариант остается теоретическим. Третий способ, интегрирующий первые два, возможно, станет выходом из сложившейся ситуации. Придерживаясь намеченной линейной структуры курса, можно вводить строгие определения в рамках изучаемой темы, а недо- стающие «анонсировать» на неформальном уровне. Позже, когда до них дой- дет очередь, их восприятие будет более спокойным и естественным, ведь эти понятия и утверждения уже знакомы. Не стоит забывать, что при движении вперед всегда появляются вопросы и задачи, затрагивающие пройденный материал. Известные свойства объек- тов теперь можно применить к новым понятиям. Равномерное распределение задач по курсу способствует удержанию пройденного материала в активном запасе, чего невозможно добиться при линейном прочтении курса. Таким образом, двигаясь вперед и вглубь, мы строим сложносплетенную систему понятий, объектов и отношений, свойств и теорем, составляющих теорию графов.

About the authors

Irina V. Sukhan

Kuban State University

Email: irina-sukhan@yandex.ru
Senior Lecturer of Computational Mathematics and Informatics Department. 149, Stavropolskaya st., Krasnodar, 350000

References

Supplementary files