Теория графов и сетей — это один из разделов дискретной математики, изучающий свойства графов.
История разработки теории графов
Основоположником теории графов считается Леонард Эйлер, великий математик восемнадцатого века. Он решил задачу семи мостов в Кенигсберге, которая формулировалась следующим образом:
«Как пройти по всем мостам города, не проходя ни по одному из них дважды?»
В то время в Кенигсберге на реке Преголя было построено именно семь мостов, которые соединяли два больших речных острова и берега реки. Эйлер обозначил речные берега и острова в реке точками, а мосты, которые их соединяют, обозначил линиями. То есть он построил первый в мире граф, получивший название графа Кенигсбергских мостов. Эйлер доказал, что решения этой задачи не существует, и определил необходимое условие наличия искомого маршрута в произвольном графе, а именно, число вершин, из которых идёт нечётное количество линий обязано равняться или двум, или нулю. Для первого варианта такими вершинами являются начальная и конечная точки маршрута. Позднее было доказано, что это условие является и достаточным. На рисунке ниже представлен граф Кенигсбергских мостов:
Рисунок 1. Граф Кенигсбергских мостов. Автор24 — интернет-биржа студенческих работ
Теория графов и сетей
Современная теория графов применяется в очень многих научных и промышленных сферах. Любая сеть независимо от вида взаимоотношений среди объектов может быть представлена в формате требуемого графа. Объектами графа могут быть нейронные связи в человеческом мозге, объединённые в сеть персональные компьютеры или просто взаимоотношения среди большой группы людей. Формально граф может быть определён как два множества V и G, которые называются вершинами и рёбрами. Рёбрами являются соединяющие вершины линии. Число рёбер, которые выходят из вершины графа, определяется как его степень.
Граф является ориентированным, если его рёбра имею направление. То есть ребро обозначается стрелкой, выходящей из начальной точки (вершины), и приходящей в конечную точку. Мультиграфом является такой граф, у которого две вершины соединены более чем одним ребром. Часто рёбра обладают весом, этот параметр, как правило, является положительным числом. К примеру, если представить схему Московского метро в виде графа, то в качестве вершин будут станции, а в качестве рёбер можно принять туннели, которые их соединяют. Семейством весов рёбер будет временной интервал, затрачиваемый на проезд между станциями, соединяемыми ребром.
Применение теории графов и сетей в экономике
Рассмотрим реальный пример. Учёные высшей технической школы Цюриха (Швейцария) исследовали информацию о тридцати семи миллионах «экономических объектов», фирм, компаний, разных фондов и частных предпринимателей, которых объединяет то обстоятельство, что все они являются участниками экономического процесса. Сначала они решили выполнить отделение реальной экономики от сложных взаимоотношений финансовых институтов. С этой целью из тридцати семи миллионов объектов они выбрали лишь транснациональные корпорации, владеющие прямо или через посредников по крайней мере десятью процентами фирм, находящихся в разных странах. В случае, когда корпорация является группой связанных фирм с единым хозяином, то вместо всех их учитывался только владелец. К примеру, The Coca-Cola Company является владельцем Coca-Cola Hellenic Bottling Company, у которой во владении находится Coca-Cola Beverages Austria, но учитывалась, в данном случае, только The Coca-Cola Company.
Таким образом учёные сформировали единый изучаемый объект, который включал в свой состав 43060 корпоративных объекта, действующих в 116 мировых государствах. Всю эту базу научные работники сформировали в виде взвешенного ориентированного мультиграфа. Множеством его вершин является набор экономических объектов (сущностей). Две сущности соединялись ребром, начинающимся в вершине А, и оканчивающимся в вершине В, в случае, когда вершине А принадлежит часть, отображаемая вершиной В. Далее специалисты все 43060 корпораций и отобрали из тридцати семи миллионов вершин лишь те, в которые возможно попасть при движении по стрелкам из вершин, являющихся корпорациями, или откуда возможно дойти до этих вершин. В итоге был сформирован граф, явившийся главным исследуемым объектом. Он состоял из 600508 вершин и 1006987 рёбер. Такая схема сети с ядром приведена на рисунке ниже:
Рисунок 2. Схема сети с ядром. Автор24 — интернет-биржа студенческих работ
В сформированном графе каждое ребро получало числовое значение от нуля до единицы, что является долей владения компаний. То есть, когда, к примеру, ребро, соединяющее вершины А и В, обладало весом 0.51, то это обозначало, что компания А владеет 51 процентом компании В. Помимо этого каждая вершина тоже имела вес, обозначающий стоимость определённой компании. Естественно, для того, чтобы оценить влияние компании на рынок будет мало оценки, с какими из вершин соединены исходящие из неё рёбра. Следует учитывать и те вершины, до которых при движении по стрелкам возможно добраться за серию переходов. В таком случае веса рёбер перемножаются.
На заключительном этапе специалисты применяли различные методики по анализу контроля компании над рынком:
- Линейная модель. Контроль над компанией делился среди всех её собственников согласно доле владения.
- Пороговая модель. Аналог предыдущего, но для долей менее 0,5. Когда у компании обнаруживался мажоритарный совладелец, то есть имеющий во владении более пятидесяти процентов компании, то компания считалась целиком под его контролем.
- Плотностная модель. Контроль над компанией делится согласно соотношению долей её совладельцев.
Учёные выполнили анализ топологии без анализа контроля, который показал, что в сформированной сети присутствует только один так называемый сильно связанный компонент. Это 1347 экономических сущностей, прямо или косвенно владеющих всеми другими компаниями сети. Данное множество называется ядром, которое в данном случае является сильно взаимосвязанным. Усреднённая степень вершины в ядре равняется примерно двадцати.
