Обучение решению математических задач с помощью графов (стр. 1 из 2)

Е.А. Кудревич, А.Е. Поличка, кафедра математического анализа ХГПУ

При подготовке учащихся к математической олимпиаде часто сталкиваешься с проблемой- каким методам решения задач уделить больше времени. Можно предложить, например, такие критерии: чтобы детям было интересно, чтобы данным методом решался большой круг задач, чтобы можно было использовать исторический материал и т. п. Всем этим критериям в полной мере удовлетворяет метод, основанный на применении графов. Один из авторов предлагаемой вниманию читателей статьи – декан физико-математического факультета ХГПУ Анатолий Егорович Поличка несколько лет преподает школьникам и студентам элементы теории графов и учит их применять графы к решению задач. Более того, он активно привлекает к этому делу своих учеников – студентов ХГПУ.

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

Не следует забывать о том, что не всякий может в непривычной и суровой атмосфере олимпиадного конкурса продемонстрировать все, на что он способен. Как правило конкурсный КПД оказывается значительной ниже 100%. В связи с этим, полезно располагать хотя бы некоторым запасом прочности, чтобы быть застрахованным от случайности.

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

Обращаю внимание на то, что олимпиады проверяют в отличии от экзаменов сообразительность, а не выучку; поэтому самое лучшее – если школьник, не рассчитывая на свои знания, разовьет все свои способности, на которых бы основывались "экспромты".

Решение задач – это работа несколько необычная, а именно умственная работа. А чтобы научиться какой-либо работе, нужно предварительно хорошо изучить тот материал, над которым придется работать, те инструменты с помощью которых выполняется эта работа.

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

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

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

По данной проблеме разработаны следующие классификации:

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

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

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

Приведем примеры решения некоторых задач.

П.Т.З. 1. "Маршруты".

Как вы помните, охотник за мертвыми душами Чичиков побывал у известных помещиков по одному разу у каждого. Он посещал их в следующем порядке: Манилова, Коробочку, Ноздрева, Собакевича, Плюшкина, Тентетникова, генерала Бетрищева, Петуха, Констанжолго, полковника Кошкарева. Найдена схема, на которой Чичиков набросал взаимное расположение имений и проселочных дорог, соединяющих их. Установите, какое имение кому принадлежит, если ни одной из дорог Чичиков не проезжал более одного раза.

Д К

Е С

Н

О

А F

В М

Решение:

По схеме дорог видно, что путешествие Чичиков начал с имения Е, а окончил имением О. Замечаем, что в имения В и С ведут только две дороги, поэтому по этим дорогам Чичиков должен был проехать. Отметим их жирной линией. Определены участки маршрута, проходящие через А: АС и АВ. По дорогам АЕ, АК и АМ Чичиков не ездил. Перечеркнем их. Отметим жирной линией ЕD ; перечеркнем DK . Перечеркнем МО и МН; отметим жирной линией MF; перечеркнем FO; отметим жирной линией FH, НК и КО. Найдем единственно возможный при данном условии маршрут. И получаем: имение Е – принадлежит Манилову, D- Коробочке, С – Ноздреву, А – Собакевичу, В – Плюшкину, М – Тентетникову, F - Бетрищеву, Н – Петуху, К – Констанжолго, О – Кошкареву.

Д К

Е С

Н О

А F

В М

П.Т.З. 2 "Группы, знакомства"

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

а) всего было передано четное число конвертов;

б) число участников, обменявшихся конвертами нечетное число раз, четно.

Решение: Пусть участники фестиваля А1, А2, А3 . . . , Аn – вершины графа, а ребра соединяют пары вершин, изображающих ребят, обменявшихся конвертами:

А2

А1 А3

А4

А7

А6 А5

а) степень каждой вершины Аi показывает число конвертов, которое передал участник Аi своим знакомым. Общее число переданных конвертов N равно сумме степеней всех вершин графа N = степ. А1 + степ. А2 + + . . . + степ. Аn-1 + степ. Аn , N=2p, где p – число ребер графа, т.е. N – четное. Следовательно, было передано четное число конвертов;

б) в равенстве N = степ. А1 + степ. А2 + + . . . + степ. Аn-1 + степ. Аn сумма нечетных слагаемых должна быть четной, а это может быть только в том случае, если число нечетных слагаемых четно. А это означает, что число участников, обменявшихся конвертами нечетное число раз, четное.