Комбинаторные задачи. Графы

Комбинаторные задачи. Графы

МОУ СОШ №8

, учитель математики

Актуальность

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

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

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

Задачи

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

Комбинаторные задачи. Графы

Слово «граф» в математике означает картинку, где нарисовано несколько точек, некоторые из которых соединены линиями. Графами являются блок – схемы программ для ЭВМ, сетевые графики строительства, где вершины – события, означающие окончания работ на некотором участке, а ребра, связывающие эти вершины, - работы, которые возможно начать по совершении одного события и необходимо выполнить для совершения следующего.

Сначала приведём довольно-таки общие рассуждения, которые имеют отношение к решению произвольных нетривиальных (или как их называют в узком смысле – ``олимпиадных'') задач, а потом переходим к непосредственному разбору конкретных комбинаторных задач, используя введённые понятия.

Процесс решения задачи

Существенным отличием задач, является то, что они ``полностью определены'', т. е. четко описаны на подходящем языке. Чаще всего это язык математики. Задачи, с которыми мы сталкиваемся в реальной жизни, не являются полностью определёнными. Чаще они описаны на естественном языке, который обладает 4 недостатками: он неполон, избыточен, неоднозначен и неточен.

Поставить задачу означает, прежде всего, понять условие задачи (т. е. удалить неполноту, избыточность и неоднозначность) или найти соответствующее представление. Задача понята только тогда, когда найдено такое представление, в котором все элементы задачи представлены без избыточности и многозначности. Для одной и той же задачи всегда можно привести несколько разных замкнутых формулировок. Не всегда при этом есть одна наиболее «естественная» формулировка. Если даже такая формулировка одна, не всегда просто её найти. Иногда нахождение такой формулировки – основное в решении задачи.

Подход к решению задачи включает следующие основные этапы:

Выяснение смысла условий задачи. Первые выводы из условий задачи. Проигрывание ситуации, обдумывание. Выбор наилучшего представления – поиск замкнутой формулировки задачи. Частичное (возврат к пункту 2) или общее решение. Проверка и обобщение решения.

Понятие комбинаторной задачи

Понятие комбинаторной задачи не имеет строгого определения. Иногда говорят о комбинаторных задачах в достаточно узком смысле слова, имея в виду практические задачи. Задачу имеет смысл называть комбинаторной, если ее решение состоит в переборе элементов x множества X. (При этом наравне с термином «комбинаторная» вполне подходит термин «переборная»'.)

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

Решение

Чёрную ладью можно поставить на шахматную доску p = 64 различными способами. Независимо от выбора поля чёрная ладья бьёт 15 полей, поэтому для второй ладьи остаётся 64 – 15 = 49 полей, то есть q = 49. Всего число возможных способов, по правилу произведения, равно pq = 64 ∙ 49 = 3136. Ответ. 3136.

Графы

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

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

Одной из таких задач-головоломок была задача о кёнигсбергских
мостах, которая привлекла к себе внимание Леонарда Эйлера.

В Кёнигсберге (ныне Калининград) было семь мостов через реку Прегель (где Л - левый берег, П — правый берег, А и Б — остро­ва). Вопрос заключался в следующем: можно ли, прогуливаясь по горо­ду, пройти через каждый мост ровно один раз?

Решение задачи. Определим четность  вершин графа на рисунке 1. Вершина А имеет индекс 5, Б — 3, П  - 3 и Л – 3. Таким образом, мы имеем четыре вершины нечетного индекса, следовательно, данный граф не является уникурсальным. Отсюда получаем, что во время прогулки по городу нельзя  пройти по каждому из семи мостов только один раз.

Еще одной задачей-головоломкой, связанной с графами и именем Эйле­ра, является задача о трех домиках и трех колодцах.

Три соседа имеют три общих колодца. Можно ли провести непересека­ющиеся дорожки от каждого дома к каждому колодцу

Решение. Предположим, что это можно сделать. Отметим домики точками Дг, Д2, Д3, а колодцы точками Кг, К.2, К3. Каж­дую точку-домик соединим с каждой точкой-колодцем. Получим девять ребер, которые попарно не пересекаются.

Эти ребра образуют на плоскости многоугольник, разделенный на более мелкие многоугольники. Поэтому для этого разбиения должно выполняться соотношение Эйлера В - Р + Г = 1. Добавим к рассматри­ваемым граням еще одну — внешнюю часть плоскости. Тогда соотноше­ние Эйлера примет вид В - Р + Г = 2, причем В = 6 и Р = 9. Следователь­но, Г = 5. Каждая из пяти граней имеет, по крайней мере, четыре ребра, поскольку по условию задачи ни одна из дорожек не должна непосред­ственно соединять два дома или два колодца. Так как каждое ребро - лежит ровно в двух гранях, то количество ребер должно быть не меньше

5*4

—- = 10, что противоречит условию, по которому их число равно 9.

2

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

Проведение исследования

на выявление навыков решений задач комбинаторного типа

Исследования показали следующее

1 опыт. Решение комбинаторных задач без раздаточного материала

4 ученика получили верные ответы, то характер решения был универсальный, у  каждого свой; 7 решили верно только 1 задачу, к  остальным были предложены варианты решений, но они изначально были не верны; 32 учеников ни одну задачу не решили, но были попытки решений;

20 человек не решили задачи, предложений решений тоже не было.

2 опыт. Решение комбинаторных задач с использованием  раздаточного материала

9 решили верно:

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

2 ученика решили задачи верно, но с универсальным решением;

6 человек решили  1 задачу верно:

2 с использованием предложенных формул,

4 с универсальным решением;

33 ученика ни одну задачу не решили, но были попытки решений; 15 человек не решили задачи, предложений решений тоже не было.

ВЫВОДЫ:

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

Данная исследовательская работа имеет как теоретическое, так и практическое значение. Её можно использовать и педагогу, для объяснения комбинаторных задач и задач с графами, и учащимся, для дополнительного или самостоятельного изучения этого вопроса, и всем тем, кому комбинаторные задачи представляют особый интерес.