Графи и их применение

«Графы и их применение»

Выполнила : ученица 9А класса

Васешенкова Марина.

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

Родич Валентина

Григорьевна.

Содержание презентации:

• Цели проекта.
• Раздел 1. Историческая справка. Возникновение теории графов.
• Раздел 2. Основные понятия и виды графов.
• Раздел 3. Применение теории графов

• в различных областях;
• русский язык;
• литература;
• иностранный язык;
• геометрия;
• алгебра;

• Раздел 4. Заключение.
• Список литературы.

Цели и задачи проекта:

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

«…Я не знаю, каким образом получается, что вопросы, имеющие совсем мало отношения к математике, скорее разрешается математиками, чем другими".

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

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

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

Толчок к развитию теория графов получила на рубеже ХIX и ХХ столетий, когда резко возросло число работ в области топологии и комбинаторики, с которыми ее связывают самые тесные узы родства. Графы стали использоваться при построении схем электрических цепей и молекулярных схем. Как отдельная математическая дисциплина теория графов была впервые представлена в 1936 году в монографии австрийского математика Д.Кинега «Теории конечных и бесконечных графов», к сожалению, не переведённой на русский язык.

«За душу каждого математика борются демон абстрактной алгебры и ангел чистой топологии».

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

• Критерий планарности графа доказали независимо друг от друга академик Российской Академии наук Л.С.Понтрягин в 1927 году и польский математик К.Куратовский в 1930 году .
• Немецкий математик Д.Пойя предложил метод производящих функций, позволяющих решать задачи подсчёта графов, втречающихся в различных областях науки.
• Метод чередующихся цепей, идея которого восходит ещё к Е.Эгевари под названием «венгерского метода», и теперь успешно применяется в некоторых разделах теоретической и прикладной математики.
• 1948 году в «Успехах математических наук» опубликована работа

«О некоторых математических вопросах теории электрических цепей», в которой успешно использованы графы. Автор этой работы ныне член-корреспондент Российской Академии наук Л.Д. Кудрявцев.

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

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

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

Вершины графа, которые не принадлежат ни одному

ребру, называются изолированными.

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

называется нуль-графом.

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

Графы, в которых не построены все

возможные ребра, называются неполными

графами.

Путем в графе от одной вершины к другой

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

которой можно проложить маршрут между этими

вершинами. При этом никакое ребро маршрута не

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

Граф, который можно представить на плоскости

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

в вершинах, называется плоским.

Ребро графа называется ориентированным ребром , если

одну из его вершин считать началом, а другую —

концом этого ребра. Граф, у которого все ребра

ориентированные, называется ориентированным

графом.

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

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

Рассмотрим применение теории графов в некоторых областях

№ 1

Представим себе, что организуется географическая экспедиция на острова Тихого океана. В её состав кроме начальника должны войти 3 географа, повар, радист, врач и техник. Участвовать в экспедиции изъявили желание десять человек, причём каждый владеет одной или несколькими из этих профессий. Всегда ли начальник экспедиции сможет из такой группы набрать нужных ему специалистов?

Нарисуем граф, у которого две группы вершин: десять соответствуют претендентам и семь – должностям. Рёбрами соединим вершины претендентов с вершинами их специальностей (рис.18).

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

№ 2

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

«(Все1 это2) (сильно3 (поколебало4 (мою5 (авторскую6 уверенность7))))»

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

L1= (х1, х2, x3, х4, х5, х6, х7)

L2 = (х1, x2)

L3 = (х3, х4, х5, х6, х7)

L4 = (х3, х4, х5, x6, х7)

L5 = (х5, х6, х7)

L6 = (х6, х7)

Изобразим данное отношение с помощью графов:

Этот граф является

Несимметричным

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

№ 3

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

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

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

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

Деревья Лермонтовской прозы во многом похожи на пушкинские, хотя расчеты показывают, что в среднем предложения Лермонтова чуть-чуть длиннее и чуть-чуть сложнее. Впрочем, есть важное различие в рисунках деревьев, свойственных этим авторам. Ширина ветвления корня дерева для фразы из «Героя нашего времени» гораздо больше, чем для фразы из «Капитанской дочки». Это означает, что дерево лермонтовской фразы растёт вширь, в то время как в пушкинской фразу оно растёт вглубь. Большая ширина ветвления возникает вследствие того, что сказуемые в лермонтовской фразе подчиняют себе не только дополнения, но и разнообразные по структуре и значению обстоятельства.

У Н.В. Гоголя в «Вечерах на хуторе близ Диканьки» в стилистической пестроте фраз встречаются не только короткие предложения. Здесь в большом количестве представлены предложения сложные по структуре. Даже относительно короткие предложения из 6-12 слов строятся у Гоголя весьма разнообразно, в его произведениях можно найти едва ли не любую теоретически возможную из данного числа слов конфигурацию ветвей дерева. Наблюдается своеобразный тип структуры с многократными зигзагами когда, спускаясь вниз по стрелкам, мы постоянно изменяем направление движения.

№ 4

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

Возьмем 73 сонет В. Шекспира и З перевода: В. Бенедиктова, В. Брюсова и Б. Пастернака и сделаем анализ. Для этого начертим графы строк, но сначала познакомимся с произведениями этих авторов.

1. В. Шекспир.

That time of year thou mayst in me be hold

When yellow leaves, or none, or few do hang

Upon those boughs which shake against the cold

In me thou seest the twilight of such day

As after sunset fadeth in the west

Which by and by black night doth take away,

Death’s second self that seals up all the rest.

In my thou seest the glowing of such fire,

That on the ashes of his youth doth lie,

As the death-bed, whereon it must expire,

Consumed with that which it was nourished by.

This thou perciev’st, which makes thy love more strong,

To love that well, which thou must leave ere long.

2. Б. Пастернак.

То время года видишь ты во мне,

Когда из листьев редко, где какой,

Дрожа, желтеет в веток голизне,

А птичий свист везде сменил покой.

Во мне ты видишь бледный край

небес,

Где от заката памятка одна

И, постепенно взявши перевес,

Их отпечатывает темнота.

Во мне ты видишь то сгоранье дна,

Когда зола, что пламенем была,

Становится могилою огня,

А то, что грело, изошло дотла

И, это видя, помни: нет цены

Свиданьям, дни которых сочтены.

4. В. Бенедиктов.

Во мне перед собой ты видишь время снега,

С кустов зеленая одежда их снята,

Певцов пернатых нет, в оркестре пустота.

Поблёклый лист упал, исчезла песен нега -

Во мне перед собой ты видишь час ночлега,

На западе дрожит чуть светлая черта,

И всё густеет мрак, мрак — этот after ego

Тьмы смертной, вечной тьмы, недалека и та.

Во мне перед тобой дней прошлых лишь остаток,

Лишь искры над золой, а пламень прекращен,

Убитый тем, чем жил и чем питался он.

Люби ж меня сильней! Ты видишь: срок мой краток,

Ты потерять меня страшишься — миг лови!

Чем больше этот страх, тем больше дай любви!

3. В. Брюсов.

То время года видишь ты во мне,

Когда, желтея, листья стали редки,

И там, где птицы пели о весне,

Оголены , дрожа от стужи, ветки.

Во мне ты сумерки находишь дня,

Что гаснет после яркого заката;

Ночь тёмная, к покою всех клоня

(Двойник твой Смерть!), его влечет куда-то!

Во мне ты видишь отблески огней,

Лежавших в пепле юности своей;

Они окончат жизнь на том ложе.

Снедаемые тем, что их запекло,

И потому, что день ты любишь строже,

Спеши любить то, что почти прошло!

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

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

А теперь наложим графы текстов перевода на граф оригинала.

После наложения, щёлкните мышью

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

№ 5 Геометрия

Задача

Чтобы измерить на местности расстояние между двумя точками А и В, из которых одна (точка А) недоступна, провешивают направление отрезка АВ (см.рисунок) и на его продолжении отмеряют произвольный отрезок ВЕ. Выбирают на местности точку D, из которой видна точка А и можно пройти к точкам В и Е. Провешивают прямые BDQ и EDF и отмеряют FD= DЕ и DQ= BD . Затем идут по прямой FQ, глядя на точку А, пока не найдут точку Н, которая лежит на прямой AD. Тогда HQ равно искомому расстоянию. Докажите.

FD= DЕ

DQ= BD

∟ FDK=∟EDB

∆ FQD=∆EBD

∟ FQD=∟EBD

∟ DQH=∟DBA

∟ QDH=∟BDA

∆ QDH=∆BDA

АВ= HQ

• Задача.

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

ВВ 1 -биссектриса

∆ АВС - равнобедренный

АА 1 -биссектриса

∟ СВ В 1 =∟АВ В 1

∟ САА 1 =∟ВА А 1

∟ САВ=∟СВА

∟ АВВ 1 =∟ВА А 1

АВ- общая

∆ АВВ 1 =∆ВА А 1

АА 1 = ВВ 1

Задача.

Докажите, что у равных треугольников АВС и А1В1С1 медианы,проведенные из вершин А и А1 равны.

А 1 М 1 - медиана

АМ- медиана

∆ АВС=∆ А 1 В 1 С 1

ВС = В 1 С 1

∟ В =∟ В 1

АВ = А 1 В 1

В 1 М 1 = М 1 С 1

ВМ = СМ

ВМ = В 1 М 1

∆ АВМ=∆ А 1 В 1 М 1

АМ = АМ 1

№ 6

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

Чтобы легче решать задачи надо знать следующий алгоритм:

1.О каком процессе идет речь в задаче?

2.Какие величины характеризуют этот процесс?

3.Каким соотношением связаны эти величины?

4.Сколько различных процессов описывается в задаче?

5.Есть ли связь между элементами?

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

ЗАДАЧА

Автобус шёл 2 ч со скоростью 45 км/ч и 3 ч со скоростью

60 км/ч. Какой путь прошёл автобус за эти 5 часов?

S¹=90 км V¹=45 км/ч t¹=2ч

S²=180 км V²=60 км/ч t²=3 ч

S= VT

S¹ + S² = 90 + 180

Решение:

1)45 x 2 = 90 (км) – прошёл автобус за 2 ч.

2)60 x 3 = 180 (км) – прошёл автобус за 3 ч.

3)90 + 180 = 270 (км) –прошёл автобус

за 5 ч.

Ответ: 270 км.

Задача

Гребец проезжает расстояние 16 км по течению реки на 6 ч скорей, чем против течения. При этом скорость лодки в стоячей воде на 2 км/ч больше, чем скорость течения. Определить скорость лодки в стоячей воде и скорость течения реки.

Vпо.т. = Vсоб. + Vтеч. ; Vпр.т. = Vсоб. - Vтеч. ; S =V · T.

S = 16 км

Vпо.т. = х +2 +х

V пр.т . = х +2 – х

tпр.т. = 16/ 2

tпо.т. = 16/2х + 2

tпр.т. - tпо.т. = 6

Vсоб.= х +2

Vтеч. = х

Составим уравнение:

16 = 4х + 4

4х = 12

х = 3 , значит скорость течения реки 3км/ч.

3 + 2 = 5 ( км/ч) – скорость соб.

Ответ : 3 км/ч; 5 км/ч.

Раздел 4. Заключение

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

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

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

• Берж К. Теория графов и её применение. – М.: 1962
• Басанер Р. И., Саити Т. Конечные графы и сети. - М.: 1971
• Верезина Л.Ю. Графы и их применение. – М.: 1979

• Еженедельное учебно-методическое приложение к газете Первое

сентября, №15. - М.: ОЦ КУДИЦ-ОБРАЗ, 2001

• Крейдлин Г.Е. Математика помогает лингвистике. – М.: 1994
• Липатов Е. П. Теория графов и её применение. – М.: 1986
• Ойстин О. Графы и их применение. – М.: 1965
• Саркисян А.А., Колягин М.Ю. Познакомьтесь с топологией – М.: 1976
• Шрейдер Ю.А. Равенство, сходство, порядок. - М.: 1971
• Энциклопедия для детей – М.: Аванта +, 2001

• Уилсон Р. Введение в теорию графов. – М.: 1977

Об авторе

Васешенкова

Марина