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

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

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

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

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

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

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

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

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

Графы представляют собой наиболее абстрактную структуру, с которой приходится сталкиваться в теории ЭВМ (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.