Приложения теории графов

Приложения  теории графов 
 
 
 
 
 
 
 
 
 

    

 
 

 

Оглавление

1. Введение…………………………………………………….………3
2. Приложение теории графов в ИТ……………………………….…6
3. Приложение теории графов в информатике……………….……..7
4. Приложение теории графов в химии……………………….……...8
5. Приложение теории графов в биологии…………………………..9
6. Приложение теории графов в психологии……………………….10
7. Приложение теории графов в логистике…………………………11
8. Приложение теории графов в физике……………………………..12
9. Приложение теории графов в программировании ……………....13
10. Приложение теории графов в экономике………………………...16
11. Заключение………………………………………………………....18
12. Список использованной литературы………………………...........19

 
 
 
 
 
 
 
 
 
 
 
 
 

Введение

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

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

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

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

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

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

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

Приложение  теории графов в ИТ 

Применение информационных технологий в теории графов можно  разделить по следующим группам. 

Программы, служащие для набора научных статей по теории графов (например, Microsoft Word, TeX). 

Программы для  изображения графов в удобном  виде (например, использование автофигур  в Microsoft PowerPoint, либо стандартного набора специальных изображений в Microsoft Visio). 

Программы для  подготовки иллюстраций научных  статей (например, Adobe Photoshop, Corel Draw). 

Специальные библиотеки в языках программирования. Начиная  от единиц, предоставляющий графический  интерфейс пользователю, до сложных  библиотек используемых в при реализации алгоритмов в коммерческих приложениях (например, JGraph и JGraphT в Java). Такого рода библиотеки содержат минимально необходимые сущности, например «граф», «ребро», «бинарное дерево», а также стандартный набор алгоритмов: «поиск в ширину», «поиск в глубину», проверка связности графа, бинарный поиск и многое другое, что позволяет прикладному алгоритмисту абстрагироваться от несущественной детализации и перейти непосредственно к реализации алгоритма. 

Поиск информации в сети Internet. 

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

Приложение  теории графов в информатике 

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

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

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

Приложение  теории графов в химии 

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

      C_nH_2n+2

      Все атомы углеводорода четырехвалентны, все атомы водорода одновалентны. Структурные формулы простейших углеводородов (а – метан CH₄, б – этан C₂H₆).

       

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

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

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

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

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

Приложение  теории графов в биологии 

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

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

Приложение  теории графов в психологии 

В психологии графы  используются для представления  промежуточных и

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

 При этом  часто графы приобретают формы  блок-схем. Примерами могут служить 

 блок-схема  сенсорного уровня отражения  Ю. М. Забродина, блок-схема 

 функциональной  системы П. К. Анохина и многие  другие.  
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Приложение  теории графов в логистике 

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