Применение теории графов к решению задач

Приложение. (Слайд 1).

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

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

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

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

Схема такого вида называется графом. Точки – вершины графа, соединяющие их линии – ребра.

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

В переводе на задачи “одним росчерком” это звучит так: “Если на рисунке все точки четные, то такой рисунок можно нарисовать одной линией, не отрывая карандаша от бумаги и не проводя дважды по одной линии; если на рисунке 2 нечетные точки (если есть одна нечетная точка, то обязательно есть и вторая), то такой рисунок также можно нарисовать одним росчерком, причем следует начинать с одной нечетной точки и заканчивать в другой нечетной точке; если же нечетных точек больше двух, то нарисовать такой рисунок одним росчерком не удастся.”

Так обвести одной линией рисунок (слайд 4) нельзя, т.к. он содержит сразу 8 нечетных точек.

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

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

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

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

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

Можно выделить (слайд 5)

• неориентированный граф;
• граф с цветными ребрами;
• ориентированный граф;
• граф-дерево или дерево возможностей .

Рассмотрим применение всех этих видов графов к решению задач.

Неориентированные графы. (Слайд 6). В них ребрами являются отрезки или части кривой линии.

Рассмотрим задачу: “В шахматном турнире участвовали 4 человека. Каждый спортсмен сыграл со всеми другими участниками соревнований по одному разу. Сколько всего было сыграно партий?” (Слайд 7). Изобразим участников турнира точками, а сыгранные ими партии – отрезками. (Слайд 8). Для того чтобы ответить на вопрос задачи, надо лишь подсчитать число проведенных отрезков, их 6, следовательно, было сыграно 6 партий.

Рассмотрим еще одну подобную задачу: “На лесной опушке встретились заяц, белка, лиса, волк, медведь и куница. Каждый, здороваясь, пожал каждому лапу. Сколько всего лапкопожатий было сделано? (Слайд 9). На графе 15 ребер, следовательно, было сделано 15 лапкопожатий. Для того чтобы упростить подсчет ребер графа, можно рассуждать так: из каждой из 6 точек выходит 5 отрезков, т.е. для подсчета отрезков умножаем 5 на 6, получаем 30, но при этом каждый отрезок мы посчитаем дважды (например, белка – лиса и лиса – белка). Следовательно, чтобы найти число ребер графа, надо 30 разделить на 2, получим.15. Такие рассуждения будут особенно полезны, когда граф содержит большее число вершин и подсчет числа ребер становится затруднительным.

Рассмотрим обратную задачу: “Несколько мальчиков встретились на вокзале, чтобы поехать за город в лес. При встрече все они поздоровались друг с другом за руку. Сколько мальчиков поехало за город, если всего было10 рукопожатий?” (Слайд 10).

Предположим, что встретились два мальчика, изобразим их точками, а рукопожатие линией, соединяющей эти точки. (Слайд 11). Добавляем третьего приятеля и получаем три рукопожатия. (Слайд 12). Значит, необходимо добавить еще четвертого мальчика. Если встретились четыре мальчика, то рукопожатий будет шесть. (Слайд 13). Необходимо добавить следующего, пятого мальчика. На получившемся графе видно (Слайд 14), что рукопожатий получилось 10. Следовательно, на вокзале встретилось пять мальчиков.

Рассмотрим еще один вид задач, где применимы неориентированные графы: “В первенстве класса по шашкам 5 участников: Аня, Боря, Влад, Гриша, Даша. Первенство проводится по круговой системе – каждый из участников играет с каждым из остальных один раз. К настоящему времени некоторые игры уже проведены: Аня сыграла с Борей, Владом и Дашей; Боря сыграл, как уже говорилось, с Аней и еще с Гришей; Влад – с Аней и Дашей, Гриша – с Борей, Даша – с Аней и Гришей. Сколько игр проведено к настоящему времени и сколько еще осталось?” (Слайд 15).

Участников соревнований изобразим точками, которые назовем первыми буквами имен детей. Если двое участников уже сыграли между собой, соединим изображающие их точки отрезками. Получим граф. (Слайд 16).

Число игр, проведенных к настоящему моменту, равно числу ребер, т.е. шести. Чтобы узнать число игр, которые осталось провести, соединим линиями другого цвета (или пунктиром) тех участников, которые еще не играли друг с другом. Таких ребер получилось 4, значит, осталось провести 4 игры: Борис – Влад, Борис – Даша, Влад – Гриша, Гриша – Аня. (Слайд 16).

Применить теорию графов можно и при решении следующей задачи: “В стране алфавит 8 городов: А, Б, В, Г, Д, Е, Ж, З и восемь непересекающихся дорог между городами А и Б, Е и Д, Б и Ж, З и А, В и Г, Г и Д, Ж и З, В и Е. Можно ли по этим дорогам проехать из А в Г?” (Слайд 17).

Построим по условию задачи граф, при этом все вершины графа сразу отмечать не будем. Начнем с построения ребер графа, учитывая то условие, что они не пересекаются. Построим отрезки АБ и ЕД, присоединим к отрезку АБ отрезки БЖ и ЗА. Построим отрезок ВГ, не пересекающий ни один из построенных отрезков и соединим точки Г и Д, Ж и З, В и Е (не обязательно отрезками, можно и кривыми линиями). По графу видно, что точки А и Г друг с другом не соединены, а значит, по указанным дорогам из города А в город Г проехать нельзя. (Слайд 18).

Для решении задач на упорядочивание множеств будем применять ориентированные графы. (Слайд 19). В этом случае одну вершину считают началом ребра, а другую – концом. В ориентированном графе все ребра должны быть ориентированы.

Попробуем вначале эту задачу решить без использования графа. При этом условие, что Толя идет впереди Гали придется вначале пропустить, т.к. неясно, они идут перед Васей и Леной или позади их. И только после прочтения последнего условия и установления, что Толя идет за Леной, можно определить месторасположение Гали. (Слайд 20).

Когда же мы решаем эту задачу при помощи графов, нам лишь необходимо представить условие задачи на графе. Изобразим всех туристов точками, которые обозначим первыми буквами имен детей. В задаче рассматривается отношение “идти впереди”, поэтому стрелку будем ставить от впереди идущего к идущему вслед за ним. Вася идет впереди Лены, значит стрелку ставим от Васи к Лене. Толя впереди Гали – стрелку ставим от Толи к Гале. Также ставим стрелку от Лены к Толе, т.к. она идет впереди него. На графе видно (Слайд 21), что первый идет Вася, за ним Лена, Толя и Галя идет последней.

Рассмотрим еще одну задачу: “В детском лагере отдыха в одной комнате живут четыре девочки: Маша, Валя, Таня и Галя. Две из них ровесницы. Известно, что Таня старше Маши, которая моложе Гали. Таня моложе Вали, которая старше Гали. Кто ровесницы?” При решении задачи без использования графа будем расставлять первые буквы имен девочек от младшей к старшей. Из условия, что Маша моложе Гали непонятно, где поставить букву Г, слева или справа от буквы Т. И только после прочтения последнего условия можно сделать вывод, что Г стоит между Т и В. Получаем, что ровесниками могут быть только Таня и Валя. (Слайд 22).

Рассмотрим решение этой же задачи при помощи графа. В задаче рассматриваются два отношения “быть младше” и “быть старше”. Выберем одно из низ и построим граф отношения “быть старше”. При этом стрелку будем ставить от старшей девочки к младшей. (Слайд 23). По графу видно, что старше всех Валя, а Маша – младшая из девочек. Следовательно, ровесницы – это Галя и Таня.

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

Рассмотрим задачу: “На пришкольном участке растут 8 деревьев: яблоня, тополь, береза, рябина, дуб, клен, лиственница и сосна. Рябина выше лиственницы, яблоня выше клена, дуб ниже березы, но выше сосны, сосна выше рябины, береза ниже тополя, а лиственница выше яблони. Расположите деревья от самого низкого к самому высокому”. (Слайд 24). Будем решать ее при помощи графа. Для этого отметим все деревья точками, а точки обозначим первыми буквами названия деревьев. В задаче рассматриваются два отношения: “быть ниже” и “быть выше”. В нашем случае удобнее рассматривать отношение “быть ниже” и вести стрелку от более низкого дерева к более высокому. Если в задаче сказано, что рябина выше лиственницы, то стрелку ставим от лиственницы к рябине и т.д. Получаем граф, на котором видно, что самое низкое дерево – клен, затем идут яблоня, лиственница, рябина, сосна, дуб, береза и тополь. (Слайд 25).

Следующий тип графов, которые можно использовать при решении задач в начальной школе – это граф-дерево или дерево возможностей. Графы такого вида используются при решении комбинаторных задач, когда надо осуществить перебор всех возможных вариантов. (Слайд 26).

Рассмотрим задачу: “В столовой на горячее можно заказать щуку, грибы и баранину, на гарнир – картофель и рис, а из напитков – чай и кофе. Сколько различных вариантов обедов можно составить из указанных блюд? (Слайд 27).

Т.к. горячих блюд три, то поставим три точки. Каждую точку обозначим первой буквой названия блюда. От этих точек проведем по две линии вниз и поставим точки, т.к. гарниров два. Их также обозначим первыми буквами названий. От каждого гарнира также проведем по две линии, точки будут обозначать напиток. Каждый путь по этому графу соответствует одному из способов выбора. Число таких путей будет соответствовать числу точек в нижнем ряду. Сосчитаем точки третьего ряда на нашем графе. Их 12, значит, можно составить 12 различных обедов. (Слайд 28).

Рассмотрим еще одну, более сложную задачу: “Из наборного полотна взяли 2 карточки с цифрой 1 и 3 карточки с цифрой 5. Сколько различных пятизначных чисел можно составить из этих карточек?” (Слайд 29).

По графу видно, что всего таких чисел можно составить 10, причем все их можно легко перечислить. (Слайд 30).

Последний вид графов, которые мы рассмотрим – это граф с ребрами двух цветов. (Слайд 31). Эти графы соответствуют таким ситуациям, в которых одни пары элементов множества находятся между собой в данном отношении, а другие – нет.

Рассмотрим задачу: “В одном классе учатся Иван, Петр и Сергей. Их фамилии Иванов, Петров и Сергеев. Установи фамилию каждого из ребят, если известно, что Иван не Иванов, Петр не Петров и Сергей не Сергеев и что Сергей живет в одном доме Петровым”. (Слайд 32).

В этой задаче речь идет о двух множествах: множестве имен и множестве фамилий. В этом случае, конечно, можно решить задачу с использованием таблицы, но для решения задач с тремя множествами таблицы уже будут непригодны. В этом случае решение задачи можно осуществить с помощью графов. Обозначим имена мальчиков точками, точно также поступим и с множеством фамилий. Если для данной пары элементов отношение выполняется, то соединим их красной линией, а если нет – черной. (Слайд 33). На графе видно, что Иван не Иванов, Петр – не Петров, Сергей – не Сергеев и не Петров, т.к. Сергей и Петров живут в одном доме. Поскольку Сергей – не Сергеев и не Петров, то, значит, он Иванов. Проведем красную линию от Сергея к Иванову. Тогда Ивановым Петр быть не может – соединим соответствующие точки черной линией. Итак, Петр – не Иванов и не Петров, следовательно, он Сергеев. Остается, что Иван носит фамилию Петров.

Рассмотрим задачу, в которой требуется установить соответствие между тремя множествами: “Три друга – Алеша, Сергей и Денис – купили щенков разной породы: щенка ротвейлера, щенка колли и щенка овчарки. Известно, что: щенок Алеши темнее по окрасу, чем ротвейлер, Леси и Гриф; щенок Сергея старше Грифа, ротвейлера и овчарки; Джек и ротвейлер всегда гуляют вместе. У кого какой породы щенок? Назовите клички щенков.” (Слайд 34).

Изобразим условие задачи при помощи графа. (Слайды 35–37). В результате получим, что у Сергея щенок породы колли Леси, у Алеши щенок овчарки Джек, у Дениса щенок ротвейлера по кличке Гриф.

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