Топологический анализ сетей

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

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

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

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

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

 

 

Рис. 9.3. Граф для оценки местоположения объектов

Четыре индекса (Si,Ki, Ba,Bi) в табл. 9.1 характеризуют степень доступности вершин. Они претендуют на центральное положение в графе. ИндексыSi,Ki – абсолютные, Ba,Bi – относительные.

Абсолютный индекс доступности Si рассчитывается как сумма инцидентных ребер к каждой вершине по строкам: Si_i = ∑ x_i. Для первой строки матрицы эта сумма равна: 0+1+2+3+3+2+4+3 = 18. По абсолютным индексам центральное положение занимают объекты с наименьшими их величинами, т. е. вершины 2, 3, 4, 6 с индексом Si равному 12 (в матрице все индексы центрального положения и сами вершины выделены полужирным курсивом).

Таблица 9.1  Матрица кратчайших расстояний между вершинами и индексы доступности вершин

 

№ вершин	1	2	3	4	5	6	7	8	Si	Ki	Ba	Bi
1	0	1	2	3	3	2	4	3	18	4	6,66	0,38
2	1	0	1	2	2	1	3	2	12	3	10,0	0,58
3	2	1	0	1	1	2	2	3	12	3	10,0	0,58
4	3	2	1	0	2	1	1	2	12	3	10,0	0,58
5	3	2	1	2	0	3	3	4	18	4	6,66	0,38
6	2	1	2	1	3	0	2	1	12	3	10,0	0,58
7	4	3	2	1	3	2	0	3	18	4	6,66	0,38
8	3	2	3	2	4	1	3	0	18	4	6,66	0,38

 

                                                                                            ∑ 120

Второй абсолютный индекс число Кенига (Ki) – это наибольший по величине элемент (x_i)строки матрицы: Ki_i = x_i (max). Егоминимальное значение, равное трем, для вершин 2, 3, 4, 6 указывает на их центральное положение (степень их доступности).

Индекс Бавелаша (Ва) определяется как отношениесуммарного значения индекса ∑ Si к величине индексаSi_i каждойстроки: ∑ Si / Si_i. Максимальное значение индекса Бавелаша указывает на высокую степень доступности вершин. Ими являются вершины 2, 3, 4, 6, имеющие Ва= 10.

Относительный индекс Бошама (Bi) рассчитывается по следующей формуле: Bi = (n – 1) / Si_i, где n – общее число вершин на транспортной сети без одной ( в нашем случае 8 – 1 = 7). Величину 7 делят на значение Si_iкаждой строки. Максимальное значение индекса Бошама (0,58) для вершин 2, 3, 4, 6, который определяет их центральное положение.

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

Показатели связности. К мерам связности относятся следующие топологические параметры: α-, β-, γ-индексы. Индексы принимают наибольшие значения в случаях насыщения сети контактами. Самые свежие новости Казани можно прочитать и просмотреть на сайте kzn.tv. Также на данном новостном ресурсе Телерадиокомпании «Казань», есть возможность смотреть новости онлайн в любое вас удобное время и всегда быть в курсе всех самых свежих новостей.

Индекс α представляет собой отношение цикломатического числа графа (m – n + ί) к максимально возможному числу циклов в этом графе (2n – 5):

α = (m – n + ί) / (2n – 5),

где m – число ребер, n – число вершин, ί – число связных компонент графа; для связного графа цикломатическое число будет m – n + 1.

Индекс α характеризует избыточность связей в сетке. Его значения варьируют в пределах от 0 до 1, при умножении на 100 – в процентах. Избыточность связей можно оценить по цикломатическому числу, но его нельзя использовать для сравнения связей в различных сетях.

Индекс β представляет собой отношение числа ребер m сети к числу ее вершин n. Чем больше ребер связывает одно и то же число вершин, тем больше циклов в сети, тем сложнее ее структура и выше связность. Значения индекса колеблются в пределах от 0 до 3. В несвязных графах и деревьях величина индекса меньше единицы. При значении β = 1 граф имеет только один цикл, при изменении от 1 до 3 графы имеют более одного цикла.

Индекс γ представляет собой отношение числа ребер m к их максимально возможному количеству в сети, которое в плоских графах равно 3 · (n – 2), гдеn – число вершин. Величина индекса в графе колеблется от 0 до 1. Он характеризует полноту связей в цепи.

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

 

                 

Рис. 9.4. Меры формы сетей:

 

а – с учетом числа ребер (δ = 6; π ^(r) = 1,33); б – с учетом реальных расстояний

Топологическая мера формы (π ^(r)) с учетом общего числа ребер в графе (m) и его диаметра (δ) – топологической длины, определяется по формуле: π ^(r) = m / δ = 11 / 3 = 3,6 (см. рис. 9.4, а). В этом графе восемь топологических диаметров, равных 3, связывающих различные пары вершин. По мере увеличения числа ребер в сети улучшаются связи между ее вершинами, топологический диаметр уменьшается, значение меры формы увеличивается. Это означает, что улучшается форма сети. Она становится более компактной.

Для графов, в которых указано расстояние в определенных единицах измерения, мера формы определяется таким же способом, как и при учете количества ребер, но с учетом протяженности всей сети графа в километрах (Д) и длины топологического диаметра в километрах (Т_д):

π = Д / Т_д.

Если топологических  диаметров в графе несколько, их реальная длина в километрах будет различной. На рис. 9.4, б также восемь топологических диаметров δ, равных 3. На рис. 9.5 эти диаметры выделены жирной линией, а реальные длины топологических диаметров различны. Для таких графов топологическая мера формы π определяется с учетом средней длины топологического диаметра Т. Последний определяется по формуле: Т = ∑ Т_д / р, где р – число топологических диаметров сети.

 

Рис. 9.5. Варианты топологических диаметров графа

Топологические диаметры выделены жирными линиями на рис. 9.5. Выделено три диаметра по 130 км, два – по 140, два – по 130, один – 160 км. Средний диаметр Т_д = 128,75. Общая протяженность этой сети 500 км. Отсюда индекс π = 500 / 128,75 = 3,88. Результаты показывают, что индекс для оценки меры формы,полученный с учетом длины ребер в километрах, более точный по сравнению с индексом π ^(r).

Высокие значения π-индекса указывают на компактную территорию, охватываемую графом.

Структурные параметры сетей. Выявления параметров территориальных структур основываются на топологических параметрах, среди которых следует отметить меры интеграции, униполярности и централизации. Эти меры основаны на суммах расстояний.

Интегрирование в обществе, промышленности, политике в современных условиях играет существенную роль. Для географических сетей важно выявить степень интеграции. Предложен следующий расчет меры интеграции: S = 1 / 2 ∑ Si_i. Сеть следует считать интегрированной, если все ее вершины имеют приблизительно равные значения мер интеграции. Параметр интеграции характеризует меру центральности на множестве вершин.

Униполярность указывает на наличие вершины в графе, которая изолирована от других вершин, т. е. характеризуется минимальным значением индекса оптимальной связности Si. Параметр униполярности относится к вершине, имеющей минимальное значение связности: V = Si_i min.

Иногда в сети встречаются группы вершин, которые резко отличаются между собой по величине индекса оптимальной связности. Такую сеть можно рассматривать как централизованную. Меру централизации можно рассчитать следующим образом: H = ∑ (Si_i –S_{i min}) или H = 2S – n V.

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