Применение графов в реальной жизни. Решение задач

Московский  издательско-полиграфический колледж  имени И.Фёдорова

Факультет Рекламы. 
 
 
 
 

РЕФЕРАТ. 

По дисциплине: «Математика»

На тему: «Применение  графов в реальной жизни. Решение  задач.» 
 
 
 

Работу  выполняли: студенты

очного  отделения, 2 курса,

группы  2Р2

Борзенкова А.В. и Зиберев А.Д. 
 
 
 
 
 
 

     Москва 2011 

Теория  графов  — это раздел дискретной математики, изучающий свойства графов. В общем смысле граф представляется как множество вершин (узлов), соединённых рёбрами. В строгом определении графом называется такая пара множеств G=(V,E), где V есть подмножество любого счётного множества, а E — подмножество V×V.

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

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

В реальной жизни графы  применяются:

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

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

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

Графы в теории массового  обслуживания

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

Графы в математике

В математике графы применяются для решения  логических задач и головоломок. Основой применения графов для решения  логических задач служит выявление  и последовательное исключение возможностей, заданных в условии. Это выявление  логических возможностей часто может  быть истолковано с помощью построения и рассмотрения соответствующих  графов. Возьмём, к примеру, такую задачу: «Беседуют трое: Белокуров, Чернов, и Рыжов. Брюнет сказал Белокурову: «Любопытно, что один из нас русый, другой - брюнет, а третий - рыжий, но ни кого цвет волос не соответствует фамилии». Какой цвет волос имеет каждый из беседующих?». Решение данной задачи можно изобразить с помощью графа.

     Решение:

      
Первое решение Для решения задачи воспользуемся таблицей 3×3. По условию задачи Белокуров не русый, Чернов не брюнет, и Рыжов не рыжий. Это позволяет поставить знак в соответствующих клетках. Кроме того, по условию Белокуров не брюнет, и, значит, в клетке на пересечении строки Белокуров и столбца Черный также нужно поставить знак минус. Из таблицы следует, что Белокуров может быть только рыжим. Поставим знак плюс в соответствующей клетке. Отсюда видно, что Чернов не рыжий. Обозначим это знаком минус в таблице. Теперь ясно, что Чернов может быть только русым, а Рыжов брюнетом. Использование таблицы помогло наглядно оформить решение задачи.

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

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

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

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

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

Графы в психологии.

В психологии графы  используются для представления  промежуточных и 
окончательных результатов теоретических и экспериментальных исследований. 
При этом часто графы приобретают формы блок-схем. Примерами могут служить 
блок-схема сенсорного уровня отражения Ю. М. Забродина, блок-схема 
функциональной системы П. К. Анохина и многие другие. 
 

Теория  Графов в химии

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

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

Графы в логистике.

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

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

Вывод:

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