Применение теории графов в экономике сообщение
Обновлено: 01.07.2024
2. Горбатов В.А. Дискретная математика. Теория, задачи, приложения: учебное пособие. – М.: Физмалит, 2000. – 544 с.
3. Долгополова А.Ф., Гулай Т.А., Литвин Д.Б. Перспективы применения математических методов в экономических исследованиях // Аграрная наука, творчество, рост. – 2013. – С. 255-257.
4. Долгополова А. Особенности применения методов математического моделирования в экономических исследованиях / А.Ф. Долгополова, Т.А. Гулай, Д.Б. Литвин // Кант: экономика и управление. – 2013. – №1. – С. 62-66.
7. Невидомская И.А., Якубова А.М. Применение факторного анализа при исследовании экономических процессов // Современные наукоемкие технологии. – 2013. – № 6. – С. 81-83.
8. Коннова Д.А., Леликова Е.И., Мелешко С.В. Взаимодействие математики с экономикой // Современные наукоемкие технологии. – 2014. – № 5-2. – С. 159-161.
9. Бондаренко В.А., Цыплакова О.Н. Некоторые аспекты интегрированного подхода изучения математического анализа // Учетно-аналитические и финансово-экономические проблемы развития региона: матер. 76-й научно-практической конференции. – Ставрополь: Альфа-Принт, 2012. – С. 280-283.
Теория графов один из наиболее интересных разделов математики. Родоначальником теории графов считается швейцарский математик Леонард Эйлер, который в 1736 году сформулировал решение задачи о семи кёнигсбергских мостах, ставшей впоследствии классической задачей теории графов. Развитие этой теории долгое время не происходило, а лишь в середине 20 века интерес к проблемам теории графов вновь появился, главным образом в Англии. Наиболее известной задачей-проблемой того периода является задача четырех красок, которая была составлена математиком Огастесом де Морганом в 1850 году. В настоящее время теория графов неуклонно развивается и получил широкое распространение в экономических исследованиях. В последнее время все чаще наблюдается проникновение математики в разные сферы и отрасли многих наук. Этот процесс затронул и экономическую сферу. Для нахождения кратчайшего или объездного пути, рационального маршрута передвижения, для оптимизации производственного цикла применяется теория графов.
В экономической сфере задачи теории графов применяются для принятия локально оптимальных решений на каждом этапе, причем конечное решение также окажется оптимальным.
Классическим примером таких задач является практическое применение жадного алгоритма в решении экономических проблем.
Под жадным алгоритмом понимается алгоритм, основанный на жадной стратегии, то есть достижении конечного результата с наименьшими затратами.
Пусть на территории некоторого города N размещены заводы, которые поставляют свою продукцию в магазины. В результате разработки были определены возможные трассы для прокладки коммуникаций и оценена стоимость их создания для каждой трассы (табл. 1).
ГРАФЫ И ОБЛАСТИ ИХ ПРИМЕНЕНИЯ
Автор работы награжден дипломом победителя II степени
Текст работы размещён без изображений и формул.
Полная версия работы доступна во вкладке "Файлы работы" в формате PDF
Теория графов в настоящее время является интенсивно развивающимся разделом математики. Это объясняется тем, что в виде графовых моделей описываются многие объекты и ситуации, что очень важно для нормального функционирования общественной жизни. Именно этот фактор определяет актуальность их более подробного изучения. Поэтому тематика данной работы достаточно актуальна.
Цель исследовательской работы: выяснить особенности применения теории графов в различных областях знаний и при решении логических задач.
Цель определила следующие задачи:
познакомиться с историей теории графов;
изучить основные понятия теории графов и основные характеристики графов;
показать практическое применение теории графов в различных областях знаний;
рассмотреть способы решения задач с помощью графов и составить собственные задачи.
Объект исследования: сфера деятельности человека на предмет применения метода графов.
Гипотеза. Мы предполагаем, что изучение теории графов может помочь учащимся решать логические задачи по математике, что определит их дальнейшие интересы.
Методы исследовательской работы:
В ходе нашего исследования были использованы такие методы, как:
1) Работа с различными источниками информации.
2) Описание, сбор, систематизация материала.
3) Наблюдение, анализ и сравнение.
4) Составление задач.
Новизна работы заключается в авторском составлении задач по теме исследования и нахождении практического использования теории графов в современном мире.
Теоретическая и практическая значимость данной работы определяется тем, что результаты могут быть использованы на информатике, математике, геометрии, черчении и классных часах, а также для широкого круга читателей, заинтересованных данной темой. Исследовательская работа имеет выраженную практическую направленность, так как в работе автором представлены многочисленные примеры применения графов во многих областях знаний, составлены свои задачи. Данный материал можно использовать на факультативных занятиях по математике.
ГЛАВА I. ТЕОРЕТИЧЕСКИЙ ОБЗОР МАТЕРИАЛА ПО ТЕМЕ ИССЛЕДОВАНИЯ
Теория графов. Основные понятия
В математике определение графа дается так:
Граф– это конечное множество точек – вершин, которые могут быть соединены линиями – ребрами.
В качестве примеров графов могут выступать чертежи многоугольников, электросхемы, схематичное изображение авиалиний, метро, дорог и т.п. Генеалогическое дерево также является графом, где вершинами служат члены рода, а родственные связи выступают в качестве ребер графа.
Схема Санкт-Петербургского метро
Рис. 1 Примеры графов
Число ребер, которое принадлежит одной вершине, называется степенью вершины графа. Если степень вершины нечетное число, вершина называется – нечетной. Если степень вершины число четное, то и вершина называется четной.
Рис. 2 Вершина графа
Нуль-граф – это граф, состоящий только из изолированных вершин, не соединенных ребрами.
Полный граф – это граф, каждая пара вершин которого соединена ребром. N-угольник, в котором проведены все диагонали, может служить примеров полного графа.
Если в графе выбрать такой путь, когда начальная и конечная точка совпадают, то такой путь называется циклом графа. Если прохождение через каждую вершину графа происходит не более одного раза, то цикл называется простым.
Если в графе каждые две вершины связаны ребром, то это связанный граф. Граф называется несвязанным, если в нем есть хотя бы одна пара несвязанных вершин.
Если граф связанный, но не содержит циклов, то такой граф называетсядеревом.
Характеристики графов
Путь графа– это такая последовательность, в которой каждые два соседних ребра, имеющих одну общую вершину, встречаются только один раз.
Длина кратчайшей цепи из вершин a и b называется расстоянием между вершинами a и b.
Вершина а называется центром графа, если расстояние между вершиной а и любой другой вершиной является наименьшим и из возможных. Такое расстояние есть радиус графа.
Максимально возможное расстояние между двумя любыми вершинами графа называется диаметром графа.
Раскраска графов и применение.
Если внимательно посмотреть на географическую карту, то можно увидеть железные или шоссейные дороги, которые являются графами. Кроме этого на катре есть граф, который состоит из границ между странами (районами, областями).
В 1852 году английскому студенту Френсису Гутри поставили задачу раскрасить карту Великобритани, выделив каждое графство отдельным цветом. Из-за небольшого выбора красок Гутри использовал их повторно. Он подбирал цвета так, чтобы те графства, которые имеют общий участок границы, обязательно окрашивались в разные цвета. Возник вопрос, какое наименьшее количество красок необходимо для раскрашивания различных карт. Френсис Гутри предположил, хотя и не смог доказать, что четырех цветов будет достаточно. Эта проблема бурно обсуждалась в студенческих кругах, но позже была забыта.
Можно представить задачу о четырех красках несколько иначе.
Для этого рассмотрим произвольную карту, представив ее виде графа: столицы государств являются вершинами графа, а ребра графа связывают те вершины (столицы), государства которых имеют общую границу. Для получения такого графа формулируется следующая задача – необходимо раскрасить граф с помощью четырех цветов так, чтобы вершины, имеющие общее ребро были раскрашены разными цветами.
Эйлеровы и Гамильтоновы графы
В 1859 году английским математиком Уильямом Гамильтоном была выпущена в продажу головоломка – деревянный додекаэдр (двенадцатигранник), двадцать вершин которого были обозначены гвоздиками. Каждая вершина имела название одного из крупнейших городов мира – Кантон, Дели, Брюссель, и т.д. Задача заключалась в нахождении замкнутого пути, который проходит по ребрам многогранника, побывав в каждой вершине только один раз. Для отмечания пути использовался шнур, который цепляли за гвоздики.
Гамильтоновым циклом называется граф, путь которого является простым циклом, который проходит через все вершины графа по одному разу.
На реке Прегель расположен город Калининград (бывший Кенигсберг). Река омывала два острова, которые между собой и с берегами были соединены мостами. Старых мостов сейчас уже нет. Память о них осталась только на карте города.
Однажды один житель города спросил у своего знакомого, можно ли пройти по всем мостам, побывать на каждом только один раз и вернуться к тому месту откуда началась прогулка. Эта задача заинтересовала многих горожан, но решить ее никто не смог. Этот вопрос вызвал заинтересованность ученных многих стран. Решение проблемы получил математик Леонард Эйлер. Кроме этого он сформулировал общий подход к решению таких задач. Для этого он превратил карту в граф. Вершинами этого графа стала суша, а ребрами – мосты, ее соединяющие.
При решении задачи про мосты Кенигсберга Эйлеру удалось сформулировать свойства графов.
Начертить граф, начав движение с одной вершины и окончив в той же вершине одним росчерком (дважды не проводя по одной и той же линии и не отрывая карандаша от бумаги) возможно в том случае, если все вершины графа четные.
Если есть граф с двумя нечетными вершинами, то его вершины тоже можно соединить одним росчерком. Для этого нужно начать с одной, а закончить на другой любой нечетной вершине.
Если есть граф с числом нечетных вершин больше двух, то граф невозможно начертить одним росчерком.
Если применять эти свойства на задачу о мостах, то можно увидеть, что все вершины исследуемого графа нечетные, значит, этот граф нельзя соединить одним росчерком, т.е. невозможно пройти по всем мостам один раз и закончить путь в том месте, где он был начат.
Если граф имеет цикл (не обязательно простой), содержащий все рѐбра графа по одному разу, то такой цикл называется Эйлеровым циклом. Эйлерова цепь (путь, цикл, контур) — цепь (путь, цикл, контур), содержащая все рѐбра (дуги) графа по одному разу.
Специалисты по системному анализу из Цюриха доказали, что значительная часть экономики (около 40 процентов) контролируется совсем небольшой долей компаний, куда входят преимущественно финансовые институты. Несмотря на то, что такой вывод подозрительно напоминает классическую теорию заговора, полученный результат является первой попыткой анализа структуры финансовых потоков в экономической системе в целом. Также это отличный повод напомнить читателям "Ленты.ру" о существовании теории графов.
Графы, мультиграфы, веса и прочая интересная теория
Родоначальником теории графов можно считать Леонарда Эйлера - великого российского (как настаивают многие историки) математика швейцарского происхождения XVIII века. Он заинтересовался вот какой задачей. Во времена Эйлера в Кенигсберге через реку Преголя было семь мостов между двумя речными берегами и парой крупных островов в русле. Задача о мостах звучала так: надо было придумать такой маршрут прогулки, чтобы он проходил по каждому мосту ровно один раз (при этом маршрут не обязан был начинаться и заканчиваться в одной и той же точке).
Эйлер изобразил два берега реки и острова точками, а мосты, соединяющие их, линиями. Так получился первый граф, который получил название графа Кенигсбергских мостов. Эйлер нашел необходимое условие существования искомого пути в произвольном графе: количество вершин, из которых выходит нечетное число линий должно быть либо два, либо ноль. В первом случае эти вершины - начало и конец обхода. Позже достаточность этого условия была доказана учеником Эйлера Карлом Хирхольцером.
Граф Кенигсбергских мостов
В современной версии теория графов используется повсеместно - всякую сеть вне зависимости от природы соотношений между объектами (это могут быть связи между нейронами в мозгу, романтические отношения между людьми внутри большой компании или же просто соединенные сетью компьютеры) можно представлять в виде подходящего графа. Формальное определение этого объекта звучит так: графом в математике называется пара множеств V и G, называемых вершинами и ребрами. Ребра существуют не сами по себе, а связывают отдельные вершины. Количество ребер, выходящих из вершины графа, называется ее степенью.
Граф называется ориентированным, если на ребрах нарисованы стрелочки - фактически это означает, что вместо двух концов у ребра появляется начало (откуда выходит стрелка) и конец (куда она приходит). Мультиграфом называется такой граф, где две вершины может соединять больше одного ребра. Иногда ребрам приписывают так называемые веса - обычно положительные числа. Например, если наш граф - схема Московского метрополитена, где вершинами выступают станции, а ребрами - соединяющие их туннели, то естественное семейство весов - время, которое тратится при проезде от одной станции до другой. Также разные числовые метки можно присваивать и вершинам графа - их иногда тоже называют весами.
Экономика как запутанный клубок
Итак, ученые из Швейцарской высшей технической школы Цюриха воспользовались Orbis 2007 - платной базой данных, которая хранит информацию о 37 миллионах "экономических сущностей" - компаний, фондов, частных лиц, объединенных тем, что они участвуют в экономическом процессе. В частности, некоторым из них принадлежат доли во вполне реальных компаниях.
На первом этапе ученые решили отделить реальную экономику от сложных отношений финансовых институтов. Для этого из 37 миллионов сущностей они отобрали только транснациональные корпорации (то есть владевшие напрямую или через дочерние организации как минимум 10 процентами компаний, расположенных в разных государствах). При этом, если корпорация представляла собой группу взаимосвязанных компаний с одним владельцем (например, The Coca-Cola Company владеет Coca-Cola Hellenic Bottling Company, которая, в свою очередь, владеет Coca-Cola Beverages Austria), то вместо всех них брался этот самый владелец (The Coca-Cola Company в данном случае). Так появился основной объект изучения - 43060 корпораций, работающих в 116 странах мира.
Всю базу Orbis ученые представили как взвешенный ориентированный мультиграф. Множество его вершин, как легко догадаться, - это экономические сущности. Две сущности соединяло ребро с началом в вершине A и концом в вершине B, если вершине A принадлежала часть, обозначаемая вершиной B. Затем ученые взяли 43060 корпорации и выбрали из 37 миллионов вершин только те, куда можно было попасть, двигаясь по стрелкам из вершин-корпораций, либо откуда можно было попасть в эти вершины. В результате был получен граф, который и оказался основным объектом исследования - он содержал 600508 вершин и 1006987 ребер.
Схема сети с ядром
В полученном графе каждому ребру присваивалось число от 0 до 1 - доля владения одной компании в другой. То есть, если, например, ребро соединяло вершины A и B и имело вес 0,51, то это означало, что A владело 51 процентом компании B. Кроме этого все вершины были также наделены весами - стоимостью соответствующей компании (таким образом, при стоимости B в x миллионов долларов, A имело собственности на 0,51x миллиона). Понятное дело, что для оценки влияния компании на рынок недостаточно оценить, с какими вершинами связаны выходящие из нее ребра - необходимо рассматривать и вершины, до которых, двигаясь по стрелкам, можно дойти за несколько ходов. В этом случае числа на ребрах перемножаются (действительно, если A владеет 50 процентами B, а B - 50 процентами C, то A владеет 25 процентами от C).
На последнем этапе ученые использовали три разных метода для анализа контроля компании над рынком. Первый метод (линейная модель) делил контроль над компанией между всеми ее собственниками пропорционально долям владения. Второй метод (пороговая модель) работал, как и предыдущий, при всех долях меньше 0,5. Если у компании был мажоритарный владелец - то есть субъект, которому принадлежало более 50 процентов компании, то она полностью переходила под его контроль. Наконец третий метод (плотностная модель) делил контроль над фирмой в зависимости от соотношений долей всех владельцев. В этом случае, например, если один из владельцев имеет небольшую долю, но все остальные имеют еще меньшую, то он может сконцентрировать в своих руках значительную часть контроля над компанией.
Топология мировой закулисы
Топологический анализ, без анализа контроля, позволил установить, что в полученной сети имеется ровно одна так называемая сильно связанная компонента - 1347 экономических сущностей, которые напрямую или косвенно владеют всеми остальными компаниями сети. Это множество получило название ядра, которое, если прибегнуть к терминологии приверженцев теории заговора, можно назвать мировой закулисой. Тут, кстати, уместно будет разочаровать этих самых приверженцев: ядро оказалось очень сильно взаимосвязанным - средняя степень вершины внутри ядра составляет примерно 20. По словам ученых, это делает всякое взаимодействие внутри множества довольно затруднительным.
В свою очередь анализ влияния разными методами позволил установить, что примерно 40 процентов объема мирового рынка контролируют всего 147 компаний. Основную часть из них составляют финансовые институты.
Несмотря на то, что выводы ученых уже подвергаются сомнению, - в частности, специалисты говорят, что взаимосвязь между контролем и долей в компании не такая простая, как в работе исследователей, - у их работы есть одно несомненное преимущество. По сути это первая попытка проанализировать мировую финансовую систему на устойчивость, используя структурный анализ. Кто знает, быть может, этот подход окажется плодотворнее классического и вопросы стабильности не будут оставаться на откуп чистой теории вероятностей.
ГОСТ
Теория графов и сетей — это один из разделов дискретной математики, изучающий свойства графов.
История разработки теории графов
Основоположником теории графов считается Леонард Эйлер, великий математик восемнадцатого века. Он решил задачу семи мостов в Кенигсберге, которая формулировалась следующим образом:
В то время в Кенигсберге на реке Преголя было построено именно семь мостов, которые соединяли два больших речных острова и берега реки. Эйлер обозначил речные берега и острова в реке точками, а мосты, которые их соединяют, обозначил линиями. То есть он построил первый в мире граф, получивший название графа Кенигсбергских мостов. Эйлер доказал, что решения этой задачи не существует, и определил необходимое условие наличия искомого маршрута в произвольном графе, а именно, число вершин, из которых идёт нечётное количество линий обязано равняться или двум, или нулю. Для первого варианта такими вершинами являются начальная и конечная точки маршрута. Позднее было доказано, что это условие является и достаточным. На рисунке ниже представлен граф Кенигсбергских мостов:
Рисунок 1. Граф Кенигсбергских мостов. Автор24 — интернет-биржа студенческих работ
Теория графов и сетей
Современная теория графов применяется в очень многих научных и промышленных сферах. Любая сеть независимо от вида взаимоотношений среди объектов может быть представлена в формате требуемого графа. Объектами графа могут быть нейронные связи в человеческом мозге, объединённые в сеть персональные компьютеры или просто взаимоотношения среди большой группы людей. Формально граф может быть определён как два множества V и G, которые называются вершинами и рёбрами. Рёбрами являются соединяющие вершины линии. Число рёбер, которые выходят из вершины графа, определяется как его степень.
Граф является ориентированным, если его рёбра имею направление. То есть ребро обозначается стрелкой, выходящей из начальной точки (вершины), и приходящей в конечную точку. Мультиграфом является такой граф, у которого две вершины соединены более чем одним ребром. Часто рёбра обладают весом, этот параметр, как правило, является положительным числом. К примеру, если представить схему Московского метро в виде графа, то в качестве вершин будут станции, а в качестве рёбер можно принять туннели, которые их соединяют. Семейством весов рёбер будет временной интервал, затрачиваемый на проезд между станциями, соединяемыми ребром.
Готовые работы на аналогичную тему
Применение теории графов и сетей в экономике
Таким образом учёные сформировали единый изучаемый объект, который включал в свой состав 43060 корпоративных объекта, действующих в 116 мировых государствах. Всю эту базу научные работники сформировали в виде взвешенного ориентированного мультиграфа. Множеством его вершин является набор экономических объектов (сущностей). Две сущности соединялись ребром, начинающимся в вершине А, и оканчивающимся в вершине В, в случае, когда вершине А принадлежит часть, отображаемая вершиной В. Далее специалисты все 43060 корпораций и отобрали из тридцати семи миллионов вершин лишь те, в которые возможно попасть при движении по стрелкам из вершин, являющихся корпорациями, или откуда возможно дойти до этих вершин. В итоге был сформирован граф, явившийся главным исследуемым объектом. Он состоял из 600508 вершин и 1006987 рёбер. Такая схема сети с ядром приведена на рисунке ниже:
Рисунок 2. Схема сети с ядром. Автор24 — интернет-биржа студенческих работ
В сформированном графе каждое ребро получало числовое значение от нуля до единицы, что является долей владения компаний. То есть, когда, к примеру, ребро, соединяющее вершины А и В, обладало весом 0.51, то это обозначало, что компания А владеет 51 процентом компании В. Помимо этого каждая вершина тоже имела вес, обозначающий стоимость определённой компании. Естественно, для того, чтобы оценить влияние компании на рынок будет мало оценки, с какими из вершин соединены исходящие из неё рёбра. Следует учитывать и те вершины, до которых при движении по стрелкам возможно добраться за серию переходов. В таком случае веса рёбер перемножаются.
На заключительном этапе специалисты применяли различные методики по анализу контроля компании над рынком:
- Линейная модель. Контроль над компанией делился среди всех её собственников согласно доле владения.
- Пороговая модель. Аналог предыдущего, но для долей менее 0,5. Когда у компании обнаруживался мажоритарный совладелец, то есть имеющий во владении более пятидесяти процентов компании, то компания считалась целиком под его контролем.
- Плотностная модель. Контроль над компанией делится согласно соотношению долей её совладельцев.
Учёные выполнили анализ топологии без анализа контроля, который показал, что в сформированной сети присутствует только один так называемый сильно связанный компонент. Это 1347 экономических сущностей, прямо или косвенно владеющих всеми другими компаниями сети. Данное множество называется ядром, которое в данном случае является сильно взаимосвязанным. Усреднённая степень вершины в ядре равняется примерно двадцати.
Читайте также: