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

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

Оглавление

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 потомков? Рекуррентное соотношение, обозначающее число необходимых  случаев, известно в биологии под  названием процесса Гальтона-Ватсона. Его можно рассматривать как частный случай многих общих формул. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

 В общих  словах, мы ищем способ реализации  функции смежности, N(v), так, чтобы  N[v] было каким-либо набором (или  в отдельных случаях просто  итератором) смежных с v вершин. Как  и во многих других книгах мы сосредоточимся на двух наиболее известных представлениях: списках смежности и матрицах смежности, потому что они наиболее полезны и обобщены. Альтернативные представления описаны в последнем разделе ниже. 
 
 
 
 
 
 
 
 
 
 
 
 
 

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

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

     1. «Транспортные» задачи, в которых вершинами графа являются пункты, а ребрами – дороги (автомобильные, железные и др.) и / или другие транспортные (например, авиационные) маршруты. Другой пример – сети снабжения (энергоснабжения, газоснабжения, снабжения товарами и т.д.), в которых вершинами являются пункты производства и потребления, а ребрами – возможные маршруты перемещения (линии электропередач, газопроводы, дороги и т.д.). Соответствующий класс задач оптимизации потоков грузов, размещения пунктов производства и потребления и т.д., иногда называется задачами обеспечения или задачами о размещении. Их подклассом являются задачи о грузоперевозках.

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

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

     4. Управление проектами. (Управление проектами – раздел теории управления, изучающий методы и механизмы управления изменениями (проектом называется целенаправленное изменение некоторой системы, осуществляемое в рамках ограничений на время и используемые ресурсы; характерной чертой любого проекта является его уникальность, то есть нерегулярность соответствующих изменений.)). С точки зрения теории графов проект – совокупность операций и зависимостей между ними. Хрестоматийным примером является проект строительства некоторого объекта. Совокупность моделей и методов, использующих язык и результаты теории графов и ориентированных на решение задач управления проектами, получила название календарно-сетевого планирования и управления (КСПУ). В рамках КСПУ решаются задачи определения последовательности выполнения операций и распределения ресурсов между ними, оптимальных с точки зрения тех или иных критериев (времени проекта, затрат, и др.).

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

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

Заключение

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

Список  использованной литературы 

1. "Соросовский образовательный журнал" №11 1996 (ст. "Плоские графы");

2. Касаткин  В. Н. "Необычные задачи математики", Киев, "Радяньска школа" 1987(часть 2);

3. Гарднер М. "Математические досуги", М. "Мир", 1972(глава 35);

4. "В помощь  учителю математики", Йошкар-Ола, 1972 (ст. "Изучение элементов теории  графов");

5. Олехник С. Н., Нестеренко Ю. В., Потапов М. К. "Старинные занимательные задачи", М. "Наука", 1988(часть 2, раздел 8; приложение 4);

6. Гарднер М. "Математические головоломки и развлечения", М. "Мир", 1971;

7. Оре О. "Графы и их применения", М. "Мир", 1965;

8. Зыков А. А. "Теория конечных графов", Новосибирск, "Наука", 1969;

9. Берж К. "Теория графов и ее применение", М., ИЛ, 1962;

10. Реньи А., "Трилогия о математике", М., "Мир", 1980.