Содержание:

1. Введение

2. Цели и задачи

3. Актуальность и новизна

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

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

   1. 4.2 Понятие о графах

   2. 4.3 Свойства графов

   3. 4.4 Использование графов в повседневной жизни

   4. 4.5 Эссе

4.6 Теория графов и анализ художественного текста

4.7 Виды графов

4.8 Признаки И. Л. Севбо

4.9 Графы и стилистика переводов иностранных текстов

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

6. Библиографический список

7. Тезисы

8. Приложения

Введение:

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

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

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

В социальном опросе мы выяснили, что учащиеся начальных классов теорию графов знают намного лучше, чем ученики старших классов, так как в современную программу начальных классов включена теория графов. ( Приложения, рис.15, 16)

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

Данные наработки мы использовали на занятиях факультативного курса.

Цели и задачи:

• Познакомиться с понятием "граф”, с его основными элементами: вершина, ребра.

• Научиться составлять графы по словесному описанию отношений между предметами и существами.

• Научиться читать графы: определять отношения между предметами и существами.

• Развить логическое и образное мышление, воображение.

• Проиллюстрировать применение математики на практике.

• Показать связь с другими областями знаний.

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

• Исследовать роль графов в нашей жизни.

• Научиться решать задачи при помощи графов.

Актуальность и новизна:

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

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

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

Гипотеза:

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

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

«В математике следует помнить не

формулы, а процесс мышления»

Е. И. Игнатьева

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

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

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

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

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

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

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

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

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

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

Так, в нашем случае к участку A ведут пять мостов, а к остальным

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

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

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

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

Понятие о графах

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

Математические графы с дворянским титулом «граф» связывает общее происхождение от латинского слова « графио » - пишу. Типичными графами являются схемы авиалиний, которые часто вывешивается в аэропортах, схемы метро, а на географических картах – изображение железных дорог (Приложения, рис. 1). Выбранные точки графа называются его вершинами, а соединяющие их линии – ребрами.  

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

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

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

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

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

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

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

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

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

Около вершин графа указаны числа – продолжительность в днях соответствующей работы. Теперь мы можем узнать наименьшую возможную продолжительность строительства. Для этого из всех путей по графу в направлении стрелок нужно выбрать путь, у которого сумма чисел при вершинах наибольшая. Он называется критическим путем (на рис. 2 он выделен коричневым цветом). В нашем случае получаем 170 дней. А если сократить время прокладки электросети с 40 до 10 дней, то и время строительства тоже сократится на 30 дней? Нет, в этом случае критический путь станет проходить не через эту вершину, а через вершины, соответствующие строительству котлована, укладке фундамента и т. д. И общее время строительства составит 160 дней, т. е. срок сократиться лишь на 10 дней.

На рис.8 изображена схема дорог между селами М, А, Б, В, Г. (Приложения, рис.8)

Здесь каждые две вершины соединены между собой ребром. Такой граф называется полным. Числа на рисунке указывают расстояния между селами по этим дорогам. Пусть в селе М находится почта и почтальон должен развезти письма по остальным четырем селам. Существует много различных маршрутов поездки. Как из них выбрать наикратчайший? Проще всего проанализировать все варианты. Сделать это поможет новый граф(внизу), на котором легко увидеть возможные маршруты. Вершина М вверху – начало маршрутов. Из нее можно начать движение четырьмя различными способами: в А, в Б, в В, в Г. После посещения одного из сел остается три возможности продолжения маршрута, потом две, потом дорога в последнее село и вновь в М. Всего 4 3 2 1 = 24 способа.

Расставим вдоль ребер графа цифры, обозначающие расстояния между селами, а в конце каждого маршрута напишем сумму этих расстояний по маршруту. Из полученных 24 чисел наименьшими являются два числа по 28км, соответствующие маршрутам М-В-Б-А-Г-М и М-Г-А-Б-В-М. Это один и тот же путь, но пройденный в разных направлениях . Заметим, что граф на рис. 8 тоже можно сделать направленным, указав направление сверху вниз на каждом из ребер, что соответствовало бы направлению движения почтальона. Подобные задачи часто возникают при нахождении лучших вариантов развозки товаров по магазинам, стройматериалов по стройкам.

Графы часто используют для решения логических проблем, связанных с перебором вариантов. Для примера рассмотрим такую задачу. В ведре 8 л воды, и имеется две кастрюли емкостью 5 и 3 л. требуется отлить в пятилитровую кастрюлю 4 л воды и оставить в ведре 4 л, т. е. разлить воду поровну в ведро и большую кастрюлю.

Ситуацию в каждый момент можно описать тремя числами, где А-количество литров воды в ведре, Б- в большой кастрюле, В - в меньшей. В начальный момент ситуация описывалась тройкой чисел ( 8, 0, 0), от нее мы можем перейти в одну из двух ситуаций: ( 3, 5, 0),если наполним водой большую кастрюлю, или ( 5, 0, 3), если наполним меньшую кастрюлю.

В результате получаем два решения: одно в 7 ходов, другое в 8 ходов.

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

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

Свойства графов:

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

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

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

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

Решая задачу про Кенигсбергские мосты, Эйлер установил, в частности, следующие три СВОЙСТВА графа:

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

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

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

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

Кроме трех свойств графа, которые установил Эйлер, решая задачу про Кенигсбергские мосты, он вывел еще два СВОЙСТВА:

4) Число нечетных вершин графа всегда четно.

5) Если в графе имеются нечетные вершины, то наименьшее число росчерков, которыми можно нарисовать граф, равно половине числа нечетных вершин этого графа.

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

Использование графов в повседневной жизни:

• Строительство железных дорог, мостов, дорог. (Приложения, рис.9)

• Построение географических карт

• Блок – схемы ЭВМ( Приложения, рис.10)

• Сетевые графики строительства ( Приложения, рис. 7)

• Схемы движения городского транспорта (Приложение, рис.11)

• Схемы авиалиний (Приложения, рис.12)

• Карты звёздного неба (Приложения, рис. 13)

• Составление генеалогического древа (Приложения, рис. 14)

Эссе:

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

Виды графов:

В ходе исследования мы выяснили, что графы бывают следующих видов:

• Направленные графы

• Граф управление

• Граф подчинения

• Составляющие графы

• Ориентированные графы

• Орграфы

Теория графов и анализ художественного текста:

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

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

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

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

Сравнив прозу Л.Н. Толстого и Ф.М. Достоевского, можно отметить, что стилю обоих писателей присущи деревья достаточно сложной конфигурации. Но фразы Л.Н. Толстого мы опишем скорее, как громоздкие, а построения Достоевского как «неупорядоченные». Язык Толстого тяжеловесен, а язык Достоевского хаотичен. Как же переводится эта оценка современного писателя на формальный язык деревьев? Громоздкость синтаксиса Толстого сказывается в значительном ветвлении деревьев влево (что повышает глубину дерева); хаотичность синтаксиса Достоевского — в большом числе зигзагов в правой части дерева. (Приложения, рис. 19)

Признаки И. Л. Севбо:

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

1. Количество узлов дерева (т.е. количество слов во фразе)

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

3. Число уровней в дереве (длина самого длинного из путей дерева)

4. Ширина ветвления корня (число узлов подчиненных корню)

Проведем эксперимент. Перед нами строки из произведения «Кавказский пленник» А.С. Пушкина и М.Ю. Лермонтова. Нам нужно определить, какой граф принадлежит Пушкину, а какой Лермонтову. Мы это сделаем с помощью Севбо.

Из данных таблицы (Приложения, рис. 20) ясно, что дерево на рисунке В (Приложения, рис. 22) сложнее дерева на рисунке А. (Приложения, рис. 21) Как было сказано выше, язык Лермонтова немного сложнее языка Пушкина. Следовательно, граф на рисунке А принадлежит А.С. Пушкину, а граф на рисунке Б — М.Ю. Лермонтову.

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