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

 

 

 

 

 

Реферат

 

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

 

 

 

Выполнила: Манкевич Е. Ю.

ДК-55-Ф-1

Проверила: Абинова Н. А.

 

 

 

2015

Содержание

Введение

1. Рассмотреть общие представления  о графах

1.1 Исторические сведения

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

1.3 Основные определения

2. Виды графов

2.1 Примеры графов

2.2 Матричное задание графов. Матрицы смежности и инцидентности

2.3 Связность. Компоненты  связности

3. Задачи решаемые с помощью графов

3.1 Задача коммивояжера

Заключение

 

Введение

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

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

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

 

 

Учитывая вопрос актуальности данной работы нами была поставлена цель - исследовать применение графов в экономике

Объектом исследования является графы.

Предметом - экономика.

Для достижения цели нами сформулированы следующие задачи:

1. Рассмотреть общие представления  о графах

2. Дать характеристику  различным видам графа

3. Изучить применение  графов в экономике.

4. Подвести итоги и  сделать выводы.

 

1. Общее представление  о графах

1.1 Исторические сведения

Введения термина «граф» приписывается известному венгерскому математику Д.Кенигу (1884-1944) автору одной из первых книг по теории графов (1936г.) Однако имеются и более ранние работы (статьи как самого Кенига , так и других авторов), где используется это название.

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

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

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

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

Пусть дано множество Х, которое состоит из элементов, называемых точками. Дан закон, позволяющий установить соотношение Т между каждым элементом множества Х и некоторыми из его подмножеств. Обозначим через Тх некое подмножество множества Х, отвечающее элементу х множества Х. Две математические величины - «множество Х» и «соответствие Т» - определяют граф G, обозначаемый как G = (X, T). Элементы множества Х будем изображать точками, и называть вершинами графа. Соотношения Т будем изображать отрезками (иногда ориентированными), соединяющими элемент с элементами подмножества Тх, и называть ребрами или дугами графа. Граф G называется конечным, если число его вершин конечно.

1.3 Основные определения

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

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

Граф называется ориентированным, если указано направление дуг

Примером неориентированного графа является карта дорог

Граф называется петлей, если его начало и конец совпадают.

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

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

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

 

 

 

 

 

 

 

 

 

 

 

 

2. Виды графов

2.1 Примеры графов. Операции  над графами

Между элементами множества вершин и множества ребер определено отношение инцидентности. Говорят, что ребро е инцидентно вершинам v1, v2, если оно соединяет эти вершины и наоборот, каждая из вершин v1, v2 инцидентна ребру е.

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

Рассмотрим некоторые важные типы графов.

Определение. Граф, у которого множество ребер пусто, называется вполне несвязным (или пустым) графом. Вполне несвязный граф обозначают N

Заметим, что у вполне несвязного графа все вершины изолированы

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

Граф, у которого все вершины имеют одну и ту же локальную степень n, называется регулярным (или однородным) степени n.

Регулярные графы степени 3 называются кубическими (или трехвалентными).

Известным примером кубического графа является граф Петерсона

Среди регулярных графов особенно интересны так называемые платоновы графы - графы, образованные вершинами и ребрами пяти правильных многогранников - Платоновых тел: тетраэдра, куба, октаэдра, додекаэдра и икосаэдра.На рисунке 6 приведен граф, соответствующий кубу.

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

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

Если в двудольном графе каждая вершина из V1 соединена с каждой вершиной из V2, то граф называется полным двудольным.

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

Очевидно, что всякий несвязный граф можно представить в виде объединения конечного числа связных графов - каждый из таких связных графов называется компонентой связности графа.

Связный регулярный граф степени 2 называется циклическим графом.

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

Подграфом графа G называется граф, все вершины и ребра которого содержатся среди вершин и ребер графа G. Подграф называется собственным, если он отличен от самого графа.

2.2 Матричное задание графов. Матрицы смежности, инцидентности

Пусть D = (V, Х) - орграф, где V={v1, v2, …,vn}, X={x1, x2, …, xm}.

Матрицей смежности орграфа D называется квадратная матрица A(D)=[aij]

 Матрицей инцидентности  орграфа D называется (nm) -матрица B(D)=[bij], у которой

Введем также матрицы смежности и инцидентности для неориентированных графов. Пусть

G = (V, X) - граф, где V={v1, v2, …,vn}, X={x1, x2, …, xm}.

Матрицей смежности графа G называется квадратная матрица A(G)=[aij] порядка n, у которой

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

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

2.3 Связность. Компоненты  связности

Граф (орграф) называется связным (сильно связным), если для любых двух его вершин v, w существует маршрут (путь), соединяющий v, w (из v и w).

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

Если граф не является связным, то он называется несвязным.

 Компонентой связности  графа называется его связный  подграф, не являющийся собственным  подграфом никакого другого связного  подграфа.

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

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

Разделяющим множеством связного графа G называется такое множество его ребер, удаление которого приводит к несвязному графу.

Разрезом называется такое разделяющее множество, никакое собственное подмножество которого не является разделяющим.

Разрез, состоящий из одного ребра, называется мостом (перешейком).

 

3. Задачи решаемые с помощью графов

3.1 Задача о четырех красках

Задача о четырех красках. Разбиение на плоскости на непересекающиеся области называется картой. Области на карте называются соседними, если они имеют общую границу. Задача состоит в раскрашивании карты таким образом, чтобы никакие две соседние области не были закрашены одним цветом. С конца позапрошлого века известна гипотеза, что для этого достаточно четырех красок. В 1976 году Аппель и Хейкен опубликовали решение задачи о четырех красках, которое базировалось на переборе вариантов с помощью компьютера. Решение этой задачи «программным путем» явилось прецедентом, породившим бурную дискуссию, которая отнюдь не закончена. Суть опубликованного решения состоит в том, чтобы перебрать большое, но конечное число (около 2000) типов потенциальных контрпримеров к теореме о четырех красках и показать, что ни один случай контрпримером не является. Этот перебор был выполнен программой примерно за тысячу часов работы суперкомпьютера. Проверить «вручную» полученное решение невозможно - объем перебора выходит далеко за рамки человеческих возможностей. Многие математики ставят вопрос: можно ли считать такое «программное доказательство» действительным доказательством? Ведь в программе могут быть ошибки… Методы формального доказательства правильности программ не применимы к программам такой сложности, как обсуждаемая. Тестирование не может гарантировать отсутствие ошибок и в данном случае вообще невозможно. Таким образом, остается уповать на программистскую квалификацию авторов и верить, что они сделали все правильно.

 

Заключение

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

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