science-review.ru
Формирование умения строить математические модели и работать с ними – одна из ведущих целей математического образования в средней и высшей школе. Это актуально как для будущих математиков (удачное построение модели, в том числе и перевод математической задачи на язык другого раздела математики – это часто ключ к её решению), так и для будущих «пользователей математики», которым важно уметь формулировать проблемы «своей» области знаний и/или практики в математических терминах, а также интерпретировать полученные результаты. Моделирование как одно из универсальных учебных и исследовательских действий выходит за рамки математики, однако именно при создании математических моделей его компоненты проявляют себя наиболее чётко [1]. Ясно, что для формирования этого действия, как и любого другого, недостаточно изучения его готовых образцов – необходима также и собственная деятельность по «производству» математических моделей из различных задачных ситуаций, по переводу конструкций реальной жизни на язык математики.
Средства обучения – это объекты, подобранные преподавателем для лучшего понимания и усвоения некой конкретной темы. В зависимости от цели обучения, преподаватель использует различные средства и модели. Как микроскоп является средством обучения в биологии (позволяет разглядеть мельчайшие свойства предметов/объектов), так графы могут являться превосходной (математической) моделью в решении математических (и не только) задач, которые раскрывают данные и условия, невидимые на первый взгляд. Помимо этого, у учащихся развиваются умения анализировать, находить соответствие между объектами, рассуждать и делать выводы, приобретаются навыки планирования.
Понятие «граф» можно вводить еще в начальной школе (см. [2,3]), однако использующий его способ решения математических задач актуален не только для школьников, но и в профессиональном образовании. За счет наглядности и простоты элементов у учащихся легко формируется представление о графах. Граф – это совокупность множества вершин и множества ребер. Под ребром понимается пара вершин, упорядоченная (направленное ребро) или неупорядоченная [4]. Если граф не содержит направленных ребер, то он называется неориентированным (н-граф, или просто граф), иначе – ориентированным (орграф). При построении модели в качестве вершин удобно брать какие-либо объекты (дома, друзья, позиции в игре), а в качестве ребер – отношения между этими объектами (пути, дружба, родство, сыгранные партии, ходы в игре). В зависимости от типа отношения получаем н-графы или орграфы; так, если речь идет о симметричном отношении, естественно использовать н-графы, в случае антисимметричного отношения – орграфы. В некоторых случаях возникают дополнительные структуры на графе, например, при решении задач дискретной оптимизации моделями могут служить так называемые нагруженные графы [5], в которых каждому ребру сопоставлено некоторое число («длина» или вес). При решении логических задач могут использоваться графы с цветными рёбрами или графы с цветными вершинами [6], и т.д. Мы предлагаем начинать обучение использованию графов как моделей с задач следующего типа.
Задача 1. В офисе компании 15 телефонов. Можно ли их соединить проводами так, чтобы каждый телефон был соединен ровно а) с пятью другими? б) с четырьмя другими?
Обсуждение. Переведем задачу на язык графов, то есть сконструируем граф, являющийся моделью данной задачи. Пусть вершины графа соответствуют телефонам, тогда естественно считать, что ребра – это провода, которые и соединяют данные телефоны. Таким образом, у нашего графа 15 вершин. Подсчитаем количество рёбер графа.
а) По условию каждый телефон должен быть соединен с пятью другими, значит, степень каждой вершины (количество ребер графа, инцидентных этой вершине) должна быть равна 5, то есть количество рёбер должно быть равно 
– нецелому числу; это говорит о том, что такого графа не существует.
б) Из условия степень каждой вершины равна 4. Зная степени всех вершин, мы можем вычислить количество ребер. Имеем 
ребер – противоречия не возникает. Необходимо обсудить с учащимися, гарантирует ли это существование такого графа, чётко сформулировать вывод о том, что для доказательства существования графа с заданными свойствами нужно предъявить его конструкцию, предложить нарисовать нужный граф (см., например, рис. 1).
Рис. 1. Граф на 15 вершинах степени 4 каждая
Для решения задачи а) мы по сути пользовались теоремой о степенях вершин: сумма степеней всех вершин любого графа равна удвоенному числу его ребер.
Предполагается, что это правило подсчёта рёбер будет самостоятельно сформулировано учащимися (важно, чтобы был понят основной принцип: при подсчёте числа рёбер графа суммированием степеней вершин каждое ребро считается дважды).
Полезно обсудить, предложили ли разные участники дискуссии один и тот же пример графа или это разные графы, а если разные, то как это можно проверить. Таким образом, будет затронуто важное понятие изоморфизма графов [5], но без использования самого этого термина.
На первых этапах обучения разумно предлагать школьникам такие задачи, где модель возникает наиболее естественным образом, например:
Задача 2. Дворовый хулиган Петя хочет отобрать у пятиклассника Леши МП3–плеер, но согласен и не отбирать, если Леша решит за него задачу. Задача очень трудная – найти, сколько диагоналей в 17-угольнике. Помогите Леше.
Решение. Вершины 17-угольника – вершины графа, диагонали и стороны – ребра графа. Всего 136 ребер. Из них 17 сторон, а остальные – диагонали. Значит, диагоналей 136–17=119.
На этом примере можно ввести понятие полного графа и предложить школьникам самостоятельно найти формулу для числа ребер полного графа на n вершинах.
Следующей может быть задача, где построение модели (как с точки зрения выделения вершин и ребер графа, так и при поиске ответа на вопрос) является менее очевидным.
Задача 3. Ваня и Миша играют в такую игру. Они по очереди связывают 5 столбиков ленточками попарно. Кто свяжет последнюю пару столбиков, тот выиграл. Кто победит – тот, кто завяжет первую ленточку, или его соперник?
Решение. После того, как все ленты будут завязаны, получится полный граф с 5 вершинами – столбиками и ребрами-ленточками. В этом графе 
ребер. Значит, выиграет тот, кто завязывал ленту вторым.
Задача 4. В деревне 23 дома, некоторые из которых соединены дорогами, и любые два дома соединяет ровно один путь. Сколько дорог в деревне?
Обсуждение. Здесь возникает новый класс графов – деревья, т.е. связные (н-)графы без циклов. Важно понять, что это определение эквивалентно (для н-графов) условию отсутствия в графе различных путей с общими началом и концом. На начальном этапе знакомства с деревьями можно предложить решить данную задачу, но для меньшего числа домов (вершин) – каждому учащемуся выбрать свое количество вершин (5, 6, 7), нарисовать соответствующий граф. Далее можно вместе сформировать понятие о дереве как о графе без циклов и предложить вывести формулу числа ребер в дереве, а также получить решение данной задачи: пусть дома будут вершинами графа, а маршруты – ребрами этого графа. В этом графе любые два города соединяет ровно один путь, значит граф является деревом. В дереве вершин на 1 больше, чем ребер, значит дорог на 1 меньше, чем домов, т.е. 22.
Понятие о дереве более сложным образом работает при решении следующих задач.
Задача 5. В государстве Океания 17 островов, между ними проложены маршруты так, что с каждого острова выходит ровно четыре маршрута. Докажите, что в Океании есть такие два острова, что с одного до другого можно добраться двумя разными путями (но может быть с пересадками на других островах).
Решение. Представим себе острова вершинами графа, а маршруты – ребрами этого графа. В этом графе сумма степеней вершин равна 17?4, и, значит, в нем 
ребра. Предположим, что в графе никакие две вершины не связаны двумя различными маршрутами, тогда в графе нет циклов (иначе между любыми вершинами цикла есть два пути – с противоположным направлением обхода). Следовательно, граф является деревом или состоит из нескольких деревьев. В любом дереве число ребер на 1 меньше числа вершин, то есть в нашем графе рёбер должно быть меньше, чем вершин. Полученное противоречие показывает, что предположение неверно.
При обсуждении этой задачи можно привлечь внимание к необходимости уточнения условия: можно ли считать граф неориентированным – то есть означает ли условие, что любой маршрут можно проходить в двух направлениях? Полезно выделить (и постепенно дополнять) общую схему описания модели, возникающей в задаче:
1. что мы принимаем за вершины графа, за ребра графа;
2. является ли граф ориентированным,
3. есть ли в графе петли и/или кратные ребра,
4. относится ли граф к каким-либо специальным изученным классам (полный, двудольный, полный двудольный, связный, дерево и др.)?
Задача 6. Маша и Саша любят играть в такую игру: в рыболовной прямоугольной сетке размером 4×5 ячеек по очереди перерезают по одной веревочке так, чтобы сетка не распалась на куски. Проигрывает тот, кто не может сделать ход (т.е. при любом варианте его хода сетка распадается). Кто выиграет при правильной игре: Маша (она ходит первая) или Саша?
Решение. Представим узлы сетки вершинами, а веревочки – ребрами графа. В начале игры было 
вершин и 
ребер. Можно удалять ребра до тех пор, пока в графе остались циклы. Как только граф станет деревом, при удалении любого ребра он перестанет быть связным, и игрок не сможет сделать ход. Вершин при этом осталось 30, значит ребер стало 30–1=29. За игру будет удалено 49–29=20 ребер, значит последний ход сделает второй игрок и выиграет.
Рис. 2
Задача 7. В сарае 10 корыт с едой и 20 поросят. Время от времени поросята перебегают от одного корыта к другому. Известно, что между каждыми двумя корытами пробегал какой-нибудь поросенок. Докажите, что хоть один поросенок перебегал от одного корыта к другому не менее трех раз.
Обсуждение. Примем корыта за вершины графа. Далее возможны разные подходы к построению модели. Ясно, что если между какими-либо корытами пробегал поросенок, то соответствующие вершины следует соединить. Если исходить из обычного понимания графа, при котором пара вершин может быть либо соединена ребром, либо не соединена (так что элементы матрицы смежности – единицы и нули), то полученный граф не будет содержать информации о том, сколько именно раз между двумя определёнными корытами перебегали поросята. С учётом требования задачи это представляется не слишком удобным. Естественнее соединять пару вершин направленным ребром всякий раз, когда между соответствующими корытами пробегает поросёнок; тогда мы получим более общую структуру, а именно, орграф с кратными рёбрами (его можно задавать матрицей смежности, элементы которой – любые целые неотрицательные числа) Из условия следует, что любые две вершины графа соединены хотя бы одним ребром (хотя бы в одном из двух возможных направлений), так что он содержит хотя бы 
ребер. Если бы каждый поросенок сделал не более двух перебежек, то ребер в графе было бы не более чем 
. Значит, хоть один поросенок перебегал не менее трех раз.
На примере этой задачи целесообразно обсудить различие между доступными в рамках теории графов моделями, в частности, между ориентированными и «обычными» (неориентированными) графами. Так, в орграфе естественно вместо степени рассматривать для каждой вершины «степень входа» и «степень выхода», и утверждение о сумме степеней вершин н-графа в случае орграфа заменяется следующим (желательно, чтобы его сформулировали в ходе дискуссии сами учащиеся): сумма степеней входа всех вершин орграфа равна сумме степеней выхода всех его вершин и равна числу (направленных) рёбер этого графа.
В частности, в полном орграфе на n вершинах число рёбер равно 
. Обратим внимание, что в полном орграфе каждое ребро проходится дважды (в двух направлениях), т.е. обычно изображается одной линией без стрелок. Учитывать ли это ребро в сумме ребер однажды или дважды, зависит от используемой в конкретном рассуждении модели. Так, в задаче 4 «граф перебежек», если рассматривать его как неориентированный, по условию был полным графом на 
вершинах, т.е. число его ребер было равно 
. При рассмотрении орграфа с кратными рёбрами (который не обязательно является полным орграфом!) то же условие дало оценку снизу на число направленных рёбер: не менее 45. Можно попробовать изменять различными способами условие задачи 4, добиваясь полного понимания конструкции. Приведём несколько возможных вопросов: изменится ли решение задачи, если фразу в условии «между каждыми двумя корытами пробегал какой-нибудь поросенок» заменить на фразу «от каждого корыта к каждому пробегал какой-нибудь поросенок»? Если да, то останется ли верным заключение? Можно ли будет его усилить?
Можно ли уменьшить количество корыт в задаче, не изменяя более ничего (и так, чтобы заключение осталось верным)? Можно ли увеличить количество поросят в задаче, не изменяя более ничего (и так, чтобы заключение осталось верным)?
Далее предлагается рассмотреть задачи, в которых естественной моделью является орграф (без кратных рёбер). Простейшие из этих задач используют сформулированное выше утверждение; мы считаем, что не следует предлагать запомнить его, лучше, чтобы при решении нескольких конкретных задач оно каждый раз возникало заново в процессе решения. Сформулируем несколько задач такого рода (в порядке повышения сложности).
Задача 8 ([7], №30819) Дима, приехав из Врунландии, рассказал, что там есть несколько озер, соединённых между собой реками. Из каждого озера вытекают три реки, и в каждое озеро впадают четыре реки. Докажите, что он ошибается.
При обсуждении можно задать вопрос: полностью ли понятно условие задачи, не нужны ли какие-то уточнения. Может возникнуть предложение специально отметить, что система рек и озёр Врунландии – замкнутая, т.е. все реки вытекают только из озёр этой страны и впадают только в озёра этой страны. Если такое уточнение будет сформулировано, то решение задачи становится очевидным: из слов Димы следует, что количество рек во Врунландии должно быть, с одной стороны, втрое больше количества озёр (учитываем степени выхода всех вершин), а с другой стороны, вчетверо больше количества озёр (учитываем степени входа всех вершин). Если во Врунландии есть хотя бы одно озеро (по словам Димы, их несколько, т.е. больше нуля), получаем противоречие.
Задача 9. В некотором государстве каждый город (их больше двух) соединён с каждым из остальных городов дорогой.
а) (ср. [8], №30821). Сумасшедший король хочет ввести на дорогах одностороннее движение так, чтобы, выехав из любого города, в него нельзя было вернуться. Можно ли так сделать?
б) Сумасшедший король хочет ввести на дорогах одностороннее движение так, чтобы из любого города можно было выехать, но, выехав, нельзя было вернуться. Можно ли так сделать?
в) (ср. [8], №30821). Честолюбивый король хочет ввести на всех дорогах одностороннее движение так, чтобы из столицы можно было добраться до любого другого города. Помогите королю осуществить такую реформу. А можно ли добиться этого результата, если до королевских реформ некоторые города не были связаны между собой дорогой, но из любого города всё же можно было добраться в любой другой (возможно, через другие города)?
г) Честолюбивый король хочет ввести на всех дорогах одностороннее движение так, чтобы из столицы можно было добраться до любого другого города (возможно, проехав по нескольким дорогам) и вернуться в столицу. Помогите королю осуществить такую реформу. А можно ли добиться этого результата, если до королевских реформ некоторые города не были напрямую связаны между собой дорогой, но из любого города всё же можно было добраться в любой другой, хотя бы через другие города?
д) (ср. [8], №30825) Легкомысленный король недолго думая ввел на всех дорогах одностороннее движение. Докажите, что найдётся город, из которого можно проехать в любой другой.
е) (ср. [8], №31088) Легкомысленный король недолго думая ввел на всех дорогах одностороннее движение. Докажите, что найдётся город, из которого можно проехать в любой другой, заехав по пути не более чем в один из остальных городов.
В ходе обсуждения задачи предлагается сопоставить формулировки и указать, как различия отразятся в построении модели. Важно также привлечь внимание к тому, что орграф без циклов в задаче а) построен на основе полного н-графа и, следовательно, совсем не похож на дерево. Можно сразу обсудить неравносильность условий (А) и (В) в случае орграфов. В задачах в)-г) возникает понятие связного графа и стимул обсудить, как модифицируется это понятие для орграфов. В пункте е) для доказательства существования вершины, связанной с любой другой вершиной путём длины не более 2, приходится воспользоваться правилом крайнего: искомая вершина – та, для которой степень выхода наибольшая (или любая из них, если таких несколько). Утверждение д), разумеется, следует из е), но может быть доказано и независимо индукцией по числу городов. Решение этих пунктов разумно начать с экспериментальной работы в парах: один из учащихся каким-либо образом расставляет стрелки на рёбрах полного графа, а другой находит в полученном орграфе вершину с требуемым свойством.
Предложенный вариант введения в теорию графов может служить «прологом» к работе над проектами (ср. [4, 6, 7]), в которых с помощью графов будут исследоваться задачи той предметной области, которая соответствует интересам школьника или профилю образовательной программы.