Добавить материал и получить бесплатное свидетельство о публикации в СМИ
Эл. №ФС77-60625 от 20.01.2015
Инфоурок / Математика / Другие методич. материалы / Исследовательская работа по математике "Графы и их применение"
ВНИМАНИЮ ВСЕХ УЧИТЕЛЕЙ: согласно Федеральному закону № 313-ФЗ все педагоги должны пройти обучение навыкам оказания первой помощи.

Дистанционный курс "Оказание первой помощи детям и взрослым" от проекта "Инфоурок" даёт Вам возможность привести свои знания в соответствие с требованиями закона и получить удостоверение о повышении квалификации установленного образца (180 часов). Начало обучения новой группы: 24 мая.

Подать заявку на курс
  • Математика

Исследовательская работа по математике "Графы и их применение"

Выберите документ из архива для просмотра:

Выбранный для просмотра документ выступление.doc

библиотека
материалов

Слайд 1

Тема моей работы «Графы и их применение»


Слайд 2

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


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


Передо мной встал вопрос: Можно ли решить эти задачи не перебором, а другим, более быстрым, способом?

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

Слайд 3


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


Я поставил перед собой такие задачи:

  • Изучить элементы теории графов.

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

  • Узнать о применении графов в науке и в различных сферах.



Методы исследования, которые я использовал:

  • Поиск и анализ информации в литературе и интернет – ресурсах.

  • Моделирование.


Слайд 4

Термин "граф" впервые появился в книге венгерского математика Денеша Кёнига в 1936 г., хотя начальные важнейшие теоремы о графах восходят к Леонарду Эйлеру. Математические графы с дворянским титулом «граф» связывает общее происхождение от латинского слова « графио » - пишу.


Слайд 5


Основы теории графов как математической науки заложил в 1736 г. Леонард Эйлер, рассматривая задачу о кенигсбергских мостах. Сегодня эта задача стала классической.


Слайд 6

Город Кенигсберг (после мировой войны он называется Калининград) стоит на реке Прегель. Некогда там было 7 мостов, которые связывали между собой берега и два острова. Жители города заметили, что они никак не могут совершить прогулку по всем семи мостам, пройдя по каждому из них ровно один раз. Так возникла головоломка: “можно ли пройти все семь кенигсбергских мостов ровно один раз и вернуться в исходное место?”.
Выстроив алгоритм, Эйлер получил отрицательный ответ в задаче о мостах.


Слайд 7

Для решения задачи о мостах Эйлер ввёл следующие определения:

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

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


Слайд 8

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


Слайд 9

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

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


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


Слайд 10


Благодаря Леонарду Эйлеру существует общий прием решения подобных задач:

  1. преобразовать рисунок в граф (определить его вершины и рёбра);

  2. определить степень каждой вершины;

  3. посчитать количество нечётных вершин;

  4. сделать выводы:

а) заданный обход возможен, если

- все вершины чётные (его можно начать

с любой вершины);

- две вершины нечётные (его нужно начать с одной

из нечётных вершин);

б) заданный обход невозможен, если нечётных вершин

больше двух;

  1. указать начало и конец пути.


Слайд 11

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

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

Слайд 12


В открытом конверте степени трёх вершин чётные, а двух вершин – нечётные, значит вычерчивание одним росчерком возможно.

Начало вычерчивания – в одной из нечётных вершин, конец – в другой нечётной вершине.


Слайд 13

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

  • Да, потому что в данном случае мы имеем дело с вершинами четного порядка.


Слайд 14

Следующая задача на вычерчивание одним росчерком «Муха в банке».

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


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


Слайд 15

А вот и решение с использованием закономерностей Эйлера задачи дистанционной олимпиады:

  • Нечётных вершин в условии задачи две – почта и дом, поэтому начинаться и заканчиваться маршрут должен в них. Почтальон Печкин начинает разносить письма с почты, значит, закончит в доме №5, там и живет дядя Федор.

  • Например, маршрут может быть таким: почта – 1 – 3 – 2 – 1 – 7 – почта – 3 – 4 – 5 – 7 – 6 – 5 .


Слайд 16

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


Слайд 17

Полученные выводы помогают решать задачи с лабиринтами. Лабиринт - это граф. А исследовать его - это найти путь в этом графе.


Слайд 18

Вот пример задачи с лабиринтами. Можно ли обойти все данные комнаты, пройдя через каждую дверь ровно один раз и выйти на улицу через комнату 1 или 10? С какой комнаты надо начинать?


Слайд 19

Пусть комнаты – вершины графа, а двери – ребра. Проверим степени вершин:

Только две вершины имеют нечетную степень. Начать движение можно из комнаты 10, а закончить в комнате 8, либо наоборот.


Слайд 20

Но, чтобы выйти на улицу (из комнаты 10), надо начинать из комнаты 8. В этом случае пройдём все двери один раз и попадём в комнату 10, но окажемся внутри комнаты, а не снаружи:


Слайд 21

Можно при помощи теории графов решать и логические задачи.

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

Решение:

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

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

Слайд 22

В деревне 10 домов, и из каждого выходит по 7 тропинок, идущих к другим домам. Сколько всего тропинок приходит между домами?


Пусть дома- вершины графа, тропинки- рёбра. По условию из каждого дома (вершины) выходит 7 тропинок (рёбер), тогда степень каждой вершины 7, сумма степеней вершин 7×10=70, а число рёбер 70 : 2= 35. Таким образом, между домами проходит 35 тропинок.

Ответ. 35 тропинок


Слайд 23

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


Инженер чертит схемы электрических цепей.

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

Историк прослеживает родословные связи по генеалогическому дереву.

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

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

Слайд 24

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

Одна из них – специалист по логистике.

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



Слайд 25

Графом является и система улиц города. Его вершины – площади и перекрестки, а ребра – улицы.

Слайд 26

Графы используют филологи

Слайд 27

Схема линий московского метрополитена тоже представляет собой граф


Слайд 28

Графы есть и на картах звездного неба.

Слайд 29

Графами являются блок – схемы программ для ЭВМ.

Слайд 30

Применяются графы и в химии


Слайд 31

Я в виде графа с использованием программы ????? создал свое генеологическое древо.

Слайд 32


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

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

Выбранный для просмотра документ реферат.doc

библиотека
материалов

Содержание:

I. Введение……………………………………………………………………2

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

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

2.Основные понятия теории графов…………………………………………..5

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

3.1 Задачи о вычерчивании фигур одним росчерком………………………..8

3.2 Задачи с лабиринтами……………………………………………………..10

3.3 Логические задачи…………………………………………………………12

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

4.1.Графы и история……………………………………………………………17

4.2.Графы и химия……………………………………………………………...18

4.3. Графы и физика…………………………………………………………….19

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

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

Приложение 1………………………………………………………………….22

Приложение 2………………………………………………………………….25

Приложение 3…………………………………………………………………..26



I Введение



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

hello_html_1490c461.png

В этом году я был участником дистанционной олимпиады по математике. В ней была предложена такая задача:

«Почтальон Печкин разнёс почту во все дома деревни, после чего зашёл к дяде Фёдору выпить молока. На рисунке показаны все тропинки, которые проходил Печкин, причём как оказалось, ни одной из них он не проходил дважды. Каким маршрутом шёл почтальон Печкин? В каком доме живёт дядя Фёдор?»

hello_html_4e0bcc2b.gifhello_html_591dee0e.gifhello_html_m28bd15c1.gifhello_html_m27a6a3d6.gifhello_html_m4e4e91e9.gif

hello_html_m5d7c9c44.gifhello_html_189f3ce7.gifhello_html_31dbf1da.gifhello_html_m1f188561.gifhello_html_m4035accc.gifhello_html_2e12319b.gifhello_html_24acf7e4.gifhello_html_m4f9a737d.gifhello_html_m4dd3bc2d.gifhello_html_m6f5c7173.gifhello_html_m21f5ccea.gifhello_html_m744034a9.gifhello_html_7f39e27e.gifhello_html_2e520590.gifhello_html_m1112e5b.gif









Разбирая решение этой задачи, я задался вопросом: «Можно ли решить эти задачи не перебором, а другим, более быстрым, способом?»

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


Цель:


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





Задачи:


  • Изучить элементы теории графов.

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

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





Методы исследования:


  1. Поиск и анализ информации в литературе.

  2. Поиск и изучение информации в интернет – ресурсах.

  3. Моделирование.




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

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

Датой рождения теории графов принято считать 1736 год, когда Леонард Эйлер решил задачу о кенигсбергских мостах (Приложение 1.).

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

Термин «граф» впервые ввел в 1936 году венгерский математик Денеш Кениг. Широкое развитие теория графов получила в 50-х годах 20 века в связи со становлением кибернетики и развитием вычислительной техники.

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

hello_html_m74024acd.jpg

2. Основные понятия теории графов.

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

hello_html_1c75f74.png

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

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

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

hello_html_m3fa4a395.pnghello_html_mfd2f9a.pnghello_html_m764ceece.png

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

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

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

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

hello_html_m3a26bd61.png


рис.5



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

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

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

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

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

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

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

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

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

Алгоритм решения

Из предыдущих рассуждений мы получаем общий прием решения каждой подобной задачи о мостах:

  1. преобразовать рисунок в граф (определить его вершины и рёбра);

  2. определить степень каждой вершины;

  3. посчитать количество нечётных вершин;

  4. сделать выводы:

а) заданный обход возможен, если

- все вершины чётные (его можно начать с любой вершины);

- две вершины нечётные (его нужно начать с одной из нечётных вершин);

б) заданный обход невозможен, если нечётных вершин больше двух;

  1. указать начало и конец пути.

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

3.1. Решение задач о вычерчивании фигур одним росчерком

Задача №1 (О кенигсбергских мостах).

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

Решение.

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


Задача №2.

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

Рhello_html_5ef8c44d.pngешение:

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

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


Зhello_html_733d21ab.jpgадача №3.

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

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

hello_html_m3863bb9b.png

Задача №4. (Муха в банке).

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

Решение.

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

Задача №5. (Путь Печкина)



hello_html_4e0bcc2b.gifhello_html_7c43585d.gif

hello_html_m5d7c9c44.gifhello_html_189f3ce7.gifhello_html_31dbf1da.gifhello_html_m1f188561.gifhello_html_2e12319b.gifhello_html_24acf7e4.gifhello_html_m4f9a737d.gifhello_html_m4dd3bc2d.gifhello_html_m6f5c7173.gifhello_html_m21f5ccea.gifhello_html_m744034a9.gifhello_html_7f39e27e.gifhello_html_2e520590.gifhello_html_m1112e5b.gif

hello_html_m4035accc.gif









Решение. Нечётных вершин в условии задачи две – почта и дом, поэтому начинаться и заканчиваться маршрут может только в этих узлах. Почтальон Печкин начинает разнос писем с почты, поэтому его маршрут может заканчиваться в доме 5, там и живёт дядя Фёдор. Например, маршрут может быть таким: почта-1-3-2-1-7-почта-3-4-5-7-6-5.


    1. Задачи с лабиринтами



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

Происхождение задач о лабиринтах относится к глубокой древности и теряется во мраке времен. Слово «лабиринт» (греческое) означает «ходы в подземельях». Решению задачи о лабиринтах предпосылаются исторические справки – чтобы показать интерес к этой задаче и дать наглядное представление о существовавших и существующих лабиринтах.

Задача о прохождении лабиринта приобретает практический интерес, поскольку устройство линий электропередач, канализации, сетей дорог, каналов и т.д. – все это более или менее сложные лабиринты. Начало решению вопроса о существовании безвыходных лабиринтов положено Эйлером.

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

Решение (т.е. маршрут, ведущий к цели) каждого лабиринта может быть найдено одним их трех сравнительно простых методов.

  • Первый метод – МЕТОД ПРОБ И ОШИБОК. Выбирайте любой путь, а если он заведет вас в тупик, то возвращайтесь назад и начинайте все сначала.

  • Второй метод – МЕТОД ЗАЧЕРКИВАНИЯ ТУПИКОВ. Начнем последовательно зачеркивать тупики, т.е. маршруты, не имеющие ответвлений и заканчивающиеся перегородкой. Незачеркнутая часть коридоров будет выходом или маршрутом от входа к выходу или к центру.

  • Третий метод – ПРАВИЛО ОДНОЙ РУКИ. Оно состоит в том, что по лабиринту надо двигаться, не отрывая одной руки (правой или левой) от стены.

Рассмотрим задачу общего вида:



Мhello_html_4b21ebc2.pngожно ли обойти все данные комнаты, пройдя через каждую дверь ровно один раз и выйти на улицу через комнату 1 или 10? С какой комнаты надо начинать?

Решение:

  1. Пhello_html_6450c857.pngусть комнаты – вершины графа, а двери – ребра. Проверим степени вершин:

  2. Только две вершины имеют нечетную степень. Начать движение можно из комнаты 10, а закончить в комнате 8, либо наоборот.

  3. Но, чтобы выйти на улицу (из комнаты 10), надо начинать из комнаты 8. В этом случае пройдём все двери один раз и попадём в комнату 10, но окажемся внутри комнаты, а не снаружи:

hello_html_m60e1062f.png


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

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

Задача №1.

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

Решение:

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

hello_html_m22fcad94.png

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

Задача №2.

Вhello_html_m2754390.jpg деревне 10 домов, и из каждого выходит по 7 тропинок, идущих к другим домам. Сколько всего тропинок приходит между домами?

Решение.

Пусть дома- вершины графа, тропинки- рёбра. По условию из каждого дома (вершины) выходит 7 тропинок (рёбер), тогда степень каждой вершины 7, сумма степеней вершин 7×10=70, а число рёбер 70 : 2= 35. Таким образом, между домами проходит 35 тропинок.

Ответ. 35 тропинок

Задача №3.

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

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

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

Решение.

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


hello_html_6e43a72c.gifhello_html_6e43a72c.gifhello_html_6e43a72c.gifhello_html_6e43a72c.gifhello_html_m3e0d8925.gifhello_html_m3e0d8925.gifhello_html_m3e0d8925.gifhello_html_m3e0d8925.gif

В С Н А

hello_html_2f9bf058.gifhello_html_4246b925.gifhello_html_m307c62f5.gifhello_html_m4f9660ec.gifhello_html_m2b6a7346.gifhello_html_2fad35f.gifhello_html_m4e638a45.gifhello_html_m3b6dcedb.gifhello_html_m74da6b5.gifhello_html_2b79d5a4.gifhello_html_m1aa87058.gifhello_html_m2daddef0.gifhello_html_2812cb8f.gifhello_html_328dbec9.gif







Ш С Т Э



Задача №4.

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

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

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

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

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


Решение.

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

hello_html_1058a213.gifhello_html_1058a213.gifhello_html_1058a213.gifhello_html_1058a213.gifhello_html_1058a213.gifhello_html_m53a42c53.gifhello_html_351bccd7.gifhello_html_m3e5dc433.gifhello_html_m64d5822f.gifhello_html_276be545.gifhello_html_2b4d1db5.gifhello_html_m27d896ee.gifhello_html_54a1eb0.gifhello_html_13cc36a0.gifhello_html_41e56783.gifhello_html_1c6a2817.gifhello_html_251dcd68.gifhello_html_m7fa166ed.gifhello_html_11b4aa24.gifhello_html_m496cd4d3.gifhello_html_4596f959.gifhello_html_m7e0480d8.gifhello_html_4f2315ca.gifhello_html_a58976e.gif





hello_html_177a290b.gifhello_html_177a290b.gifhello_html_177a290b.gifhello_html_177a290b.gifhello_html_177a290b.gif

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

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

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

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

hello_html_33028d5c.png











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

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

Инженер чертит схемы электрических цепей.

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

Историк прослеживает родословные связи по генеалогическому дереву.

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

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

Графы применяются в различных отраслях науки. В последние десятилетия теория графов находит все новые области применения (физика, химия, генетика, психология, социология, экономика, лингвистика, электроника, теория планирования и управления). Именно запросы практики способствуют интенсивному развитию теории графов.

4.1.Графы и история.

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

Генеалогическое дерево А.С. Пушкина.

hello_html_7229c52d.jpg

Моё генеалогическое дерево

hello_html_618fcf4a.png

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

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

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

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

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

Мhello_html_m45467518.pngолекулярные графы и деревья: а, б - мультиграфы этилена и формальдегида; в-молекулы изомеров пентана.





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

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





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

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

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

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







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

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

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

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





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

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

2. Перельман Я.И. Одним росчерком. – Ленинград, 1940

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

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

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



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

Леонард Эйлер и мосты Кёнигсберга

Лhello_html_m39f52a00.jpgеонард Эйлер родился в швейцарском городе Базеле, где в 15 лет окончил университет, а в 17 лет получил степень магистра. Во время обучения в университете Эйлер брал уроки у одного из самых известных математиков того времени Иоганна Бернулли и подружился с его сыновьями Даниилом и Николаем, которые были приглашены для работы в только что созданную Петербургскую академию наук. Через год по их рекомендации туда же был приглашен и двадцатилетний Эйлер. Этот выбор оказался одним из самых удачных для России. Нет такой области математики, где Эйлер не сказал своего слова. Работал он сутками напролет в любой обстановке, опубликовал примерно 850 работ. Он легко обнаруживал новые задачи и методы их решения. Даже историю возникновения теории графов можно проследить по переписке великого ученого.

Вот перевод латинского текста, который взят из письма Эйлера к итальянскому математику и инженеру Маринони, отправленного из Петербурга 13 марта 1736 года:

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

В своём письме к Маринони Эйлер подробно описал ход своих рассуждений:

"Кенигсбергские же мосты расположены так, что их можно представить на рисунке, где A обозначает остров, а B, C и D – части континента, отделенные друг от друга рукавами реки. Семь мостов обозначены буквами a, b, c, d, e, f, g ".

hello_html_m14c1a0c5.png

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

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

Поэтому, чтобы найти ответ, продолжим письмо Эйлера и посмотрим, какое же правило он нашел. Итак,

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

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

hello_html_33b31549.png

"Далее нужно различать, является ли число мостов, ведущих к этим отдельным участкам, четным или нечетным. Так, в нашем случае к участку A ведут пять мостов, а к остальным – по три моста".

То есть нам нужно определить степень каждой вершины (количество рёбер, сходящихся в вершине) и узнать, какие вершины четные, а какие нечетные. Подпишем степени вершин в кружочках. И посчитаем количество нечетных вершин. Нечетные вершины: А, B, C, D.

hello_html_m2fc52781.png

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

Приложение 2

Разные задачи на вычерчивание одним росчерком

hello_html_m6e077f4.jpg



hello_html_209e4555.png

hello_html_54121b90.png







hello_html_3fb0b104.jpg











hello_html_2cc39d6c.jpg









Приложение 3

Профессия логист

Оhello_html_m7bce192e.pngписание профессии:

Это специалист, который координирует движение товаров на пути от производства до точек реализации.

Название профессии происходит от английского слова logistics - снабжение, материально-техническое обеспечение.

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

Цепочка может выглядеть, например, так: закупка товаров у иностранного поставщика - их страхование - перевозка - растаможивание (прохождение таможенного контроля, уплата пошлин) - складирование - упаковка и/или снабжение русскоязычными этикетками и документацией - распределение по оптовым торговым базам - продажа в розничной сети.

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

Например, завезли слишком много какого-то товара - он попусту загромождает складские помещения и может прийти в негодность. А какой-нибудь другой товар, который следует привезти к вполне определенному сроку (например, елки к Новому году или цветы к 8 Марта), из-за неправильно оформленных сопроводительных документов застрянет на таможенном складе и поступит в продажу слишком поздно, когда уже окажется никому не нужен.

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

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















27



Выбранный для просмотра документ теория графов.pptx

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

Описание презентации по отдельным слайдам:

№ слайда 1 Применение графов Теория графов сейчас одна из самых развиваемых частей матем
Описание слайда:

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

№ слайда 2 Применение графов При графическом изображении формул веществ указывается посл
Описание слайда:

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

№ слайда 3 Цель: показать применение теории графов для решения различных видов задач. За
Описание слайда:

Цель: показать применение теории графов для решения различных видов задач. Задачи: Изучить элементы теории графов. Разобрать решение различных видов задач. Узнать о применении графов в науке и в различных сферах деятельности. Методы исследования: Поиск и анализ информации в литературе. Поиск и изучение информации в интернет – ресурсах. Моделирование.

№ слайда 4 История возникновения графов Термин "граф" впервые появился в книге венгерско
Описание слайда:

История возникновения графов Термин "граф" впервые появился в книге венгерского математика Д. Кенига в 1936 г., хотя начальные важнейшие теоремы о графах восходят к Л. Эйлеру. Математические графы с дворянским титулом «граф» связывает общее происхождение от латинского слова « графио » - пишу.

№ слайда 5 История возникновения графов Основы теории графов как математической науки за
Описание слайда:

История возникновения графов Основы теории графов как математической науки заложил в 1736 г. Леонард Эйлер, рассматривая задачу о кенигсбергских мостах. Сегодня эта задача стала классической. Задаче о кёнигсбергских мостах Эйлер посвятил целое исследование. содержание

№ слайда 6 Задача о Кенигсбергских мостах Город Кенигсберг (после мировой войны он назыв
Описание слайда:

Задача о Кенигсбергских мостах Город Кенигсберг (после мировой войны он называется Калининград) стоит на реке Прегель. Некогда там было 7 мостов, которые связывали между собой берега и два острова. Жители города заметили, что они никак не могут совершить прогулку по всем семи мостам, пройдя по каждому из них ровно один раз. Так возникла головоломка: “можно ли пройти все семь кенигсбергских мостов ровно один раз и вернуться в исходное место?”. Выстроив алгоритм, Эйлер получил отрицательный ответ в задаче о мостах.

№ слайда 7 Что такое граф Для решения задачи о мостах Эйлер ввёл следующие определения:
Описание слайда:

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

№ слайда 8 Что такое граф Количество рёбер, выходящих из вершины графа, называется степе
Описание слайда:

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

№ слайда 9 Одним росчерком В ходе рассуждений Эйлер пришёл к следующим выводам: не может
Описание слайда:

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

№ слайда 10 Одним росчерком Благодаря Леонарду Эйлеру существует общий прием решения под
Описание слайда:

Одним росчерком Благодаря Леонарду Эйлеру существует общий прием решения подобных задач: преобразовать рисунок в граф (определить его вершины и рёбра); определить степень каждой вершины; посчитать количество нечётных вершин; сделать выводы: а) заданный обход возможен, если - все вершины чётные (его можно начать с любой вершины); - две вершины нечётные (его нужно начать с одной из нечётных вершин); б) заданный обход невозможен, если нечётных вершин больше двух; указать начало и конец пути.

№ слайда 11 Одним росчерком Граф мостов Кёнигсберга имел четыре нечётные вершины, следов
Описание слайда:

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

№ слайда 12 Одним росчерком 3 3 2 4 4 Степени трёх вершин чётные, а двух вершин – нечётны
Описание слайда:

Одним росчерком 3 3 2 4 4 Степени трёх вершин чётные, а двух вершин – нечётные, значит вычерчивание одним росчерком возможно. Начало вычерчивания – в одной из нечётных вершин, конец – в другой нечётной вершине

№ слайда 13 Одним росчерком Говорят, что Магомет вместо подписи (он был неграмотен) описы
Описание слайда:

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

№ слайда 14 Одним росчерком Муха в банке. Муха забралась в банку из-под сахара. Банка име
Описание слайда:

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

№ слайда 15 Одним росчерком 3 5 7 1 2 6 почта Нечётных вершин в условии задачи две – почт
Описание слайда:

Одним росчерком 3 5 7 1 2 6 почта Нечётных вершин в условии задачи две – почта и дом, поэтому начинаться и заканчиваться маршрут должен в них. Почтальон Печкин начинает разносить письма с почты, значит, закончит в доме №5, там и живет дядя Федор. Например, маршрут может быть таким: почта – 1 – 3 – 2 – 1 – 7 – почта – 3 – 4 – 5 – 7 – 6 – 5 . 4

№ слайда 16  Хотите попробовать?
Описание слайда:

Хотите попробовать?

№ слайда 17 Задачи с лабиринтом Лабиринт - это граф. А исследовать его - это найти путь
Описание слайда:

Задачи с лабиринтом Лабиринт - это граф. А исследовать его - это найти путь в этом графе. дальше

№ слайда 18 Задачи с лабиринтом Можно ли обойти все данные комнаты, пройдя через каждую
Описание слайда:

Задачи с лабиринтом Можно ли обойти все данные комнаты, пройдя через каждую дверь ровно один раз и выйти на улицу через комнату 1 или 10? С какой комнаты надо начинать?

№ слайда 19 Пусть комнаты – вершины графа, а двери – ребра. Проверим степени вершин: Реш
Описание слайда:

Пусть комнаты – вершины графа, а двери – ребра. Проверим степени вершин: Решение: Только две вершины имеют нечетную степень. Начать движение можно из комнаты 10, а закончить в комнате 8, либо наоборот.

№ слайда 20 Но, чтобы выйти на улицу (из комнаты 10), надо начинать из комнаты 8. В этом
Описание слайда:

Но, чтобы выйти на улицу (из комнаты 10), надо начинать из комнаты 8. В этом случае пройдём все двери один раз и попадём в комнату 10, но окажемся внутри комнаты, а не снаружи: Решение:

№ слайда 21 Логические задачи Аркадий, Борис. Владимир, Григорий и Дмитрий при встрече о
Описание слайда:

Логические задачи Аркадий, Борис. Владимир, Григорий и Дмитрий при встрече обменялись рукопожатиями (каждый пожал руку каждому по одному разу). Сколько всего рукопожатий было сделано? Решение: Пусть каждому из пяти молодых людей соответствует определенная точка на плоскости, названная первой буквой его имени, а производимому рукопожатию — отрезок или часть кривой, соединяющая конкретные точки — имена. Если подсчитать число ребер графа, изображенного на рисунке, или по формуле n(n-1)/2, это число и будет равно количеству совершенных рукопожатий между пятью молодыми людьми. Их 10.

№ слайда 22 Логические задачи В деревне 10 домов, и из каждого выходит по 7 тропинок, иду
Описание слайда:

Логические задачи В деревне 10 домов, и из каждого выходит по 7 тропинок, идущих к другим домам. Сколько всего тропинок приходит между домами? Решение. Пусть дома- вершины графа, тропинки- рёбра. По условию из каждого дома (вершины) выходит 7 тропинок (рёбер), тогда степень каждой вершины 7, сумма степеней вершин 7×10=70, а число рёбер 70 : 2= 35. Таким образом, между домами проходит 35 тропинок. Ответ. 35 тропинок

№ слайда 23 Применение графов Инженер чертит схемы электрических цепей. Химик рисует стру
Описание слайда:

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

№ слайда 24 Графом является и система улиц города. Его вершины – площади и перекрестки, а
Описание слайда:

Графом является и система улиц города. Его вершины – площади и перекрестки, а ребра – улицы. дальше Применение графов

№ слайда 25 Граф метаграмм Графы используют филологи
Описание слайда:

Граф метаграмм Графы используют филологи

№ слайда 26  Схема линий москов-ского метропо-литена
Описание слайда:

Схема линий москов-ского метропо-литена

№ слайда 27 Применение графов Графы есть и на картах звездного неба.
Описание слайда:

Применение графов Графы есть и на картах звездного неба.

№ слайда 28 Применение графов Графами являются блок – схемы программ для ЭВМ. дальше
Описание слайда:

Применение графов Графами являются блок – схемы программ для ЭВМ. дальше

№ слайда 29 История и графы
Описание слайда:

История и графы

№ слайда 30 Заключение Изучая этот материал, я узнал области применения теории графов и
Описание слайда:

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

№ слайда 31
Описание слайда:

№ слайда 32
Описание слайда:

Краткое описание документа:

Исследовательская работа по математике выполнена учеником 6 класса Кирилловым Даниилом. 

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

Задачи:

·Изучить элементы теории графов.

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

 

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

В реферате освещены основные моменты истории и понятия теории графов, приведены примеры известных задач.

В последние десятилетия теория графов находит все новые области применения (физика, химия, генетика, психология, социология, экономика, лингвистика, электроника, теория планирования и управления). Именно запросы практики способствуют интенсивному развитию теории графов.

 

Автор
Дата добавления 14.01.2015
Раздел Математика
Подраздел Другие методич. материалы
Просмотров3577
Номер материала 300803
Получить свидетельство о публикации

Выберите специальность, которую Вы хотите получить:

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

ПЕРЕЙТИ В КАТАЛОГ КУРСОВ

Похожие материалы

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