Графы в школьном курсе математики.

Тема графов очень интересна при изучении, что позволяет привлечь школьников к

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

изучать свойства отношений в «чистом виде», а графическое представление решения

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

очень удобно, интересно, увлекательно, можно рассмотреть несколько вариантов решения

одной и той же задачи и выбрать наиболее легкое, удобное, красивое, интересное решение.

Начальные сведения о графах как геометрических схемах, состоящих из точек

(вершин) и соединяющих их линий (ребер), достаточно просты, а работа с ними вызывает

у детей большой интерес.

В школьном курсе математики теория графов не рассматривается, но в учебниках

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

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

задачи ЕГЭ тоже наполнены заданиями, которые легче решить, применяя графический

способ. Но что мешает учителю включить в факультативный курс теорию графов и

показать, как с ее помощью можно быстро решать «сложные» задачи. Тем более, что

некоторый теоретический материал доступен для понимания детей уже даже начальной

школы.

Задачи по теории графов можно предлагать не только детям, посещающим

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

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

с устных, и постепенно повышать уровень их сложности. Конечно, для неподготовленных

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

занимать достаточно долгое время. Поэтому на первых этапах задачи по графам лучше

всего задавать, как дополнительное домашнее задание, но не обязательное для всех

учащихся. При первом знакомстве с такими упражнениями учителю не обязательно

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

термин может психологически оттолкнуть детей от поиска решения: «я не решу, ведь мы

этого не проходили», хотя и решение может быть совсем легким, элементарным. Лишь

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

задания выделяют в особый раздел математики – топологию, теорию графов. Особенно

важно, на этом этапе, похвалить тех детей, которые решали или пытались решать задачи, и

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

дальнейшем можно раз в неделю уделять по 5 минут в конце уроке для дальнейшего

изучения теории графов. Но более детальное рассмотрение темы, всё же, надо вынести на

факультативный курс.

Для школьника не обязательно давать строгое определение графа, как

математического объекта. Им вполне достаточно будет сформулировать несколько

определений и теорем и показать, как они работают при решении задач.

Итак, сформулируем основные определения и теоремы на которых можно

построить факультативный курс по графам.

Граф – это набор точек, некоторые из которых соединены линиями.

Особо важно обратить внимание детей в определении на том, что могут

соединяться не все точки друг с другом и соединяются не обязательно отрезками, а

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

примерами – наглядными рисунками.

рис.1 рис.2 рис.3 рис.4 рис.5

На вышеприведенных примерах очень удобно ввести следующие понятия:

вершины (точки) и ребра (линии, соединяющие вершины) графа и закрепить эти понятия

на примерах. Четкого, строгого обозначения вершин не существует, обозначают из

контекста задачи: или буквами (русскими, латинскими) или цифрами. Причем нужно

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

вершины могут быть соединены несколькими ребрами одновременно (рис.4) и что ребро

может «выходить и заходить» в одну и ту же вершину (рис.3) – такое ребро называют

петлей.

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

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

графами, не догадываясь об этом, когда изображают различные объекты: населенные

пункты, карты городов, схемы электроприборов, атомы. Схема метро это тоже граф:

вершины конечные станции и станции пересадок, ребра – пути, соединяющие эти

станции. Дворянство тоже применяло графы для создания генеалогического дерева. В них

вершины – это члены рода, а связывающие их линии - отношения родственности,

ведущие от родителей к детям. Ниже приведен фрагмент родословной А.С. Пушкина.

Графы бывают конечные (число его ребер конечно) и бесконечные (число его ребер

бесконечно). В начальной школе и 5-6 классах задачи на бесконечные графы не

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

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

числами 1, 2, 3… Но так как ряд натуральных чисел бесконечен, то и граф тоже

бесконечный. Конечно, полностью изобразить бесконечный граф нельзя, но можно

изобразить его частично.

рис.6

Степень вершины – число ребер выходящих из вершины графа. Если ребро

является петлей, то его считают дважды. Закрепляем определение примерами (см. рис.1-

5).

Иногда степень вершины записывают в виде таблицы, а иногда пишут рядом с

самой вершиной. Важно подчеркнуть, что одно и тоже ребро считается дважды (один раз –

для одной вершины, второй – для другой), так как оно соединяет две вершины.

Вершины бывают четные (степень вершины четна) и нечетные (степень вершины

нечетна).

Первые задания, которые можно предлагать по теме графы, связаны как раз с этими

понятиями: построить граф, определить по рисунку, сколько вершин, ребер у граф, какова

степень вершины графа, посчитать сколько четных и нечетных вершин и тому подобные

задания. Такие задания можно предлагать и в начальной школе, так как они вполне

доступны детям 3-4 классов.

Задание: По рисунку определить: сколько вершин, ребер у графа и какова степень

каждой вершины графа?

рис.7

Решение: Сначала посчитаем количество вершин. Для наглядности на первых порах

их можно выделить другим цветом – 8 вершин (рис.8). Для подсчета ребер удобно

посчитанное ребро выделять черточкой, чтобы не посчитать его дважды – 9 ребер (рис.9)

рис.8 рис.9

рис.10

Для определения степени вершины графа лучше все вершины обозначить буквами

(рис.10), а потом результаты записать в таблицу.

Первое свойство, которое вводим детям без доказательства: «Число нечетных

вершин графа – четно». И в дальнейшем, все свойства и теоремы даются без строгого

доказательства. Закрепление данного свойства происходит так же на решении задач.

Задание: Построить граф, у которого вершины имеют следующие степени:

а) А – 7, Б – 3, С – 1; б) А – 5, Б – 1, С – 4.

Решение: При решении задач на построение графов, надо объяснить детям, что

сначала необходимо проверить, возможно ли вообще построение заданного графа. Для

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

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

все его вершины нечетные, и число их нечетно. А вот граф б) построить можно, так как у

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

конфигурации графы (рис.11-13). Именно на таких заданиях и закрепляется, что число

нечетных вершин графа – четно.

Поучительная сторона этих задач состоит в исследовании, возможно или нет

решение данной задачи, прежде чем приниматься за само решение.

Обратите внимание детей, что построение графа следует начинать с изображения

всех его вершин, и лишь потом соединять их ребрами. Причем лучше всего начинать

соединять ребрами вершины с наименьшей и наибольшей степенью.

рис.11 рис.12 рис.13

Далее лучше всего дать задания такого плана: «без построения графа, определить

число ребер графа».

Свойство 2: Для того чтобы найти количество ребер в графе, надо просуммировать

степени вершин и результат разделить пополам.

Задание: Даны степени вершин графа: А – 2, Б – 5, С – 1, Д – 4. Без построения

графа, определить число ребер графа.

Решение: Первое, что должны проверить дети: возможно ли построение такого

графа. Чтобы проверить это, надо сосчитать число нечетных вершин – их должно быть

четно. По условию задачи 2 нечетных вершины Б и С, значит построение возможно.

Теперь можно ответить на вопрос задачи, используя второе свойство: (2+5+1+4):2=6.

После решения задачи можно предложить детям построить этот граф и проверить

решение. Причем рисунки могут получиться совершенно разные, в зависимости от того,

какие вершины будут соединены (рис.14-16). Самое главное, чтобы степени вершин

соответствовали условию задачи. Эти задания не сложные и доступны учащимся 5

классов.

рис.14 рис.15 рис.16

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

непрерывной последовательностью ребер. Другими словами: из любой вершины можно

пройти в другую вершину по ребрам (рис.17-18).

Несвязный граф – граф, который состоит из нескольких частей, каждая из которых

или связный граф, или отдельные вершины (рис.19).

рис.17

рис.18

рис.19

Предложенный выше теоретический материал по графам вполне доступен детям 5-

6 классов. Рассмотрим ниже основные задачи, опираясь на которые можно построить

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

математических олимпиадах или в разделе задач со звездочками.

1.

Десять человек приветствовали друг друга рукопожатиями. Пять человек

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

сделано рукопожатий?

Решение: Вначале надо разобраться с детьми, правильно ли они понимают понятие

рукопожатие на языке графов. Одно рукопожатие – это две вершины соединены одним

ребром. То есть, два человека и у них одно рукопожатие на двоих. Данную задачу можно

переформулировать на язык графов следующим образом: дано 10 вершин, известны

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

количество ребер в графе надо сложить степени каждой вершины и разделить пополам –

применить второе свойство . Так как пять человек сделали по семь рукопожатий, то это

значит, что из пяти вершин выходят по семь ребер, а всего ребер: 5+5+5+5+5+5+5=5

∙

7.

Аналогично рассуждаем и с остальными вершинами, получаем:

(

5∙ 7

+

3 ∙ 5

+

2 ∙ 4

)

2

=

(

35

+

15

+

8

)

2

=

58

2

=

29

2.

Можно ли организовать футбольный турнир девяти команд так, чтобы

каждая команда провела по четыре встречи?

Решение: Переформулируем задачу на язык графов: можно ли построить такой

граф, у которого 9 вершин и степень каждой вершины равна 4. По свойству два, найдем

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

противном случае – нельзя. (9

∙

4):2=18. Да, можно и будет сыграно 18 игр.

3.

Можно ли 15 телефонов соединить между собой так, чтобы каждый из них

был связан ровно с 11 другими?

Решение: Переформулируем задачу на язык графов: можно ли построить такой

граф, у которого 15 вершин и степень каждой вершины равна 11. Применим второе

свойство: 15

∙

11: 2=82,5. Получили не натуральное число, значит нельзя соединить

телефоны.

4.

В государстве 100 городов, из каждого выходит 4 дороги. Сколько всего

дорог в государстве?

Решение: Одна дорога соединяет два города, т.е. две вершины соединены одним

ребром. Применим второе свойство: 100

∙

4:2 =200.

5.

Может ли в государстве, в котором из каждого города выходит 3 дороги,

быть ровно 100 дорог?

Решение: Решим задачу, составив уравнение: х

∙

3: 2=100, где х – число городов в

государстве. х

∙

3=200, х=66,(6) – число не натуральное, значит в таком государстве не

может быть ровно 100 дорог.

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

дальнейшему изучению теоретического материала по теме графы.

Цикл – замкнутый путь в графе. Графы бывают с циклом (рис.20 цикл выделен

голубым цветом) и без цикла (рис.21).

рис.20 рис.21 рис.22

Дерево – связный граф, не имеющий циклов (рис.22). Перед введением этого

определения обязательно надо повторить понятие связный граф. Далее предлагаем

задания следующего типа:

Задание: Среди предложенных графов (рис.23-26) найти графы-деревья и графы с

циклом. Укажите, сколько вершин входит в цикл?

рис.23 рис.24 рис.25 рис.26

Решение: Графы-деревья изображены на рис.24 и рис.25; графы с циклом – рис.23

(цикл состоит из 3 вершин) и рис. 26 (цикл состоит из 4 вершин).

Далее вводим еще одно важное свойство, которое очень часто применяется при

решении логических задач.

Свойство 3: Если граф связный и нечетных вершин у него 0 или 2, то его можно

обойти, пройдя по каждому ребру только один. По-другому можно переформулировать

это свойство так: Если граф связный и нечетных вершин у него 0 или 2, то его можно

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

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

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

Как правило, задания на это свойство вызывают у детей наибольший интерес.

Задание: Из предложенных графов (рис.27- 33) найти те, которые можно

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

ребру дважды) и нарисовать их в тетради.

рис.27 рис.28 рис.29 рис.30

рис.31 рис.32 рис.33

Решение: Для решения этого задания необходимо посчитать степени всех вершин,

определить нечетные вершины и посчитать их количество. Если их 2 или 0, то граф

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

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

графов надо знать: если граф имеет две нечетных вершины, то его изображение надо

начинать из одной нечетной вершины, а заканчивать – в другой. Если же все вершины

графа четные, то начало и конец графа совпадают. Графы, изображенные на рис.27, 28, 33

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

В качестве домашнего задания можно предложить детям проанализировать

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

росчерком, а какие нельзя и объяснить почему?

Если применить немного фантазии и воображения, то одним росчерком можно

изобразить много необычных рисунков (рис.34-36).

рис.34 рис.35 рис.36

Для отработки понятия Эйлеров граф полезно дать задание следующего типа:

Задание: Достроить графы до Эйлеровых (рис.37-39)

рис. 37 рис. 38 рис.39

Решение: Чтобы решить это задание, надо сначало посчитать степень каждой

вершины и дополнить ребрами граф так, чтобы стало две нечетных вершины или ни

одной. На рис. 40-42 представлен один из вариантов решения.

рис.40 рис.41 рис.42

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

для решения задач, с применением теории графов, можно выделить следующие этапы:

1.

Анализ условия задачи и перевод ее на язык графов;

2.

Геометрическая интерпретация условия, построение графа. Именно на этом

этапе очень важен элемент творчества потому, что далеко не просто найти соответствия

между элементами условия и соответствующими элементами графа;



Точками обозначают объекты задачи (вершины графа). Если в задачах дано

несколько групп объектов, то лучше их изображать в разных плоскостях и различными

цветами;



Линиями (отрезками, дугами) обозначают отношения между объектами

(рёбра графа). Отношения могут быть двух типов: принадлежит и не принадлежит. Если

отношение «принадлежит», то линии сплошные, если отношение «не принадлежит» -

пунктирные;

3.

Выделяем ключевые фразы задач и, анализируя их, проводим ребра;

4.

Если ключевых фраз не достаточно для решения задачи, то анализируем

граф и проводим недостающие ребра;

5.

Выбираем нужные отношения (сплошные линии) и записываем ответ.

Использование графов в качестве некоторого вспомогательного средства позволяет

облегчить процесс обучения и подготовить учеников к восприятию сложных тем в курсе

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

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

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

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

Таким образом, применяя теорию графов в школьном курсе математики, решение

многих математических задач и доказательств упрощается, придает им наглядность и

простоту.