Теория графов. Применение теории графов при решении задач

Начало теории графов все единодушно относят к 1736 г. , когда Л. Эйлер решил популярную в то время задачу о кенигсберских мостах. Однако этот результат более ста лет оставался единственным результатом теории графов. Лишь в середине XIX века инженер- электрик Г. Кирхгоф разработал теорию деревьев для исследования электрических цепей, а математик А. Кэли в связи с описанием строения углеводородов решил перечислительные задачи для трех типов деревьев.

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

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

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

Цель исследования - изучить применение графов в школьном курсе геометрии.

Объект – процесс обучения геометрии.

Предмет –классная и внеклассная работа

Задачи: 1) определить сущность и содержание применения графов в школьном курсе геометрии;

2) разработать ПМК для проведения уроков геометрии в 7-9 классах.

Ведущая тема – построение графовой модели для доказательства геометрических теорем.

Теоретическая основа:

1. Теория графов возникшая в 1736 году (Леонард Эйлер (1708-1783) получила бурное развитие, остаётся актуальной и сейчас, т. к. в повседневной жизни всё большее применение находят графические иллюстрации, геометрические представления и другие приёмы и методы наглядности.

1. Теория графов находит применение в различных областях современной математики и её многочисленных приложений (Липатов Е. П. )

2. Теория графов применяется в таких областях математики, как математическая логика, комбинаторика и др.

Теоретическая значимость работы заключается в:

-выявление областей применения теории графов ;

- использование теории графов к изучению геометрических теорем и задач;

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

В результате выполнения данной работы создан:

- программно-методический комплекс для проведения уроков геометрии в 7-9 классах.

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

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

Для этого используется граф-дерево.

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

Исследовательская часть.

Раздел 1. Изучение истории возникновения теории графов.

Родоначальником теории графов принято считать математика Леонарда Эйлера (1707-1783). Историю возникновения этой теории можно проследить по переписке великого ученого. Вот перевод латинского текста, который взят из письма Эйлера к итальянскому математику и инженеру Маринони, отправленного из Петербурга 13 марта 1736 года.

"Некогда мне была предложена задача об острове, расположенном в городе Кенигсберге и окруженном рекой, через которую перекинуто семь мостов. Спрашивается, может ли кто-нибудь непрерывно обойти их, проходя только однажды через каждый мост. И тут же мне было сообщено, что никто еще до сих пор не мог это проделать, но никто и не доказал, что это невозможно. Вопрос этот, хотя и банальный, показался мне, однако, достойным внимания тем, что для его решения недостаточны ни геометрия, ни алгебра, ни комбинаторное искусство. После долгих размышлений я нашел легкое правило, основанное на вполне убедительном доказательстве, с помощью которого можно во всех задачах такого рода тотчас же определить, может ли быть совершен такой обход через какое угодно число и как угодно расположенных мостов или не может. Кенигсбергские же мосты расположены так, что их можно представить на следующем рисунке, на котором A обозначает остров, а B, C и D – части континента, отделенные друг от друга рукавами реки. Семь мостов обозначены буквами a, b, c, d, e, f, g ".

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

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

Так можно ли обойти Кенигсбергские мосты, проходя только один раз через каждый из этих мостов? Чтобы найти ответ, продолжим письмо Эйлера к Маринони:

"Вопрос состоит в том, чтобы определить, можно ли обойти все эти семь мостов, проходя через каждый только однажды, или нельзя. Мое правило приводит к следующему решению этого вопроса. Прежде всего, нужно смотреть, сколько есть участков, разделенных водой, – таких, у которых нет другого перехода с одного на другой, кроме как через мост. В данном примере таких участков четыре – A, B, C, D. Далее нужно различать, является ли число мостов, ведущих к этим отдельным участкам, четным или нечетным. Так, в нашем случае к участку A ведут пять мостов, а к остальным – по три моста, т. е. Число мостов, ведущих к отдельным участкам, нечетно, а этого одного уже достаточно для решения задачи. Когда это определено, применяем следующее правило: если бы число мостов, ведущих к каждому отдельному участку, было четным, то тогда обход, о котором идет речь, был бы возможен, и в то же время можно было бы начать этот обход с любого участка. Если же из этих чисел два были бы нечетные, ибо только одно быть нечетным не может, то и тогда мог бы совершиться переход, как это предписано, но только начало обхода непременно должно быть взято от одного из тех двух участков, к которым ведет нечетное число мостов. Если бы, наконец, было больше двух участков, к которым ведет нечетное число мостов, то тогда такое движение вообще невозможно если можно было привести здесь другие, более серьезные задачи, этот метод мог бы принести еще большую пользу и им не следовало бы пренебрегать".

Обоснование вышеприведенного правила можно найти в письме Л. Эйлера к своему другу Элеру от 3 апреля того же года. Мы перескажем ниже отрывок из этого письма.

Математик писал, что переход возможен, если на участке разветвления реки имеется не более двух областей, в которые ведет нечетное число мостов. Для того, чтобы проще представить себе это, будем стирать на рисунке уже пройденные мосты. Легко проверить, что если мы начнем двигаться в соответствии с правилами Эйлера, пересечем один мост и сотрем его, то на рисунке будет изображен участок, где опять имеется не более двух областей, в которые ведет нечетное число мостов, а при наличии областей с нечетным числом мостов мы будем располагаться в одной из них. Продолжая двигаться так далее, пройдем через все мосты по одному разу.

История с мостами города Кенигсберга имеет современное продолжение.

Задача На озере находится семь островов, которые соединены между собой так, как показано на рисунке 2. На какой остров должен доставить путешественников катер, чтобы они могли пройти по каждому мосту и только один раз? Почему нельзя доставить путешественников на остров A?

Решение. Поскольку эта задача подобна задаче о Кенигсбергских мостах, то при ее решении мы также воспользуемся правилом Эйлера. В результате получим следующий ответ: катер должен доставить путешественников на остров E или F, чтобы они смогли пройти по каждому мосту один раз. Из того же правила Эйлера следует невозможность требуемого обхода, если он начнется с острова A.

В дальнейшем над графами работали Кениг (1774-1833), Гамильтон (1805-1865), из современных математиков – К. Берж, О. Оре, А. Зыков.

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

Первая работа по теории графов, принадлежащая известному швейцарскому математику Л. Эйлеру, появилась в 1736 г. Толчок к развитию теория графов получила на рубеже ХIX и ХХ столетий, когда резко возросло число работ в области топологии и комбинаторики, с которыми ее связывают самые тесные узы родства. Графы стали использоваться при построении схем электрических цепей и молекулярных схем. Как отдельная математическая дисциплина теория графов была впервые представлена в работе венгерского математика Кенига в 30-е годы ХХ столетия.

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

Раздел 2. Основные виды, понятия и структура графов.

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

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

№ Название графа Определение Рисунок Пример применения этого вида графов

1 Нулевой граф Вершины графа, которые не принадлежат Задача: Аркадий, Борис. Владимир, Григорий и Дмитрий при встрече обменялись ни одному рукопожатиями, каждый пожал руку каждому по одному разу. Сколько всего ребру, называются изолированными. рукопожатий было сделано? Ситуация, соответствующая моменту, когда рукопожатия еще не совершались, представляет собой точечную схему, изображенную на рисунке.

Граф, состоящий только из изолированных вершин, называется нуль-графом.

Обозначение: O' – граф с вершинами, не имеющий ребер

2 Полные графы Граф, в котором каждая пара вершин Заметим, что если полный граф имеет n вершин, то количество ребер будет Совершены все рукопожатия.

соединена равно n(n-1)/2 Если подсчитать число ребер графа, изображенного на рисунке , то это число и ребром, называется полным. будет равно количеству совершенных рукопожатий между пятью молодыми людьми. Их

Обозначение: U' – граф, состоящий из n 10.

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

3 Неполные графы Графы, в которых не построены все Ситуация, когда совершены еще не все рукопожатия,пожали руки А и Б, А и Г, Д и возможные ребра , называются неполными Г, В и Д.

графами

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

вершинами.

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

началом пути, вершина в конце маршрута —

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

циклом называется цикл, не проходящий Например, из пункта A (вершина графа) в пункт H можно добраться различными ни маршрутами: ADGH, AEH, AEFCEH, ABCEH.

через одну из вершин графа более одного Чем отличается маршрут AEH от маршрута AEFCEH?

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

Этот маршрут длиннее, чем AEH. Маршрут AEH можно получить из маршрута

Если же цикл включает в себя все ребра AEFCEH «вычеркнув» из последнего маршрут FCE.

графа по одному разу, то такой цикл Маршрут AEH является путем в графе, а маршрут AEFCEH путем не является.

называется Эйлеровой линией.

Связные и несвязные графы. Определение 1: Можно ли из проволоки длиной 12 дм изготовить каркас куба с ребром длины

Две вершины графа называются связными, 1 дм, не ломая проволоку на части?

если в графе существует путь с концами в этих вершинах. Если такого пути не существует, вершины называются не связными.

Нельзя.

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

1) когда степень каждой вершины четная(путь замкнут)

2)когда только две вершины с нечетной степенью.

Определение 2:

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

Граф называется несвязным, если в нем есть хотя бы одна несвязная пара вершин.

6 Деревья Деревом называется любой связный граф, Приложение №1. Генеалогическое древо Жолмурзаевой Томирис.

не имеющий циклов.

Договорились считать «деревом» и всякий граф, состоящий из одной (изолированной)

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

7 Изоморфные графы. Графы, изображенные на рисунке , дают одну и ту же информацию. Такие графы называют изоморфными (одинаковыми).

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

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

Построим граф, вершины которого

А, Б, В, 1, 2, 3

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

Проведенные в графе на рисунке ребра

А1, А2, A3 и В1,В2, ВЗ (соответствующие тропинкам от домов А и В ко всем колодцам).

Построенный граф разбил плоскость на три области: X, У, Z. Вершина Б, в зависимости от ее расположения на плоскости, попадает в одну из этих трех областей. Если вы рассмотрите каждый из трех случаев «попадания» вершины

Б в одну из областей X, Y или Z, то убедитесь, что всякий раз одна из вершин графа 1, 2 или 3

(один из колодцев) будет «недоступной» для вершины Б (т. е. нельзя будет провести одно из ребер Б1, Б2 или Б3. которое не пересекло бы уже имеющихся в графе ребер).

Ответ на вопрос задачи будет: «Нельзя!»

Ориентированные графы Ребро графа называется ориентированным ребром, если одну из его вершин считать началом, а другую — концом этого ребра.

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

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

Вывод по проделанной работе:

• я научилась структурировать в таблицу весь информационный материал;

• скомпонованность теоретического материала способствуют наглядному представлению о видах графов и их применению;

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

Приложение №1.

ГЕНЕОЛОГИЧЕСКОЕ ДРЕВО

Задача.

Построить генеалогическое дерево Жолмурзаевой Томирис.

Метод решения.

Графический способ решения задачи.

Графический способ решения задачи заключается в вычерчивании «дерева логических условий». «Дерево» выражает в виде простого чертежа логическую взаимосвязь между родственниками. Каждому поколению на дереве соответствует одна ветвь.

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

Раздел 3. Применение теории графов.

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

3. 1. Применение графов в геометрических задачах и теоремах.

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

Задача.

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

Методы решений.

Доказательство задачи с помощью рассуждений.

Пусть АВС – равнобедренный треугольник с

В1 А1 основанием АВ и биссектрисами АА1 и ВВ1.

Рассмотрим ∆АВВ1 и ∆ВАА1. У них ∟В1АВ=

∟А1ВА как углы при основании равнобедрен – ного треугольника ∆АВС. ∟АВВ1= ∟А1АВ

А В так как АА1 и ВВ1 – биссектрисы углов при основании равнобедренного треугольника. АВ- общая сторона. Значит

∆АВВ1 = ∆ВАВ1 по стороне и двум прилежащим к ней углам. Из равенства треугольников следует равенство их сторон АА1 и ВВ1.

Доказательство задачи с помощью графа.

Доказать: АА=ВВ

Используем для рассуждений граф. Вершины графа- условия теоремы или задачи и этапы доказательства.

Ребра графа – логические следования. Конец граф-схемы – доказываемое утверждение.

Дя выделения составных частей использован цвет. Условие теоремы и задачи – синий. Доказываемое утверждение – красный. Этапы доказательства – черный.

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

3. 2. Программно- методический комплекс.

а) Пособие для учителя.

Предлагаемое пособие составлено в соответствии с учебником геометрии 7-9 классов А. В. Погорелова. Основное ее назначение обеспечить процесс изучения геометрии необходимыми средствами наглядностей, оказать помощь учителю в преподавании геометрии: облегчить процесс доказательства теорем, усвоение теоретического материала в процессе решения задач. Граф-схемы носят многоплановый характер и в зависимости от целей и форм занятий можно использовать по-разному: как иллюстративные, направленные на усиление наглядности при объяснении нового теоретического материала, при обобщении и систематизации нового материала (граф-схемы с теоремами); как карточки, используемые при проведении индивидуальных и фронтальных опросов (граф-схемы с задачами). К этому пособию предлагается рабочая тетрадь для учащихся. Рабочую тетрадь можно использовать для организации самостоятельной работы учащихся в урочное и внеурочное время.

б) Рабочая тетрадь для учащихся.

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

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

Пособие полезно для учащихся 7-9 классов.

в) Электронное пособие.

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

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

- проведения занятий клуба «Аристотель» по теме «Решение логических задач с помощью графов».

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

- на уроках геометрии в 8,9 классе.

- выступления с проектом на школьной научно- практической конференций.

ЗАКЛЮЧЕНИЕ.

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

1. Преимуществом графового доказательства теорем и решения задач перед традиционным является иллюстрация динамики доказательства теорем и задач.

2. Введение в процесс доказательства геометрических теорем и задач метода граф-схем способствует укреплению у учащихся навыков построения доказательства.

3. Разработанный программно-методический комплекс для изучения геометрии в 7-9 классах: а) пособие для учителя; б) рабочая тетрадь для учащихся; в) электронное пособие полезен учащимся 7-9 классов.