Курсовая работа (т): Особенности применения теории графов при решении задач и в практической деятельности

6. Графы - деревья. Корень

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

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

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

Число вершин и рёбер дерева. Для подсчёта числа элементов дерева служит теорема: "Дерево с n вершинами имеет n - 1 рёбер".

Как выглядит дерево рассмотрим следующий рис. 11:

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

Рис.11

Рассмотрим произвольное дерево с n заданными и пронумерованными в произвольном порядке вершинами. Пусть например, т = 11(левый, рис.12).

Рис.12

Но ведь те же 11 вершин можно соединить попарно 10 рёбрами и по- другому, чтобы получилось какое-то новое дерево (правый рисунок). У этого нового дерева совпадает с предыдущим только 3 ребра.

Спрашивается: сколько существует таких разных деревьев?

Английскому математику А.Кэлли (1875 г.) опыт, приобретённый в процессе непосредственного подсчёта числа деревьев, помог найти правильный ответ на этот вопрос. Деревьев с n пронумерованными вершинами существует nn-2..

7. Применение графов в жизни

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

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

·        В информатике и программировании (граф - схема алгоритма).

·        В коммуникационных и транспортных системах. В частности, для маршрутизации данных в интернете.

·        В экономике.

·        В логистике.

·        В физике или схемотехнике (топология межсоединений элементов на печатной плате или микросхеме представляет собой граф или гиперграф).

·        В биологии.

·        стереохимии

·        В строительстве.

·        В менеджменте.

·        В географии.

·        В социологии.

·        В автоматизации технологических процессов и производств.

·        В психологии.

·        В рекламе.

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

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

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

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

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

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

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

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

Теория графов в психологии.

Теория графов в логистике.

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

Заключение

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

Список литературы

1.      <#"878354.files/image015.gif">

Задача 2. Условие: Восстановить по графу матрицу инцидентности для неориентированного графа.

Ответ: