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



Скачать 146.33 Kb.
Дата08.10.2012
Размер146.33 Kb.
ТипИсследовательская работа


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

Октябрьская средняя общеобразовательная школа

Исследовательская работа по математике

по теме

«Теория графов при решении различных

видов задач»

Выполнил:
ученик 7 б класса
Макшун Алексей

Руководитель:

учитель математики
Коршунова Ольга Юрьевна

Мошково 2011 год

Содержание

1.

Введение.




1. 1.

Актуальность выбранной темы.

3

1.2.

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

4

2.

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




2.1.

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

6

2.2.

Эйлеровы пути. Построение фигуры одним росчерком.

9

2.3.

Плоские графы.

14

3.

Заключение.

15

4.

Литература.


16



  1. Введение.

1. 1. Актуальность выбранной темы.

Однажды мне встретилась задача, описанная Льюсом Кэрроллом. «Три человека жили в трех домиках, неподалеку от них находились три колодца: один с водой, другой с маслом, а третий с повидлом, и ходили к ним по тропинкам, изображенным на рисунке. Однажды эти люди перессорились и решили провести тропинки от своих домов к колодцам так, чтобы эти тропинки не пересекались»1.



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

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

  • Изучить элементы теории графов для решения интересующих меня задач.

  • Разобрать решение различных видов задач.

  • Повысить математическую культуру.



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

Датой рождения теории графов принято считать 1736 год, когда Леонард Эйлер решил задачу о кенигсбергских мостах. Рукава реки Прегель, на берегу которой расположен город Кенигсберг, образовывали два острова. В эту эпоху четыре образовавшихся участка суши (правый и левый берег и два острова) соединяло семь мостов так, как это показано на рисунке. Горожане, гуляя по городу, пытались составить маршрут, чтобы он проходил по каждому мосту ровно один раз. Это им не удавалось, а Эйлер доказал, что это принципиально невозможно. Термин «граф» впервые ввел в 1936 году венгерский математик Денеш Кениг. Широкое развитие теория графов получила с 50-х годах 20 века в связи со становлением кибернетики и развитием вычислительной техники.

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

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




Использует графы и дворянство. Например, в генеалогическом дереве, вершины – члены рода, а связывающие их отрезки – отношения родственности.
Генеалогическое дерево А.С. Пушкина.4



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

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

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

В математике определение графа дается так:

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



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

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

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



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

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

На рисунке 5 изображен граф с пятью вершинами. Степень вершины А обозначим Ст.А. На рисунке : Ст.А = 1, Ст.Б = 2, Ст.В = 3, Ст.Г= 2, Ст.Д= 05.

рис.5



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

Решение:

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


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

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

По вечерам Андрей и токарь играют в домино против Сергея и электрика.

Определите профессию каждого из друзей.7
Решение.

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



В С Н А



Ш С Т Э

Задача №3.

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

Петренко и Гришин никогда не держали в руках малярной кисти.

Иванов и Гришин собираются посетить мельницу, на которой работает их товарищ. Петренко и Капустин живут в одном доме с почтальоном.

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

Гришин и Капустин по субботам обязательно встречаются в парикмахерской, где работает их друг. Почтальон предпочитает бриться сам. Кто есть кто?8

Решение.

Иванов Петренко Сидорчук Гришин Капустин





маляр мельник плотник почтальон парикмахер

2.2. Эйлеровы пути. Построение фигуры одним росчерком.

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

Закономерность 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 + К3 + ...):
K1 + 2К2 + ЗК3 + 4К4 + 5К5 + ... + nКn = 2R,
1 + К3 + К5 +...) + (2K2 + 2K3 +4K4 + 4К5 + ...)=2R
Вторая скобка- четное число как сумма четных чисел. Полученная сумма (2R) четное число. Отсюда (К1 + К3 + К5 +...)-четное число.

Что и требовалось доказать.9
Задача №4.

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

Решение .

Невозможно. В таком графе было бы нечетное число вершин нечетной степени.

Заметим, что если полный граф имеет n вершин, то количество ребер будет равно n(n-1)/2.
Действительно, количество ребер в полном графе с n вершинами определяется как число неупорядоченных пар, составленных из всех n точек-ребер графа, т. е. как число сочетаний из n элементов по 2:
Граф, не являющийся полным, можно дополнить до полного с теми же вершинами, добавив недостающие ребра. Так, например, на рисунке 3 изображен неполный граф с пятью вершинами. На рисунке 4 ребра превращающие граф в полный граф изображены другим цветом, совокупность вершин графа с этими ребрами называется дополнением графа.11

Задача №5.

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

Решение:

Построим граф. Сыгранные игры отметим синими линиями, красными дополним до полного графа. Получим, что сыграно 7 игр, а осталось – 8. Можно проверить: в графе 6 вершин тогда всего ребер 6*5/2=15 (7+8).



Эйлеровы графы.

Эйлеров путь - путь в графе, проходящий через каждое ребро ровно один раз.

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

рис.6 (эйлеровы графы)

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

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

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

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

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

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

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

Задача № 7.

Четыре острова соединены между собой и с берегами реки 14 мостами так, как это показано на рисунке. Можно ли за одну прогулку обойти все эти мосты, побывав на каждом из них один раз?

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




Задача №8.

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



Решение:

  1. Можно, т. к. только 2 нечетные вершины.

  2. Нельзя, т. к. 4 нечетные вершины.

Задача №9.

Говорят, что Магомет вместо подписи (он был неграмотен) описывал одним росчерком состоящий из двух рогов луны знак, представленный на рисунке. Возможно ли это?17

Решение. Да, потому что в данном случае мы имеем дело с вершинами четного порядка.
Задача №10. Муха в банке.

Муха забралась в банку из-под сахара. Банка имеет форму куба. Сможет ли муха последовательно обойти все 12 ребер куба, не проходя дважды по одному ребру? Подпрыгивать и перелетать с места на место не разрешается.18

Решение.

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

Задача № 11.

Попробуйте построить данные фигуры одним росчерком.19


2.3. Плоские графы.

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

Эйлер доказал теорему, которая даёт отрицательный ответ на вопрос этой задачи.

Теорема Эйлера.

Если граф, имеющий n вершин и m ребер,- плоский, тогда справедливо равенство n-m+p=2, где p количество непересекающихся частей (их называют гранями), на которые этот граф разбивает плоскость.

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

Граф «три дома и три колодца» имеет шесть вершин и девять рёбер. Если он плоский, количество граней p должно быть равно p = n – m + 2 = 9 - 6 + 2 = 5. Но так как никакие два дома или два колодца не соединены между собой, каждая грань имеет, по меньшей мере, четыре ребра. Получим неравенство 2n ≥ 4p(каждое ребро считается два раза), откуда получаем ложное неравенство 18 ≥ 20. Аналогично доказывается, что полный пятивершинный граф также не может быть плоским.

Теорема Понтрягина – Куратовского.

Граф является плоским тогда и только тогда, когда он не содержит графа с шестью вершинами типа «домики-колодцы» и полного графа с пятью вершинами.20



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


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

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

4. Литература.

1. Альхова З.Н., Макеева А.В. Внеклассная работа по математике. – Саратов: «Лицей», 2002 г.

2. Башмаков М. И. Математика в кармане «Кенгуру». - М.: Дрофа, 2010г.

3. Игнатьев Е. И. Математическая смекалка. - М.: «Омега», 1994г.

4. Подготовка школьников к олимпиадам по математике. 5-6 классы./сост. Григорьева Г.И. – М. : «Глобус», 2009 г.

5. "Математика" - приложение к газете "Первое сентября" №7,2005г

5.Физико-математический журнал «Квант», №6, 1994г.

6. Энциклопедический словарь юного математика / Сост.А.П.Савин.- М.: Педагогика, 1989.

Так же использовались данные со следующих сайтов:

http://www.as-pushkin.ru/index.php?cnt=4

http:goon.ruinfometronovosibirsk_metro_map.htm



1 Энциклопедический словарь юного математика / Сост.А.П.Савин.- М.: Педагогика, 1989.

2 Башмаков М. И. Математика в кармане «Кенгуру». - М.: Дрофа, 2010г.

3 http:goon.ruinfometronovosibirsk_metro_map.htm


5 Физико-математический журнал «Квант», №6, 1994г.

6 Подготовка школьников к олимпиадам по математике. 5-6 классы./сост. Григорьева Г.И. – М. : «Глобус», 2009 г.

7 Альхова З.Н., Макеева А.В. Внеклассная работа по математике. – Саратов: «Лицей», 2002 г.


8 "Математика"- приложение к газете "Первое сентября" №7,2005г

9 Физико-математический журнал «Квант», №6, 1994г.


10 Башмаков М. И. Математика в кармане «Кенгуру». - М.: Дрофа, 2010г.

11Физико-математический журнал «Квант», №6, 1994г.

12 Подготовка школьников к олимпиадам по математике. 5-6 классы./сост. Григорьева Г.И. – М. : «Глобус», 2009 г.


13 Физико-математический журнал «Квант», №6, 1994г.

14 Башмаков М. И. Математика в кармане «Кенгуру». - М.: Дрофа, 2010г.

15 Альхова З.Н., Макеева А.В. Внеклассная работа по математике. – Саратов: «Лицей», 2002 г.

16 Альхова З.Н., Макеева А.В. Внеклассная работа по математике. – Саратов: «Лицей», 2002 г.


17 Игнатьев Е. И. Математическая смекалка. - М.: «Омега», 1994г.

18 Альхова З.Н., Макеева А.В. Внеклассная работа по математике. – Саратов: «Лицей», 2002 г.

19 Подготовка школьников к олимпиадам по математике. 5-6 классы./сост. Григорьева Г.И. – М. : «Глобус», 2009 г.


20 Башмаков М. И. Математика в кармане «Кенгуру». - М.: Дрофа, 2010г.


Похожие:

Исследовательская работа по математике по теме «Теория графов при решении различных видов задач» iconИсследовательская работа в мире графов и лабиринтов. Применение теории графов при решении логических задач
В мире графов и лабиринтов. Применение теории графов при решении логических задач
Исследовательская работа по математике по теме «Теория графов при решении различных видов задач» iconМетодические указания к самостоятельным и семинарским занятиям по теории графов Москва 2006
Предназначены для решения задач по теории графов как при самостоятельном изучении теории графов, так и при решении задач на семинарах...
Исследовательская работа по математике по теме «Теория графов при решении различных видов задач» iconНаучная работа по теме: 1 глава 1 4 теория графов 4 Эйлеровы графы 7 Задача о мостах, Леонард Эйлер и теория графов 8
Как это сделать? Я стала искать пути решения, и оказалось, что это можно сделать с помощью графов. Раньше понятием «граф» я встречалась...
Исследовательская работа по математике по теме «Теория графов при решении различных видов задач» iconПрименение различных инвариантов графов к проверке изоморфизма некоторых видов графов
Мельникова Е. А., Сайфуллина Е. Ф. Применение различных инвариантов графов к проверке изоморфизма некоторых видов графов. // Проблемы...
Исследовательская работа по математике по теме «Теория графов при решении различных видов задач» iconИнтегрированный урок по обж, информатике и икт и математике в 9 классе по теме Безопасность жизнедеятельности при решении задач по математике. «Предмет математики настолько серьезен

Исследовательская работа по математике по теме «Теория графов при решении различных видов задач» iconИсследовательская работа. «Графы» Макаров Дмитрий
Теория графов находит применение в различных областях современной математики и ее многочисленных приложениях, в особенности это относится...
Исследовательская работа по математике по теме «Теория графов при решении различных видов задач» iconУрок по физике и математике в 9-м классе по теме
...
Исследовательская работа по математике по теме «Теория графов при решении различных видов задач» iconТема: Связность графов. Множества сочленения и разделяющие множества
В теории графов, понятие связности графа является ключевым при решении многих прикладных задач
Исследовательская работа по математике по теме «Теория графов при решении различных видов задач» iconРешение задач различных типов по теме Поверхностное натяжение жидкости
Цель урока: закрепление знаний и умений по теме «Поверхностное натяжение жидкости» при самостоятельном решении задач
Исследовательская работа по математике по теме «Теория графов при решении различных видов задач» iconУрок геометрии в 7«в» классе по теме «Медианы, биссектрисы, высоты»
Обобщение ранее изученного материала, систематизация знаний, развитие навыков при решении различных задач
Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org