Применение теории графов в реальной жизни. Работа №303678

Школьная научно – практическая конференция

«Дети в мире науки»

 

 

 

 

Секция: Математика, физика, информатика

 

 

 

 

 

 

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

Применение теории графов в реальной жизни

Мицканюк Константин

МАОУ «СОШ №3 Г Новый Уренгой, 8 класс

 

 

 

 

 

 

 

 

 

Научный руководитель: Кузьмина Л. Д,

Учитель высшей категории

МАОУ СОШ №3 г. Новый Уренгой;

 

 

2020

 

Содержание:

 

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

 

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

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

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

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

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

 

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

 

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

I.Ведение

Любой из нас, конечно, прав,

Найдя без проволочек,

Что он … обыкновенный граф

Без палочек и точек.

Граф - древневерхненемецкий gravo, gravio «предводитель, вождь»;

Граф (титул) — дворянский титул;

Граф - греч. γράφω «царапаю, черчу, пишу»;

Граф - латинское слово «графио» - пишу;

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

Понятие «граф» – одно из самых простых и самых употребительных понятий в математике и других науках, хотя теория графов зародилась чуть ли не 250 лет тому назад в ходе решения головоломки, и тогда же появились первые теоремы о графах, доказанные самим Леонардом Эйлером. Долгие годы эта теория не находила широких приложений и была известна в основном как средство решения головоломок, логических или развлекательных задач, задач олимпиадного типа или на смекалку. При решении таких задач удобно составлять таблицы, изображать объекты точками, соединять их отрезками или стрелками, подмечать закономерности из полученных рисунков, выполнять над точками и отрезками операции, не похожие на алгебраические и геометрические. И в обычной жизни очень часто мы рисуем на бумаге точки, изображающие химические вещества, населенные пункты, генеалогические деревья и соединяем эти точки линиями и стрелками, означающими некоторые отношения между рассматриваемыми объектами. Такие схемы встречаются всюду под различными названиями: электрические цепи (в физике), карты, лабиринты, диаграммы, генеалогические деревья, диаграммы организации (в экономике), социограммы (в психологии) и т.д. В 1936 году Д. Кёниг предложил называть такие схемы графами и систематически изучать их свойства.

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

Цель:

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

Задачи:

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

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

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

.

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

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

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

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

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

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

Алтуальность:

 

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

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

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

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

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

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

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

Теория графов является одной из немногих областей математики, дата рождения которых может быть указана. Первая работа о графах, принадлежащая швейцарскому математику Леонарду Эйлеру, появилась в 1736 г. в публикациях Петербургской Академии наук. Эйлер (Euler) Леонард, математик, механик и физик.

Родился в семье небогатого пастора Пауля Эйлера. Образование получил сначала у отца, а затем в Базельском университете, где слушал лекции по математике Иоганна Бернулли. В 1727 г. Эйлер был приглашен в Петербургскую Академию Наук, где за 14 лет подготовил к печати около 80 трудов и опубликовал свыше 50. В 1741 Эйлер переехал в Берлин, где за 25 лет жизни подготовил около 300 работ. Живя в Берлине, Эйлер не переставал интенсивно работать для Петербургской АН, сохраняя звание её почётного члена. Он вёл обширную научную и научно-организационную переписку, в частности переписывался с М. В. Ломоносовым, которого высоко ценил. В июле 1766 Эйлер вместе с семьей вернулся в Петербург. Несмотря на преклонный возраст и постигшую его почти полную слепоту, он до конца жизни продуктивно работал. За 17 лет вторичного пребывания в Петербурге им было подготовлено около 400 работ.

Знаменитая задача о мостах города Кенигсберга (сейчас это Калининград).Город Кенигсберг стоит там, где два рукава реки Прегель, сливаясь, омывают остров Кнейпхоф. Остров и берега соединены между собой семью мостами. Издавна среди жителей Кёнигсберга была распространена такая загадка: как пройти по всем мостам (через реку Прегеля), не проходя ни по одному из них дважды. Многие кёнигсбержцы пытались решить эту задачу как теоретически, так и практически, во время прогулок. Впрочем, доказать или опровергнуть возможность существования такого маршрута никто не мог. В 1736 году задача о семи мостах заинтересовала выдающегося математика, члена Петербургской академии наук Леонарда Эйлера, о чём он написал в письме итальянскому математику и инженеру Мариони от 13 марта 1736 года. В этом письме Эйлер пишет о том, что он смог найти правило, пользуясь которым, легко определить, можно ли пройти по всем мостам, не проходя дважды ни по одному из них. Ответ был «нельзя».

Решение задачи по Леонарду Эйлеру

На упрощённой схеме части города (графе) мостам соответствуют линии (дуги графа), а частям города — точки соединения линий (вершины графа). В ходе рассуждений Эйлер пришёл к следующим выводам:

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

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

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

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

→ →

Граф кёнигсбергских мостов

Созданная Эйлером теория графов нашла очень широкое применение в транспортных и коммуникационных системах (например, для изучения самих систем, составления оптимальных маршрутов доставки грузов или маршрутизации данных в Интернете).

 

 

 

 

 

 

 

 

 

 

 

 

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

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

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

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

 

 

 

 

 

 

Вершины – точки графа

Дуга – линия со стрелкой

Ребро – линия без стрелки

Степенью вершины графа называется количество выходящих из нее ребер. В связи с этим, вершина, имеющая четную степень, называется четной вершиной, соответственно, вершина, имеющая нечетную степень, называется нечетной вершиной, т.е. вершина чётная, если из неё выходит 2,4,6,8.... линий (рёбер или дуг), вершина нечётная, если из неё выходит 1,3,5,7,9...линий (рёбер или дуг).

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

Ориентированный граф – это граф, вершины которого соединены дугами. С помощью таких графов могут быть представлены схемы односторонних отношений. Граф, отражающий отношение «пишет письма».

Взвешенный граф – это граф, у которого вершины или рёбра (дуги) несут дополнительную информацию (вес).

Изоморфные графы – это графы одинаковые, но по-разному нарисованные графы.

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

Несвязный граф имеет вид нескольких “кусков”,каждый из которых – либо отдельная вершина без ребер, либо связный граф.

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

количеством частей (Г) на которые разделяется плоскость:

В – P + Г = 2

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

n(n-1)/2

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

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

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

Задача 1. Между девятью планетами солнечной системы установлено космическое сообщение. Рейсовые ракеты летают по следующим маршрутам: Земля – Меркурий; Плутон – Венера; Земля – Плутон; Плутон – Меркурий; Меркурий –Вене; Уран – Нептун; Нептун – Сатурн; Сатурн –Юпитер; Юпитер – Марс и Марс – Уран. Можно ли долететь на рейсовых ракетах с Земли до Марса ?

Решение: Нарисуем схему условия: планеты изобразим точками, а маршруты ракет – линиями.

Теперь сразу видно, что долететь с Земли до Марса нельзя.

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

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

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

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

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

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

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

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

Задача 4. В Тридевятом царстве только один вид транспорта – ковер-самолет. Из столицы выходит 21 ковролиния, из города Дальний – одна, а из всех остальных городов, – по 20. Докажите, что из столицы можно долететь в город Дальний.

Доказательство: Понятно, что если нарисовать граф ковролиний Царства, то он может быть несвязным. Рассмотрим компоненту связности, которая включает в себя столицу Царства. Из столицы выходит 21 ковролиния, а из любых других городов, кроме города Дальний – по 20, поэтому, чтобы выполнялся закон о четном числе нечетных вершин необходимо, чтобы и город Дальний входил в эту же самую компоненту связности. А так как компонента связности – связный граф, то из столицы существует путь по ковролиниям до города Дальний, что и требовалось доказать.

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

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

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

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

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

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

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

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

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

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

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

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

Задача 9. У короля 19 баронов-вассалов. Может ли оказаться так, что у каждого вассального баронства 1, 5 или 9 соседних баронств? (Ответ. Нет, не может. В противном случае получился бы граф соседства баронств с нечетным количеством нечетных вершин.)

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

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

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

 

 

 

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

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

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

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

Лингвисты проводят анализ художественного текста по принципу И.Л. Севбо, который привёл 7 таких признаков, мы приведём для примера 4.

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

2. Количество простых

предложений в сложном (помеченных

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

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

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

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

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

Номер признака

Рисунок А

Рисунок В

1

10

12

2

1

2

3

4

5

4

3

4

 

Из данных таблицы ясно, что дерево на рисунке В сложнее дерева на рисунке А. Как было сказано выше, язык Лермонтова немного сложнее языка Пушкина. Следовательно, граф на рисунке А принадлежит А.С. Пушкину, а граф на рисунке В – М.Ю. Лермонтову. Как видите, с помощью графов, зная особенности стиля того или иного писателя, можно определить, кому принадлежит фраза.

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

 

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. Б. Пастернак.

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

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

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

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

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

небес,

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

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

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

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

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

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

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

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

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

 

3. В. Брюсов.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

 

 

Теперь начертим графы нескольких строк эти стихотворений

 

В.

Шекспир

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

3. В. Брюсов

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

Анализ можно сделаем с помощью принципа Севбо.

Из данных таблицы ясно, стилистика перевода Шекспира В Брюсововым совпадают.

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

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

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

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

 

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

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

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

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

Графы в астрономии

 

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

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

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Литература

Оре

Ойстин

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

Липатов Е. П. «Теория графов и её применение», 1986

Берж К. «Теория графов и её применение», 1962

Верезина

Л.Ю. «Графы и их применение», 1979

Крейдлин

Г.Е. «Математика помогает лингвистике», 1994

Оре

Ойстин

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

Уилсон Р. «Введение в теорию графов», 1977

Зыков Л.А. «Основа теории графов», 1987