Методические аспекты обучения доказательству студентов математических направлений в рамках курса «Теория графов»



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

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

Д. Пойа, известный математик и педагог, в своей работе [1] отмечает, что человек, изучающий математику, должен учиться доказательным рассуждениям. «Человек должен овладеть стандартом, с которым он мог бы сравнивать всевозможные, выдвигаемые в качестве доказательств доводы, встречающиеся ему в современной жизни. Этим стандартом являются строгие математические доказательства. А математика предоставляет прекрасную возможность научиться доказательным рассуждениям».

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

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

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

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

Саранцев выделяет следующие уровни обучения доказательству [3]:

− Формирование потребности в логических обоснованиях утверждений.

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

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

− Умение использовать методы научного познания и умение самостоятельно выполнять доказательство.

− Умение опровергать предложенные доказательства.

Процесс изучения теоремы включает следующие этапы [4]:

− Мотивация изучения теоремы.

− Ознакомление с фактом, отраженным в теореме.

− Формулировка теоремы.

− Усвоение содержания теоремы.

− Ознакомление со способом доказательства теоремы.

− Доказательство теоремы.

− Применение теоремы.

− Установление связи теоремы с другими теоремами.

Эффективным средством реализации перечисленных этапов являются специальные упражнения, которые должны [3]:

− Способствовать мотивации введения теоремы.

− Выявлять закономерности, отраженные в теореме.

− Способствовать усвоению содержания теоремы.

− Помогать пониманию значения каждого слова в формулировке теоремы, запоминанию ее формулировки.

− Обеспечивать восприятие идеи доказательства, раскрывать приемы доказательства.

− Обучать применению теоремы.

− Раскрывать взаимосвязь изучаемой теоремы с другими теоремами.

К упражнениям, реализующим эти этапы, относятся [3]:

− Упражнения на оперирование моделями.

− Упражнения с практическим содержанием.

− Упражнения на применение ранее изученных теорем и понятий.

− Упражнения на выделение условия и заключения теоремы.

− Упражнения на распознавание ситуаций, удовлетворяющих теореме.

− Упражнения на ознакомление с методом доказательства.

− Упражнения, моделирующие способ доказательства.

− Упражнения на выделение в доказательствах недостающих утверждений и их обоснований.

− Упражнения на систематизацию теорем.

− Упражнения на составление плана доказательства.

При работе над формулировкой и доказательством теорем можно придерживаться следующего плана [5]:

1. Прочитайте формулировку теоремы. Выделите, что дано и что требуется доказать. Какие понятия использовались в формулировке?
2. Проверьте, если возможно, справедливость теоремы на частных случаях; нарушение заключения, если не выполняется какой-либо пункт условия. Приведите, если возможно, графические иллюстрации.
3. Можно ли сформулировать теорему в форме достаточного, или необходимого, или достаточного и необходимого условия какого-либо факта?
4. Прочитав доказательство, попробуйте сформулировать его основную идею.
5. Составьте план доказательства, постарайтесь оформить его в виде схем, рисунков. Представьте доказательство как цепочку отдельных элементов, следующих друг за другом. Можно ли изменить их порядок?
6. Выясните, какие теоремы и определения использовались при доказательстве; где использовался каждый элемент условия; что главное нужно запомнить, чтобы восстановить доказательство.
7. Изложите доказательство конспективно, заменяя каждое предложение одним подлежащим или сказуемым.
8. Завершите работу по анализу доказательства теоремы полным изложением этого доказательства.

На материале утверждений теории графов можно продемонстрировать различные методы доказательства и формы работы с ними. Рассмотрим несколько примеров.

Теорема. Во всяком графе с n вершинами, где n  2, всегда найдутся по меньшей мере две вершины с одинаковыми степенями.

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

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

Рассмотрим еще ряд теорем.

Теорема. Любой (u, v)- маршрут содержит простую (u, v)-цепь.

Теорема. Всякий цикл содержит простой цикл.

Теорема. Объединение двух несовпадающих простых (u, v)-цепей содержит простой цикл.

Доказательство этих теорем состоит в конструировании алгоритма поиска требуемых объектов.

Иногда удобно в одном утверждении собрать несколько теорем. Это придает компактность формулировке теоремы и позволяет видеть связь между утверждениями.

Теорема. Для (n, m) – графа G следующие утверждения эквивалентны:

1) граф G — дерево;

2) граф G — связный граф и m = n — 1;

3) граф G — ациклический граф и m = n — 1;

4) любые две вершины графа G соединяет единственная простая цепь;

5) граф G — ациклический граф, обладающий тем свойством, что если какую-либо пару его несмежных вершин соединить ребром, то полученный граф будет содержать ровно один цикл.

Можно предложить следующий план доказательства этой теоремы [6]. Доказав истинность импликаций 1)  2), 2)  3), 3)  4), 4)  5), 5)  1), мы подтвердим эквивалентность всех пяти утверждений. Причем первая импликация доказывается методом математической индукции, вторая и пятая — от противного, причем для пятой используется вариант доказательства, когда вместо импликации А  В доказывают теорему – В  – А, а доказательство третьей и четвертой импликаций опирается на ранее введенные в курсе теоремы. В качестве дополнительного упражнения можно предложить доказать эквивалентность любой пары данных высказываний. Полезным для студентов-математиков также представляется приведение нескольких вариантов доказательства утверждения. Например, импликация 1)  2) легко доказывается и без метода индукции.

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

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

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

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

Приведем список некоторых подобных аналогий, задачи взяты из [7]:

Формулировка теоремы	Формулировка задачи
В любом графе всегда найдутся по крайней мере две вершины с одинаковыми степенями.	Доказать, что при проведении спортивного соревнования по круговой системе (каждый играет с каждым) в любой момент времени найдутся хотя бы два игрока, проведшие одинаковое число встреч
Для любого графа справедливо утверждение: либо он, либо его дополнение — связный граф.	В некоторой стране каждая пара городов соединена только одним транспортным маршрутом: или железнодорожным, или автобусным. Доказать, что из любого города страны в любой другой можно доехать (возможно, с пересадками) только поездом или только автобусом
Сумма степеней всех вершин графа есть число четное.	Пятнадцать школьников, уезжая на каникулы, договорились, что каждый пошлет открытки трем из остальных. Может ли оказаться так, что каждый получит открытки именно от тех, кому напишет сам?
Если в графе степень каждой вершины не меньше чем n/2, то этот граф — гамильтонов.	В стране некоторые пары городов соединены авиалиниями, причем каждый город соединен не менее чем с половиной других городов. Доказать, что можно найти такой маршрут облета городов, который начинается и заканчивается в одном и том же городе и каждый город посещается ровно один раз.
Граф К3,3 не планарен.	Имеются три дома и три колодца. Каждый хозяин пользуется всеми тремя колодцами. Однажды хозяева поссорились и решили проложить дорожки от дома к колодцам так, чтобы они не пересекались. Возможно ли это?
В связном плоском графе справедлива формула Эйлера: в — р + г = 2, где в — число вершин, р — число ребер, г — число граней с учетом бесконечной.	В стране 7 озер, соединенных между собой 11 каналами, причем от любого озера можно доплыть до любого другого. Сколько в стране островов, образованных озерами и каналами?
Для связного планарного (n, m)-графа при n  3 выполняется неравенство m  3n — 6.	Конструктор придумал схему печатной платы, которая состоит из 12 приборов и 32 проводников, соединяющих их. Можно ли изготовить такую плату так, что все проводники будут расположены на одной ее стороне?

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

1. Докажите, что сумма степеней всех вершин любого графа есть число четное, равное удвоенному числу ребер.
2. Докажите, что в любом графе число вершин нечетной степени четно.
3. Докажите, что в любом нетривиальном графе всегда найдутся по крайней мере две вершины с одинаковыми степенями.
4. Докажите, что если в нетривиальном графе порядка n имеются в точности две вершины с одинаковыми степенями, то в этом графе всегда найдется либо в точности одна вершина степени 0, либо в точности одна вершина степени n — 1.
5. Для каких n и d существует регулярный граф порядка n и степени d.
6. Докажите, что всякий цикл содержит простой цикл.
7. Докажите, что объединение двух несовпадающих простых (u, v)-цепей содержит простой цикл.
8. Докажите, что если у графа все простые циклы четной длины, то граф не имеет ни одного цикла нечетной длины.
9. Докажите, что для связности графа необходимо и достаточно, чтобы для некоторой фиксированной вершины u и каждой другой вершины v существовал (u, v)-маршрут.
10. Докажите, что либо граф, либо его дополнение является связным.
11. Докажите, что связный граф представляет собой простой цикл тогда и только тогда, когда каждая его вершина имеет степень 2.
12. Докажите, что для двудольности графа необходимо и достаточно, чтобы он не содержал циклов нечетной длины.
13. Докажите, что гиперкуб Q_n является двудольным графом.
14. Докажите эквивалентность следующих утверждений:

1. Граф G — дерево;
2. Граф G — связный и число ребер в нем на 1 меньше числа вершин;
3. Граф G — ациклический и число ребер в нем на 1 меньше числа вершин;
4. Любые две вершины графа G соединяет единственная простая цепь;
5. Граф G — ациклический граф, обладающий тем свойством, что если какую-либо пару его несмежных вершин соединить ребром, то полученный граф будет содержать ровно один цикл.

15. Докажите, что в любом дереве имеется не менее двух концевых вершин.
16. Докажите, что число ребер в любом графе, которые необходимо удалить для получения остова, не зависит от последовательности их удаления. Чему оно равно?
17. Докажите, что центр дерева состоит из одной или двух смежных вершин.
18. Докажите, что вершина а является точкой сочленения тогда и только тогда, когда существуют различные вершины u и v такие, что каждая цепь из u в v проходит через а.
19. Докажите, что ребро (а, b) является мостом тогда и только тогда, когда (а, b) единственная цепь, соединяющая а и b.
20. Докажите, что ребро (а, b) является мостом тогда и только тогда, когда оно не принадлежит ни одному циклу.
21. Докажите, что если вершина инцидентна мосту и не является висячей, то она является точкой сочленения.
22. Докажите формулу Эйлера о числе граней.
23. Докажите обобщение формулы Эйлера для несвязного графа.
24. Докажите, что для связного планарного (n, m)-графа при n ≥ 3 выполняется неравенство m ≤ 3n — 6.
25. Докажите непланарность графа К₅.
26. Докажите, что каждый планарный граф содержит вершину степени 5 или меньше.
27. Определите число ребер и граней в плоской триангуляции с n вершинами.
28. Докажите, что связный граф является эйлеровым тогда и только тогда, когда степени всех его вершин четны.
29. Докажите, что связный граф обладает эйлеровой цепью с концами А и В тогда и только тогда, когда А и В — единственные нечетные вершины.
30. Докажите, что гиперкуб Q_n является гамильтоновым графом.

Литература:

1. Д. Пойа Математика и правдоподобные рассуждения. — М.: Изд-во «Наука», 1975.
2. А. Купиллари Трудности доказательств. Как преодолеть страх перед математикой. — М.: Техносфера, 2002.
3. Саранцев Г. И. Обучение математическим доказательствам и опровержениям в школе. — М.: Владос, 2006.
4. Саранцев Г. И. Упражнения в обучении математике. — М.: Просвещение, 1980.
5. Годунова Е. К. Введение в теорию графов. Индивидуальные задания. — М.: МПГУ, 2012.
6. Емеличев В. А., Мельников О. И., Сарванов В. И., Тышкевич Р. И. Лекции по теории графов: уч. пос. Изд. 4-е. — М.: ЛЕНАНД, 2015.
7. Мельников О. И. Теория графов в занимательных задачах. — М.: Книжный дом «ЛИБРОКОМ», 2009.