Реферат: «Теория графов. Реферат: «Теория графов Где применяются графы

Муниципальное общеобразовательное учреждение

«Средняя общеобразовательная школа № 6»

Реферат на тему:

«Теория графов»

Подготовила: Майорова Екатерина, 8Г класс

Учитель: Малова Татьяна Алексеевна

I. Введение

II. Основная часть.

1.История возникновения теории графов.

2.Некоторые задачи теории графов.

2.1 Логические задачи

2.2 Задачи на связность.

2.3 Задачи по теореме Эйлера о нечетных вершинах

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

3.1.Графы и информация

3.2.Графы и химия.

3.3.Графы и биология

3.4.Графы и физика

III. Заключение.

IV. Список литературы.

I. Введение.

Я выбрала эту тему, потому что она была и остается актуальной в наше время.

Сейчас почти в любой отрасли науки и техники встречается применение графов. В физике - при построении электрических схем, в химии и биологии

При изучении молекул и их цепочек, в географии – при составлении карт, в истории – при составлении родословной,

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

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

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

II. 1. История возникновения теории графов

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

Историю возникновения этой теории можно проследить по переписке великого ученого. В ней он сообщал, что ему была предложена задача о семи мостах Кенигсберга. Спрашивалось, может ли кто-нибудь непрерывно обойти их, проходя только однажды через каждый мост. И ему сразу же было сообщено, что никто еще до сих пор не мог это проделать, но никто и не доказал, что это невозможно. Вопрос этот показался ему достойным внимания тем, что «…Для его решения недостаточны ни геометрия, ни алгебра, ни комбинаторное искусство...». После долгих размышлений он нашел легкое правило, основанное на вполне убедительном доказательстве, с помощью которого можно во всех задачах такого рода определить, может ли быть совершен такой обход через какое угодно число и как угодно расположенных мостов или не может. Кенигсбергские же мосты расположены так, что их можно представить на рисунке, на котором А обозначает остров, а В, С и D - части континента, отделенные друг от друга рукавами реки. Семь мостов обозначены буквами а, b, с, d, е, f, g.

http://www.cba.upc.edu/projects/logos/Euler_logo.png Кенигсбергские мосты.

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

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

История с мостами города Кенигсберга имеет современное продолжение. В некоторых учебниках математики или в дополнительных материалах (приложениях) учебника можно встретить задачи, чьё решение основано именно на предложенном Эйлером способе.

Я поняла, что в ходе рассуждений Эйлер пришёл к следующим выводам:

Число нечётных вершин (вершин, к которым ведёт нечётное число рёбер) графа должно быть чётно. Не может существовать граф, который имел бы нечётное число нечётных вершин.

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

Граф с более чем двумя нечётными вершинами невозможно начертить одним росчерком.

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

Я, изучив эти выводы, решила проверить их на примерах других задач из раздела теории графов.

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

2. Некоторые задачи теории графов

Задач по теории графов не так много. Я рассмотрела материалы

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

^ 2.1 Логические задачи

Задача 1. Аркадий, Борис. Владимир, Григорий и Дмитрий при встрече обменялись рукопожатиями (каждый пожал руку каждому по одному разу). Сколько всего рукопожатий было сделано?
Пусть каждому из пяти молодых людей соответствует определенная точка на плоскости, названная первой буквой его имени (рис.2), а производимому рукопожатию - отрезок или часть кривой, соединяющая конкретные точки - имена (рис. 3).

Нулевой граф с пятью вершинами

Неполный граф с пятью вершинами

http://school-sector.relarn.ru/dckt/projects/ctrana/graf/gr1.htm

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

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

Полный граф с пятью вершинами

Задача 2. Доска имеет форму двойного креста, который получается, если из квадрата 4x4 убрать угловые клетки.

Можно ли обойти ее ходом шахматного коня и вернуться на исходную клетку, побывав на всех клетках ровно по одному разу?

Решение: я занумеровала последовательно все клетки:

А теперь с помощью рисунка показала, что такой обход таблицы, как указано в условии, возможен:

Задача 3. В городе Маленьком 15 телефонов. Можно ли их соединить проводами так, чтобы каждый телефон был соединен ровно с пятью другими?

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

Ответ. Соединить телефоны таким образом невозможно.

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

Задача 4. В государстве 100 городов, из каждого города выходит 4 дороги. Сколько всего дорог в государстве?

Решение. Подсчитаем общее количество выходящих городов дорог – 100 . 4 = 400. Однако при таком подсчете каждая дорога посчитана 2 раза – она выходит из одного города и входит в другой. Значит всего дорог в два раза меньше, т.е. 200.

Задача 5. Может ли в государстве, в котором из каждого города выходит ровно 3 дороги, быть ровно 100 дорог?

Решение. Подсчитаю число городов. Число дорог равно числу городов х, умноженному на 3 (число выходящих из каждого города дорог) и разделенному на 2.Тогда 100 = Зх/2 => Зх=200, чего не может быть при натуральном х. Значит, 100 дорог в таком государстве быть не может.

^ 2.2 Задачи на связность.

Есть еще одно важное понятие, относящееся к графам – понятие связности.

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

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

^ Графы Эйлера.

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

Задача 1. Можно ли нарисовать изображенный на рисунке граф не отрывая карандаш от бумаги и проводя каждое ребро ровно один раз?

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

^ 2.3 Задачи по теореме Эйлера о нечетных вершинах

Задача 1. В классе 30 человек. Может ли быть так, что 9 человек имеют по 3 друга, 11 – по 4 друга, а 10 – по 5 друзей?

Ответ. Нет (по теореме о четности числа нечетных вершин).

Задача 2. У короля 19 баронов-вассалов. Может ли оказаться так, что у каждого вассального баронства 1, 5 или 9 соседних баронств?

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

3. Применение теории графов.

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

3.1.Графы и информация

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

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

3.2.Графы и химия.

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

3.3.Графы и биология

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

процессов – размножение бактерий. Предположим, что через определенный

промежуток времени каждая бактерия либо делится на две новые, либо

погибает. Тогда для потомства одной бактерии я получу двоичное дерево.

Нас будет интересовать лишь один вопрос: в скольких случаях n-е

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

3.4.Графы и физика

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

Печатной схемой называют пластинку из какого-либо диэлектрика

(изолирующего материала), на которой в виде металлических полосок

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

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

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

III. Заключение

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

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

IV. Список литературы и Интернет-ресурсов.

1. "Соросовский образовательный журнал" №11 1996 (ст. "Плоские графы");

2. Касаткин В. Н. "Необычные задачи математики", Киев, "Радяньска школа"

1987(часть 2);

3. Гарднер М. "Математические досуги", М. "Мир", 1972(глава 35);

4. "В помощь учителю математики", Йошкар-Ола, 1972 (ст. "Изучение элементов теории графов");

5. Олехник С. Н., Нестеренко Ю. В., Потапов М. К. "Старинные занимательные

Задачи", М. "Наука", 1988(часть 2, раздел 8; приложение 4);

6. Гарднер М. "Математические головоломки и развлечения", М. "Мир", 1971;

7. Оре О. "Графы и их применения", М. "Мир", 1965;

8. Зыков А. А. "Теория конечных графов", Новосибирск, "Наука", 1969;

9. Берж К. "Теория графов и ее применение", М., ИЛ, 1962;

10. Реньи А., "Трилогия о математике", М., "Мир", 1980.

11. http://ru.wikipedia.org

12. http://www.xumuk.ru

13. http://www.seznaika.ru

Что такое метод графов?

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

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

Схема графа, состоящая из «изолированных» вершин, называется нулевым графом. (рис.2)

Графы, в которых не построены все возможные ребра, называются неполными графами. (рис.3)

Графы, в которых построены все возможные ребра, называются полными графами. (рис.4)

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

Заметим, что если полный граф имеет n вершин, то количество ребер будет равно

n(n-1)/2

Действительно, количество ребер в полном графе с n вершинами определяется как число неупорядоченных пар, составленных из всех n точек-ребер графа, т. е. как число сочетаний из n элементов по 2:

Граф, не являющийся полным, можно дополнить до полного с теми же вершинами, добавив недостающие ребра. Так, например, на рисунке 3 изображен неполный граф с пятью вершинами. На рисунке 4 ребра превращающие граф в полный граф изображены другим цветом, совокупность вершин графа с этими ребрами называется дополнением графа.

Степени вершин и подсчет числа ребер.

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

Если степени всех вершин графа равны, то граф называется однородным . Таким образом, любой полный граф - однородный.

рис.5

На рисунке 5 изображен граф с пятью вершинами. Степень вершины А обозначим Ст.А.

На рисунке: Ст.А = 1, Ст.Б = 2, Ст.В = 3, Ст.Г= 2, Ст.Д= 0.

Сформулируем некоторые закономерности, присущие определенным графам.

Закономерность 1.

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

Доказательство:

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

Закономерность 2.

Сумма степеней вершин графа число четное, равное удвоенному числу ребер графа.

Эта закономерность справедлива не только для полного, но и для любого графа. Доказательство:

Действительно, каждое ребро графа связывает две вершины. Значит, если будем складывать число степеней всех вершин графа, то получим удвоенное число ребер 2R (R - число ребер графа), т. к. каждое ребро было подсчитано дважды, что и требовалось доказать

Число нечетных вершин любого графа четно. Доказательство:

Рассмотрим произвольный граф Г. Пусть в этом графе число вершин, степень которых 1, равна К1; число вершин, степень которых 2, равно K2; ...; число вершин, степень которых n, равно Кn. Тогда сумму степеней вершин этого графа можно записать как
K1 + 2К2 + ЗК3 + ...+ nКn.
С другой стороны: если число ребер графа R, то из закономерности 2 известно, что сумма степеней всех вершин графа равна 2R. Тогда можно записать равенство
K1 + 2К2 + ЗК3 + ... + nКn = 2R. (1)
Выделим в левой части равенства сумму, равную числу нечетных вершин графа (К1 + К3 + ...):
K1 + 2К2 + ЗК3 + 4К4 + 5К5 + ... + nК = 2R,
(К1 + К3 + К5 +...) + (2K2 + 2Х3 +4K4 + 4К5 + ...)=2R
Вторая скобка- четное число как сумма четных чисел. Полученная сумма (2R) четное число. Отсюда (К1 + К3 + К5 +...)-четное число.

Рассмотрим теперь задачи, решаемые с помощью графов:

Задача. Первенство класса . В первенстве класса по настольному теннису 6 участников: Андрей, Борис, Виктор, Галина, Дмитрий и Елена. Первенство проводится по круговой системе – каждый из участников играет с каждым из остальных один раз. К настоящему моменту некоторые игры уже проведены: Андрей сыграл с Борисом, Галиной и Еленой; Борис, как уже говорилось, с Андреем и еще с Галиной; Виктор – с Галиной, Дмитрием и Еленой; Галина с Андреем и Борисом; Дмитрий – с Виктором и Елена – с Андреем и Виктором. Сколько игр проведено к настоящему моменту и сколько еще осталось?

Обсуждение. Изобразим данные задачи в виде схемы. Участников будем изображать точками: Андрея – точкой А, Бориса – точкой Б и т.д. Если двое участников уже сыграли между собой, то будем соединять изображающие их точки отрезками. Получается схема, показанная на рисунке 1.

Точки А, Б, В, Г, Д, Е - вершины графа, соединяющие их отрезки – ребра графа.

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

Число игр, проведенных к настоящему моменту, равно числу ребер, т.е. 7.

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

Чтобы найти число игр, которые надо провести, построим еще один граф с теми же вершинами, но ребрами будем соединять тех участников, которые еще не играли друг с другом (рис.2) Ребер у этого графа оказалось 8, значит, осталось провести 8 игр: Андрей – с Виктором и Дмитрием; Борис – С Виктором, Дмитрием и Еленой и т.д.

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

Задача. Кто играет Ляпкина – Тяпкина? В школьном драмкружке решили ставить гоголевского «Ревизора». И тут разгорелся жаркий спор. Все началось с Ляпкина – Тяпкина.

Ляпкиным – Тяпкиным буду я! – решительно заявил Гена.

Нет, я буду Ляпкиным – Тяпкиным, возразил Дима.- С раннего детства мечтал воплотить этот образ на сцене.

Ну, хорошо, уступить эту роль, если мне дадут сыграть Хлестакова, - проявил великодушие Гена.

- …А мне – Осипа, - не уступил ему в великодушии Дима.

Хочу быть Земляникой или Городничим,- сказал Вова.

Нет, Городничим буду я, - хором закричали Алик и Боря. – Или Хлестаковым, -

Удастся ли распределить роли так, чтобы исполнители были довольны?

Обсуждение. Изобразим юных актеров кружками верхнего ряда: А – Алик, Б – Борис, В – Вова, Г – Гена, Д – Дима, а роли, которые они собираются играть, - кружками второго ряда (1 – Ляпкин – Тяпкин, 2 – Хлестаков, 3 – Осип, 4 – Земляника, 5 – Городничий). Затем от каждого участника проведем отрезки, т.е. ребра, к ролям, которые он хотел бы сыграть. У нас получиться граф с десятью вершинами и десятью ребрами (рис.3)

Чтобы решить задачу, нужно из десяти выбрать пять ребер, не имеющих общих вершин. Сделать это легко. Достаточно заметить, что в вершины 3 и 4 ведут по одному ребру, из вершин Д и В соответственно. Это означает, что Осипа (вершина 3) должен играть Дима (кто же еще?), а Земляничку – Вова. Вершина1 – Ляпкин – Тяпкин – соединена ребрами с Г и Д. Ребро 1 – Д отдает, так как Дима уже занят, остается 1 – Г, Ляпкина – Тяпкина должен играть Гена. Остается соединить вершины А и Б с вершинами 2 и 5, соответствующими ролям Хлестакова и Городничего. Это можно сделать двумя способами: либо выбрать ребро А -5 и Б – 2, либо ребро А -2 и Б -5. В первом случае Алик будет играть Городничего, а Боря – Хлестакова, во втором случае наоборот. Как показывает граф, других решений задача не имеет.

Тот же граф получится при решении следующей задачи:

Задача. Сварливые соседи. Жители пяти домов поссорились друг с другом и, чтобы не встречаться у колодцев, решили поделить их (колодцы) так, чтобы хозяин каждого дома ходил к «своему» колодцу по «своей» тропинке. Удастся ли им это сделать?

Возникает вопрос: так ли нужны были графы в разобранных задачах? Разве нельзя прийти к решению чисто логическим путем? Да, можно. Но графы придали условиям наглядность, упростили решение и выявили сходство задач, превратив две задачи в одну, а это уже не так уж мало. А теперь представьте себе задачи, графы которых имеют 100 или более вершин. А ведь именно такие задачи приходиться решать современным инженерам и экономистам. Тут без графов не обойтись.

III. Графы Эйлера.

Теория графов – наука сравнительно молодая: во времена Ньютона такой науки еще не существовало, хотя и были в ходу «генеалогические деревья», представ-ляющие собой разновидности графов. Первая работа по теории графов принадлежит Леонарду Эйлеру, и появилась она в 1736 году в публикациях петербургской Академии наук. Начиналась эта работа с рассмотрения следующей задачи:

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

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

Фигура эта, такая простая на вид, оказывается, имеет интересную особенность. Если мы начнем движение из вершины В, то у нас это обязательно получится. А что будет, если мы начнем движение из вершины А? Легко убедиться, что обвести линию в этом случае нам не удается: у нас всегда будет оставаться не пройденные ребра, добраться до которых уже невозможно.

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

Графы, начерченные на рис.6 также можно начертить одним росчерком пера.

Теперь попробуйте вычертить одним росчерком граф, изображенный на рис.7

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

Проведем рассуждения, которые убедят нас в этом. Рассмотрим узел А. Из него выходят три вершины. Начнем вычерчивать граф с этой вершины. Чтобы пройти по каждому из этих ребер, мы должны выйти из вершины А по одному из них, в какой – то момент обязательно вернуться в него по второму и выйти по третьему. А вот снова войти уже не сможем! Значит, если мы начнем вычерчивание с вершины А, то закончить в нем не сможем.

Допустим теперь, что вершина А не является началом. Тогда в процессе вычерчивания мы должны войти в него по одному из ребер, выйти по другому и снова вернуться по третьему. А так как выйти из него мы не сможем, то вершина А в этом случае должен являться концом.

Итак, вершина А должен быть или началом, или конечным узлом вычерчивания.

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

Граф, который можно нарисовать, не отрывая карандаша от бумаги, называется эйлеровым (рис.6).

Такими графы названы в честь учёного Леонарда Эйлера.

Закономерность1. (вытекает из рассмотренной нами теоремы).

Невозможно начертить граф с нечетным числом нечетных вершин.
Закономерность 2.

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

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

Граф, имеющий более двух нечетных вершин, невозможно начертить «одним росчерком».
Фигура (граф), которую можно начертить, не отрывая карандаш от бумаги, называется уникурсальной.

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

Граф называется несвязным , если это условие не выполняется.

рис.7рис.8

На рисунке 7, очевидно, изображен несвязный граф. Если, например, на рисунке между вершинами Д и Е провести ребро, то граф станет связным. (рис.8)

Такое ребро в теории графов (после удаления которого граф из связного превращается в несвязный) называется мостом .

Примерами мостов на рисунке 7 могли бы служить ребра ДЕ, A3, ВЖ и др., каждое из которых соединяло бы вершины «изолированных» частей графа.(рис.8)

Несвязный граф состоит из нескольких «кусков». Эти «куски» называются компонентами связности графа. Каждая компонента связности является, конечно, связным графом. Отметим, что связный граф имеет одну компоненту связности.
ТЕОРЕМА.

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

Доказательство:

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

Вернемся теперь к задаче о кенигсбергских мостах.

Обсуждение задачи . Обозначим различные части города буквами А, В, С, Д, а мосты – буквами а, b, c, d, e, f, g – мосты, соединяющие соответствующие части города. В этой задаче существуют лишь переходы через мосты: переходя через любой мост, мы всегда из одной части города попадаем в другую, И, наоборот, переходя из одной части города в другую, мы непременно пройдем по мосту. Поэтому, изобразим план города в виде графа, вершины которого А, В, С, Д (рис.8) изображают отдельные части города, а ребра a, b, c, d, e, f, g – мосты, соединяющие соответствующие части города. Ребра зачастую оказываются удобнее изображать удобнее не прямолинейными отрезками, а криволинейными – «дугами».

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

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

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

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

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

Это по сути граф. Пять компьютеров являются вершинами, а соединения (пути передачи сигналов) между ними – ребрами. Заменив компьютеры вершинами, мы получим математический объект – граф, который имеет 10 ребер и 5 вершин. Пронумеровать вершины можно произвольным образом, а не обязательно так, как это сделано на рисунке. Стоит отметить, что в данном примере не используется ни одной петли, то есть такого ребра, которое выходит из вершины и сразу же входит в нее, но петли могут встречаться в задачах.

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

G=(V, E), здесь G – граф, V – его вершины, а E – ребра;
|V| – порядок (число вершин);
|E| – размер графа (число рёбер).

В нашем случае (рис. 1) |V|=5, |E|=10;

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

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

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

Ориентированные графы имеют следующую форму записи:

G=(V, A), где V – вершины, A – направленные ребра.

Третий тип графов – смешанные графы (рис. 3). Они имеют как направленные ребра, так и ненаправленные. Формально смешанный граф записывается так: G=(V, E, A), где каждая из букв в скобках обозначает тоже, что ей приписывалось ранее.

В графе на рисунке 3 одни дуги направленные [(e, a), (e, c), (a, b), (c, a), (d, b)], другие – ненаправленные [(e, d), (e, b), (d, c)…].

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

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

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

В любом из рассмотренных нами графов имеется возможность выделить путь и, причем не один. Путь – это последовательность вершин, каждая из которых соединена с последующей посредством ребра. Если первая и последняя вершины совпадают, то такой путь называется циклом. Длина пути определяется количеством составляющих его ребер. Например, на рисунке 4.а путем служит последовательность [(e), (a), (b), (c)]. Этот путь является подграфом, так как к нему применимо определение последнего, а именно: граф G’=(V’, E’) является подграфом графа G=(V, E), только тогда когда V’ и E’ принадлежат V, E.

Начало теории графов все единодушно относят к 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 вершин, то количество ребер будет Совершены все рукопожатия.

Обозначение: 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 классов.

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

(РИСУНОК 1.1)

По поводу обнаруженного им способа решать задачи подобного рода Эйлер писал [см. стр. 102-104]:

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

История с мостами города Кенигсберга имеет современное продолжение. Откроем, например, школьный учебник по математике под редакцией Н.Я. Виленкина для шестого класса. В нем на странице 98 в рубрике развития внимательности и сообразительности мы найдем задачу, имеющую непосредственное отношение к той, которую когда-то решал Эйлер.

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

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

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