Статья: Обучение решению математических задач с помощью графов

👉🏻👉🏻👉🏻 ВСЯ ИНФОРМАЦИЯ ДОСТУПНА ЗДЕСЬ ЖМИТЕ 👈🏻👈🏻👈🏻

При подготовке учащихся к математической олимпиаде часто сталкиваешься с проблемой- каким методам решения задач уделить больше времени. Можно предложить, например, такие критерии: чтобы детям было интересно, чтобы данным методом решался большой круг задач, чтобы можно было использовать исторический материал и т. п. Всем этим критериям в полной мере удовлетворяет метод, основанный на применении графов. Один из авторов предлагаемой вниманию читателей статьи – декан физико-математического факультета ХГПУ Анатолий Егорович Поличка несколько лет преподает школьникам и студентам элементы теории графов и учит их применять графы к решению задач. Более того, он активно привлекает к этому делу своих учеников – студентов ХГПУ.
Как и в спорте, тренировка юного математика требует затраты большого времени. Для успеха на олимпиаде необходимы некоторые специальные типы одаренности.
Не следует забывать о том, что не всякий может в непривычной и суровой атмосфере олимпиадного конкурса продемонстрировать все, на что он способен. Как правило конкурсный КПД оказывается значительной ниже 100%. В связи с этим, полезно располагать хотя бы некоторым запасом прочности, чтобы быть застрахованным от случайности.
Теперь можно точнее сформулировать основную задачу факультатива: как можно полнее развить потенциальные творческие способности каждого слушателя факультатива, не ограничивая заранее сверху уровень сложности используемого задачного материала. Как видно, личная цель – подготовка к олимпиаде – совпадает с общественной – повышения уровня математической подготовки учащихся средней школы.
Обращаю внимание на то, что олимпиады проверяют в отличии от экзаменов сообразительность, а не выучку; поэтому самое лучшее – если школьник, не рассчитывая на свои знания, разовьет все свои способности, на которых бы основывались "экспромты".
Решение задач – это работа несколько необычная, а именно умственная работа. А чтобы научиться какой-либо работе, нужно предварительно хорошо изучить тот материал, над которым придется работать, те инструменты с помощью которых выполняется эта работа.
Значит, для того чтобы научиться решать задачи, надо разобраться в том, что собой они представляют, как они устроены, из каких составных частей они состоят, каковы инструменты, с помощью которых производится решение задач.
Решая практические задачи с помощью теории графов ясно видно, что в каждом шаге, в каждом этапе ее решения необходимо применить творчество. С самого начала, на 1 этапе, оно заключается в том, суметь проанализировать и закодировать условия задачи. Второй этап – схематическая запись. состоит в геометрическом представлении графов, и на этом этапе элемент творчества очень важен потому, что далеко не просто найти соответствия между элементами условия и соответствующими элементами графа.
Все остальные этапы тоже не обходятся без применения творчества и изобретательности. Проведение поиска способа и осуществления решения задачи (с проверкой и исследованием) нуждается в следующих способностях решающих: способность абстрагирования, способность моделирования, способность гибкого применения теории графов, способность применения всех известных математических способов решения. Бесспорно, формулирование ответа задачи это тоже творческое изобретение, т.к. также необходима и кодировка и абстрагирование. Заключительный анализ задачи тоже не легок, необходимо творчески найти то рациональное зерно, по которому можно будет определить к какому типу задач относится данная решенная.
По данной проблеме разработаны следующие классификации:
Первая классификация необходима для построения теоретического курса, так как каждый теоретический факт, включенный в факультативный курс должен быть закреплен при решении задач теоретического характера.
Вторая классификация необходима для выявления связи теории графов с другими разделами математики. Задачи 3-го типа этой классификации решаются с помощью выбора некоторых элементов из теории графов и применения их в других теориях. То есть при решении таких задач не достаточно знать одну теорию и успешно ее применять, необходимо оперировать понятиями и приемами сразу нескольких теорий.
Приведем примеры решения некоторых задач.
Как вы помните, охотник за мертвыми душами Чичиков побывал у известных помещиков по одному разу у каждого. Он посещал их в следующем порядке: Манилова, Коробочку, Ноздрева, Собакевича, Плюшкина, Тентетникова, генерала Бетрищева, Петуха, Констанжолго, полковника Кошкарева. Найдена схема, на которой Чичиков набросал взаимное расположение имений и проселочных дорог, соединяющих их. Установите, какое имение кому принадлежит, если ни одной из дорог Чичиков не проезжал более одного раза.
По схеме дорог видно, что путешествие Чичиков начал с имения Е, а окончил имением О. Замечаем, что в имения В и С ведут только две дороги, поэтому по этим дорогам Чичиков должен был проехать. Отметим их жирной линией. Определены участки маршрута, проходящие через А: АС и АВ. По дорогам АЕ, АК и АМ Чичиков не ездил. Перечеркнем их. Отметим жирной линией ЕD ; перечеркнем DK . Перечеркнем МО и МН; отметим жирной линией MF; перечеркнем FO; отметим жирной линией FH, НК и КО. Найдем единственно возможный при данном условии маршрут. И получаем: имение Е – принадлежит Манилову, D- Коробочке, С – Ноздреву, А – Собакевичу, В – Плюшкину, М – Тентетникову, F - Бетрищеву, Н – Петуху, К – Констанжолго, О – Кошкареву.
Участники музыкального фестиваля, познакомившись, обменялись конвертами с адресами. Докажите, что:
а) всего было передано четное число конвертов;
б) число участников, обменявшихся конвертами нечетное число раз, четно.
Решение: Пусть участники фестиваля А1, А2, А3 . . . , Аn – вершины графа, а ребра соединяют пары вершин, изображающих ребят, обменявшихся конвертами:
а) степень каждой вершины Аi показывает число конвертов, которое передал участник Аi своим знакомым. Общее число переданных конвертов N равно сумме степеней всех вершин графа N = степ. А1 + степ. А2 + + . . . + степ. Аn-1 + степ. Аn , N=2p, где p – число ребер графа, т.е. N – четное. Следовательно, было передано четное число конвертов;
б) в равенстве N = степ. А1 + степ. А2 + + . . . + степ. Аn-1 + степ. Аn сумма нечетных слагаемых должна быть четной, а это может быть только в том случае, если число нечетных слагаемых четно. А это означает, что число участников, обменявшихся конвертами нечетное число раз, четное.
Лист бумаги Плюшкин разрезал на 3 части. Некоторые из полученных листов он также разрезал на три части. Несколько новых листиков он вновь разрезает на три более мелкие части и т.д. Сколько Плюшкин получает листков, если разрезает k листков?
Девять шахматистов проводят турнир в один круг (каждый участник должен сыграть с каждым из остальных по одному разу). Покажите, что в любой момент найдутся двое, закончившие одинаковое число партий.
Решение. Переведем условие задачи на язык графов. Каждому из шахматистов поставим в соответствие вершину графа, соединим ребрами попарно вершины, соответствующие шахматистам, уже сыгравшим между собой партию. Получим граф с девятью вершинами. Степени его вершин равняются числу партий, сыгранных соответствующими игроками. Покажем, что во всяком графе с девятью вершинами всегда найдутся хотя бы две вершины одинаковой степени.
Каждая вершина графа с 9-тью вершинами может иметь степень, равную 0, 1, 2, 3, 4, 5, 6, 7, 8. Предположим, что существует граф, все вершины которого имеют разную степень, т.е. каждое из чисел последовательности 0, 1, 2, 3, 4, 5, 6, 7, 8 является степенью одной и только одной из его вершин. Но этого не может быть. Действительно, если в графе есть вершина степени 0, то в нем не найдется вершина со степенью 8, так как эта вершина должна быть соединена со всеми остальными вершинами графа в том числе и с той, у которой степень =0. Иначе говоря, в графе с 9-тью вершинами не могут быть одновременно вершины степени 0 и 8. Следовательно найдутся хотя бы две вершины, степени которых равны между собой. Получили, что в любой момент времени найдутся хотя бы двое, сыгравшие одинаковое число партий.
Кто играет Тяпкина-Ляпкина. В школьном драмкружке решили ставить гоголевского «Ревизора». И тут разгорелся жаркий спор. Все началось с Ляпкина-Тяпкина.
Ляпкиным-Тяпкиным буду я! – решительно заявил Гена.
Нет, я буду Ляпкиным-Тяпкиным, - возразил Дима, - с раннего детства мечтал воплотить этот образ на сцене.
Ну, хорошо, согласен уступить эту роль, если мне дадут сыграть Хлестакова, - проявил великодушие Гена.
. . . А мне – Осипа, - не уступил ему в великодушии Дима.
Хочу быть Земляникой или Городничим, - сказал Вова.
Нет, Городничим буду я, - хором закричали Алик и Боря. – Или Хлестаковым, добавили они одновременно.
Удастся ли распределить роли так, чтобы исполнители были довольны?
Решение. Попробуем построить граф для данной ситуации. Изобразим юных актеров кружками верхнего ряда: А –Алик, Б – Боря, В – Вова, Г – Гена, Д – Дима, а роли, которые они собираются играть, - кружками второго ряда (1 – Ляпкин-Тяпкин, 2 – Хлестаков, 3 – Осип, 4 – Земляника, 5 - Городничий). Затем от каждого участника проведем отрезки, т.е. ребра к ролям, которые он хотел бы сыграть. У нас получится граф с десятью вершинами и десятью ребрами.
Чтобы решить задачу, нужно из десяти выбрать пять ребер, не имеющих общих вершин. Сделать это легко. Достаточно заметить, что в вершины 3 и 4 ведет по одному ребру, из вершин Д и В соответственно. Это означает, что Осипа (вершина 3) должен играть Дима, а Землянику – Вова. Вершина 1 – Ляпкин-Тяпкин соединена ребрами с Г и Д. Ребро 1 – Д отпадает, так как Дима уже занят, остается ребро 1 – Г, Ляпкина-Тяпкина должен играть Гена. Остается соединить вершины А и Б с вершинами 2 и 5, соответствующим ролям Хлестакова и Городничего. Это можно сделать двумя способами: либо выбрать ребра А - 5 и Б – 2, либо ребра А – 2 и Б – 5. В первом случае Алик будет играть Городничего, а Боря – Хлестакова, во втором случае – наоборот.
Задача о Кенигсбергских мостах. Город Кенигсберг (ныне Калининград) расположен на берегах и двух островах реки Прегель (Преголи). Различные части города соединены семью мостами, как показано на рисунке. В воскресные дни горожане совершают прогулки по городу. Можно ли выбрать такой маршрут, чтобы пройти один и только один раз по каждому мосту и притом вернуться в начальную точку пути?
Обозначим различные части города буквами А, В, С, D, а мосты – буквами a, b, c, d, e, f, g. В этой задаче существенны лишь переходы через мосты: переходя через любой мост, мы всегда из одной части города попадем в другую, и, наоборот, переходя из одной части города в другую мы непременно пройдем по мосту. Поэтому изобразим план города в виде графа, вершины которого изображают отдельные части города, а ребра – мосты, соединяющие соответствующие части города.
Если бы существовал маршрут, удовлетворяющий условию задачи, то существовал бы замкнутый и непрерывный обход этого графа, проходящий один раз по каждому ребру. Иными словами, этот граф можно было бы вычертить, не отрывая карандаша от бумаги и не проходя дважды по одному и тому же ребру. Но это невозможно – какую бы вершину мы ни выбирали за исходную, нам придется проходить через остальные вершины, и при этом каждому «входящему» ребру (мосту, по которому мы вошли в эту часть города) будет соответствовать выходящее ребро (мост, которым мы воспользуемся затем, чтобы покинуть эту часть города): число ребер, входящих в каждую вершину, будет равно числу ребер выходящих из нее, т.е. общее число ребер, сходящихся в каждой вершине должно быть четным. Наш граф этому условию не удовлетворяет, и поэтому требуемого маршрута не существует.
П.Т.З. 7. "Наибольшее и наименьшее число элементов".
Город имеет в плане вид прямоугольника, разбитого на клетки: n улиц параллельны друг другу, m других пересекаются под прямым углом. На улицах города – но не на перекрестках – стоят милиционеры. Каждый милиционер сообщает номер проходящего мимо него автомобиля, направление его движения и время, когда он проехал. Какое наименьшее число милиционеров нужно расставить на улицах, чтобы по их показаниям можно было однозначно восстановить путь любого автомобиля, едущего по замкнутому маршруту (маршрут не проходит по одному и тому же участку улицы дважды)?
Наименьшее число милиционеров равно (m-1)(n-1).
Если милиционеры расставлены требуемым образом, то вся сетка улиц распадается на какое-то число k кусков, не содержащих замкнутых маршрутов (циклов), - иначе найдется цикл, по которому можно проехать не будучи замененным ни одним милиционером. Если оставшийся кусок сетки содержит р перекрестков то в нем содержится ровно р – 1 отрезков улиц. Так как перекрестков всего m n, то число отрезков, на которых нет милиционеров, равно mn – k. Общее число отрезков улиц равно 2mn – m – n. Таким образом, число занятых отрезков равно
Пример нужной расстановки (n – 1)(n – 1) милиционеров показан на рисунке

Название: Обучение решению математических задач с помощью графов
Раздел: Рефераты по математике
Тип: статья
Добавлен 06:53:06 05 мая 2007 Похожие работы
Просмотров: 3736
Комментариев: 17
Оценило: 6 человек
Средний балл: 4.5
Оценка: 5   Скачать

Срочная помощь учащимся в написании различных работ. Бесплатные корректировки! Круглосуточная поддержка! Узнай стоимость твоей работы на сайте 64362.ru
Если Вам нужна помощь с учебными работами, ну или будет нужна в будущем (курсовая, дипломная, отчет по практике, контрольная, РГР, решение задач, онлайн-помощь на экзамене или "любая другая" учебная работа...) - обращайтесь: https://clck.ru/P8YFs - (просто скопируйте этот адрес и вставьте в браузер) Сделаем все качественно и в самые короткие сроки + бесплатные доработки до самой сдачи/защиты! Предоставим все необходимые гарантии.
Привет студентам) если возникают трудности с любой работой (от реферата и контрольных до диплома), можете обратиться на FAST-REFERAT.RU , я там обычно заказываю, все качественно и в срок) в любом случае попробуйте, за спрос денег не берут)
Да, но только в случае крайней необходимости.

Статья: Обучение решению математических задач с помощью графов
Курсовая работа по теме Биоэтические аспекты использования животных в биомедицине
Дипломная работа: Формирование распределение и использование денежных средств предприятий государства и других
Дипломная работа по теме Організація бухгалтерського обліку за національними стандартами на підприємстві
Курсовая Список Литературы На Тему
Дипломная работа по теме Взаимодействие органов власти со средствами массовой информации на примере муниципального образования города Кургана
Малое Предпринимательство В Российской Федерации Реферат
Статья: Вычисление собственных чисел и собственных функций опрератора Штурма-Лиувилля на полуоси
Случай На Птичьем Дворе Сочинение 5 Класс
Реферат: Taking Things Forr Granted Essay Research
Реферат На Тему Здоровый Образ Жизни У Детей
Курсовая работа по теме Анализ деятельности ИФНС по Ленинскому району г. Ульяновска
Пособие по теме Билеты с ответами по географии (9 класс)
Реферат по теме Биография Петра Первого
Курсовая Работа На Тему Теории Происхождения И Предпосылки Возникновения Денег
Курсовая работа по теме Развитие организационно-управленческой мысли в России (на примере ОАО 'Роснефть')
Реферат: Задачі з міжнародного менеджменту
Курсовая работа: Налоговый учёт прочих расходов (представительские расходы, командировочные расходы, расходы на рекламу)
Реферат: Вопросы защиты прав, нарушенных иностранным арбитражным решением
Судовые Двигатели Внутреннего Сгорания Курсовая
Реферат: Социализация
Реферат: Холдинг
Сочинение: Вечная молодость "Педагогической поэмы" А.С.Макаренко
Доклад: Творческий путь А.Н. Островского