Топологічний аналіз мереж
Теорія графів дозволяє досліджувати топологічний аналіз транспортних і економіко-географічних мереж: доступність, зв`язність, форму і структуру. Є ряд показників, що описують ці мережі. Їх називають заходами - кількісні показники, що характеризують явище або процес.
Зміст
Показники доступності. Побудова графа, що моделює доступність транспортної мережі, полягає в наступному. Всі точки перетину доріг приймаються за фіктивні вершини. Це поняття умовне, оскільки ці точки правомірно вважати вершинами, як і населені пункти. Змістовна інтерпретація їх може бути представлена різницею умовних позначень в графі: фактичний вершина (населений пункт) -N - фіктивна вершина точок перетину доріг. Використання фіктивних ребер призводить до істотних погрішностей.
Заходи доступності використовуються для оцінки транспортно-географіshy-чеського положення. До них відносять число Кеніга, індекс оптимальної зв`язності вершин, індекс центральності Бавелаша, Бошама.
Якщо граф невеликий ці заходи можна розрахувати по графічному зображенню. Для великого графа будується матриця і розрахункові операції проводять за допомогою матричної алгебри.
Нехай буде наступний граф з населеними пунктами (рис. 9.3). До нього складемо матрицю найкоротших відстаней - за кількістю інцідентних ребер з`єднують вершини (табл. 9.1), обчислимо заходи доступності і дамо оцінку оптимальної зв`язності вершин.
Мал. 9.3. Граф для оцінки місця розташування об`єктів
Чотири індексу (Si,Ki, Ba,Bi) В табл. 9.1 характеризують ступінь доступності вершин. Вони претендують на центральне положення в графі. індексиSi,Ki - абсолютні, Ba,Bi - відносні.
Абсолютний індекс доступності Siрозраховується як сума інцідентних ребер до кожної вершині по рядках: Sii = sum- xi. Для першого рядка матриці ця сума дорівнює: 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 Відео: AutoCAD MAP 3D: Аналіз топології мережі |
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 Відео: Теорія мереж: 6. Топологія мережі | 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 |
sum- 120
Другий абсолютний індекс число Кеніга (Ki) - це найбільший за величиною елемент (xi) Рядки матриці: Kii = xi(max). Егомінімальное значення, рівне трьом, для вершин 2, 3, 4, 6 вказує на їх центральне положення (ступінь їх доступності).
Індекс Бавелаша (Ва) визначається як отношеніесуммарного значення індексу sum- Si до величини індексуSii каждойстрокі: sum- Si / Sii. Максимальне значення індексу Бавелаша вказує на високу ступінь доступності вершин. Ними є вершини 2, 3, 4, 6, мають Ва = 10.
Відносний індекс Бошама (Bi) Розраховується за такою формулою: Bi = (n - 1) / Sii, де n- загальне число вершин на транспортної мережі без однієї (в нашому випадку 8 - 1 = 7). Величину 7 ділять на значення Siiкожного рядка. Максимальне значення індексу Бошама (0,58) для вершин 2, 3, 4, 6, який визначає їх центральне положення.
Таким чином, як абсолютні, так і відносні індекси вказали на центральне положення другої і четвертої вершин графа і матриці.
Показники зв`язності. До заходів зв`язності відносяться наступні топологічні параметри: alpha--, beta--, gamma - індекси. Індекси приймають максимальні значення у випадках насичення мережі контактами. найсвіжіші можна прочитати і переглянути на сайті kzn.tv. Також на даному новинному ресурсі Телерадіокомпанії «Казань», є можливість дивитися новини онлайн в будь-який вас зручний час і завжди бути в курсі всіх найсвіжіших новин.
індекс alpha- являє собою відношення цикломатическая числа графа (m - n + ) до максимально можливого числа циклів в цьому графі (2n - 5):
alpha- = (m - n + ) / (2n - 5),
де m - число ребер, n - число вершин, - число зв`язкових компонент графа- для зв`язкового графа цикломатичне число буде m - n + 1.
індекс alpha- характеризує надмірність зв`язків в сітці. Його значення варіюють в межах від 0 до 1, при множенні на 100 - у відсотках. Надмірність зв`язків можна оцінити по Цикломатичне число, але його не можна використовувати для порівняння зв`язків в різних мережах.
індекс beta- являє собою відношення числа ребер m мережі до числа її вершин n. Чим більше ребер пов`язує одне і те ж число вершин, тим більше циклів в мережі, тим складніше її структура і вище зв`язність. Значення індексу коливаються в межах від 0 до 3. У незв`язних графах і деревах величина індексу менше одиниці. при значенні beta- = 1 граф має тільки один цикл, при зміні від 1 до 3 графи мають більше одного циклу.
індекс gamma- являє собою відношення числа ребер m до їх максимально можливій кількості в мережі, яке в плоских графах дорівнює 3 middot- (n - 2), деn - число вершин. Величина індексу в графі коливається від 0 до 1. Він характеризує повноту зв`язків в ланцюзі.
Показники форми графа. Заходи форми мереж пов`язані з визначенням топологічного діаметра графа. Діаметр графа (delta-) являє собою топологічну довжину, яка дорівнює числу ребер в найкоротшій ланцюга, що з`єднує дві найвіддаленіші один від одного вершини (рис. 9.4, а). Якщо на ребрах вказані конкретні відстані, то такі помічені моделі графа більш змістовні (рис. 9.4, б).
Відео: Дані On-line в ГІС Zulu - Системи диспетчерського контролю мереж
Мал. 9.4. Заходи форми мереж:
а - з урахуванням числа ребер (delta- = 6 pi- (r) = 1,33) - б - з урахуванням реальних відстаней
Топологічна міра форми (pi- (r)) З урахуванням загального числа ребер в графі (m) І його діаметра (delta-) - топологічної довжини, визначається за формулою: pi- (r) = m / delta- = 11/3 = 3,6 (див. рис. 9.4, а). У цьому графі вісім топологічних діаметрів, рівних 3, що зв`язують різні пари вершин. У міру збільшення числа ребер в мережі поліпшуються зв`язку між її вершинами, топологічний діаметр зменшується, значення заходів форми збільшується. Це означає, що поліпшується форма мережі. Вона стає більш компактною.
Для графів, в яких зазначено відстань в певних одиницях виміру, міра форми визначається таким же способом, як і при обліку кількості ребер, але з урахуванням протяжності всієї мережі графа в кілометрах (Д) і довжини топологічного діаметра в кілометрах (Тд):
pi- = Д / Тд.
Якщо топологічних діаметрів в графі кілька, їх реальна довжина в кілометрах буде різною. На рис. 9.4, б також вісім топологічних діаметрів delta-, рівних 3. На рис. 9.5 ці діаметри виділені жирною лінією, а реальні довжини топологічних діаметрів різні. Для таких графів топологічна міра форми pi- визначається з урахуванням середньої довжини топологічного діаметра Т. Останній визначається за формулою: Т = sum- Тд / Р, де р - число топологічних діаметрів мережі.
Мал. 9.5. Варіанти топологічних діаметрів графа
Топологічні діаметри виділені жирними лініями на рис. 9.5. Виділено три діаметра по 130 км, два - по 140, два - по 130, один - 160 км. Середній діаметр Тд = 128,75. Загальна протяжність цієї мережі 500 км. Звідси індекс pi- = 500 / 128,75 = 3,88. Результати показують, що індекс для оцінки міри форми, отриманий з урахуванням довжини ребер в кілометрах, більш точний в порівнянні з індексом pi- (r).
високі значення pi - індексу вказують на компактну територію, що охоплюються графом.
Відео: Р.В. Шамин. Функціональний аналіз аналіз - лекція № 12
Структурні параметри мереж. Виявлення параметрів територіальних структур ґрунтуються на топологічних параметрах, серед яких слід відзначити заходи інтеграції, уніполярності і централізації. Ці заходи засновані на суми відстаней.
Інтегрування в суспільстві, промисловості, політиці в сучасних умовах відіграє істотну роль. Для географічних мереж важливо виявити ступінь інтеграції. Запропоновано наступний розрахунок заходи інтеграції: S = 1/2 sum- Sii. Мережа слід вважати інтегрованою, якщо всі її вершини мають приблизно рівні значення заходів інтеграції. Параметр інтеграції характеризує міру центральності на множині вершин.
Уніполярність вказує на наявність вершини в графі, яка ізольована від інших вершин, т. Е. Характеризується мінімальним значенням індексу оптимальної зв`язності Si. Параметр уніполярності відноситься до вершини, що має мінімальне значення зв`язності: V = Siimin.
Іноді в мережі зустрічаються групи вершин, які різко відрізняються між собою за величиною індексу оптимальної зв`язності. Таку мережу можна розглядати як централізовану. Міру централізації можна розрахувати наступним чином: H = sum- (Sii -Simin) або H = 2S - nV.
Розглянуті заходи, що характеризують структурні параметри, дають можливість виявити особливості кількісної та якісної структури мереж, що відрізняються закономірностями формування, розвитку і функціонування.
