Матрична форма запису графа
Граф можна задати матрицею суміжності
vij = 1 якщо граф містить ребро (i, j);
vij = 0, інакше.
Наприклад, граф структурної схеми системи управління якістю, зображений на рис.3.2 можна як наступної матриці суміжності.
Використовуються інші форми матричного запису графів. Наприклад, у вигляді матриці інцидентів
1, якщо i - Початкова вершина ребра (i, j);
wij = -1, якщо i кінцева вершина ребра (i, j);
0 в інших випадках.
Наприклад, для графа на рис.3.2 матриця інцидентів виглядатиме таким чином.
Якщо граф не орієнтований, то матриця інцидент містить тільки 0 і 1.
wij = 1, якщо є ребро (i, j);
wij = 0 у протилежному випадку.
Спискова форма запису графа
Велика кількість нулів у матриці суміжності та інцидентів свідчить про неекономічність цих форм подання графів, що особливо суттєво, якщо графи містять багато вершин. Тому, крім матриць, використовуються спискові форми запису графів. Список є безліч
R(i) R - є безліч вершин графа, в які можна безпосередньо потрапити з i-ої вершини.
Наприклад, у графі структури управління якістю, показаної на рис.3.2 можна подати наступним списком.
Цей запис можна спростити, якщо елементи множин R(i) записати в круглих дужках, перед якими поставити номер (позначення) i:
R = [О(Р), Р(Ц), Ц(І,У), І(О), У(П), П(Т), Т(Ц)]
Лекція 4
Аналіз структури системи
Опис структури системи як графа дає можливість провести аналіз структури системи та оцінити її якість. Розглянемо такі основні завдання аналізу структур.
Аналіз елементів
ПриДослідженні структури особливе значення має виділення елементів, що відповідають ізольованим, висячим та тупиковим вершинам графа.Ізольовані вершинине інцидентні жодному з ребер графа;висячівідповідають вершинам, у які не можна потрапити з жодної іншої вершини графа;тупиковівідповідають вершинам, з яких не можна потрапити до інших вершин графа. Як приклад розглянемо граф на рис.4.1.
Рис.4.1 Фрагмент структури системи
Граф на рис.4.1 містить ізольовану вершину 12, висячі вершини 1, 2, 3 і жодної тупикової вершини. Якщо з'єднати вершину 12 з вершинами 11 і 8, то вона перетвориться на тупикову. Ізольовані, висячі та тупикові вершини на графі знаходяться наступним чином:
Береться матриця суміжності графа V = vij;
За цією матрицею кожної вершини k (k = 1, 2, … , n), де n – число вершин у графі, визначається вектор v(k) = (vk, v k ) з компонентами
vk = , v k = , де
vk – сума елементів k-ого рядка матриці V, що визначає число ребер, що виходять з вершини k,
v k – сума елементів k-го стовпця матриці V, що визначає число ребер, що входять у вершину k.
vk = v k = 0, то вершина k ізольована;
Якщо vk = 0, то вершина k тупикова;
v k = 0, то вершина k висяча.
Що дає аналіз елементів?
а. Наявність у графі ізольованих вершин зазвичай свідчить про помилки, допущені при формуванні або опис структури, адже система завжди цілісний об'єкт, всі елементи якого взаємопов'язані;
б. Висячі вершини повинні відповідати вхідним елементам системи (вхід системи);
в. Тупикові вершини повинні відповідати вихідним елементам системи (вихід системи);
м. Черезвисячі та тупикові вершини здійснюється процес взаємодії системи із зовнішнім середовищем, тому дуже важливо, щоб шляхом дослідження графа вони були правильно інтерпретовані.
Аналіз зв'язку
Дослідження зв'язку між елементами структури спрямовано, перш за все, на виявлення у відповідному графі петель, контурів та сильнозв'язаних підграфів. Наприклад, граф на рис.4.1 має петлю у вершини 11 і два контури, утворені ребрами, що з'єднують вершини (4, 5, 6, 9) та (6, 9, 10, 11).
Подграф називаєтьсясильнозв'язним, якщо всі входять до нього вершини взаємодосяжні, тобто. з будь-якої вершини підграфа можна потрапити до будь-якої іншої його вершини.
2.1.Виділення з графа сильнозв'язного підграфа
Нехай Qi – безліч вершин графа, досяжних з вершини, а Q i – безліч вершин графа, у тому числі можна досягти вершину .
З визначення сильнозв'язного підграфа випливає, що перетин множин Q(i) = Qi∩Q i містить вершини, що належать одному сильнозв'язного підграфа, тому знаходження перетину Q(i) рівнозначне визначенню сильнозв'язного підграфа, що включає вершину .
Послідовно перебираючи і визначаючи множини Q(i) до тих пір, поки ці множини не увійдуть всі вершини графа, можна знайти його розбиття на сильнозв'язні підграфи.
2.2.Приклад визначення сильнозв'язного графа
Для графа на рис.4.1 знайдемо його сильнозв'язні подграф шляхом визначення наступних перетинів множин.
Тепер вихідний граф можна розбити на сильнозв'язні підграфи: G(1), G(2), G(3), G(4), G(7), G(8), G(12), з яких лише G(4) ) є нетривіальним (містить більше однієї вершини).
Подамо знайдені сильнозв'язні підграфи як вершини нового графа, показаного на рис.4.2.
В результаті отримаємо граф, званийконденсацією, який значно простіше вихідного і в якому відсутні контури та петлі. Побудова конденсацій рекомендується для складних структур, що містять велику кількість елементів. Безпосереднє дослідження таких структур утруднено, а виділення конденсацій дозволяє зосередити увагу на аналізі суттєвих зв'язків, що найбільше характеризують особливості взаємодії елементів системи.
Діаметр структури
Якщо I і J – безліч висячих та тупикових вершин графа відповідно, то діаметр структури визначається наступною формулою
d = dij,
, де
dij – довжина мінімального шляху між висячою вершиною та тупиковою вершиною дорівнює числу ребер, що становлять цей шлях.
Діаметр структури характеризує максимальну кількість зв'язків, що поділяють вхідні та вихідні елементи структури. За значенням діаметра d можна побічно судити про ряд граничних параметрів системи, зокрема про її надійність, тривалість, затримки повідомлень, що йдуть від висячих вершин до тупикових, інерційності. Визначення значень dij зводиться до стандартної задачі пошуку найкоротшого шляху на графі кожної пари (i,j) такий, що , .
Зв'язкість
Теоретично графів під зв'язністю графів розуміється найменше вершин, видалення яких із графів наводить анезв'язному (що містить ізольовані вершини) або тривіальному (що складається з однієї вершини) графу. Використовується також поняттяреберної зв'язності- найменшого числа ребер, видалення яких призводить до незв'язного чи тривіального графа. Обидві характеристики досить складно вирахувати, ще складніше дати їм відповідну фізичну інтерпретацію, тому обмежимося лише визначенням поняття «зв'язність».
Ступінь централізації
Ця характеристика (критерій якості) структури застосовується для оцінки нерівномірності завантаження елементів структури шляхом обчисленняіндексу центральностіβ. Приклад показано на рис.4.3.
Рис.4.3.а) зв'язки у структурі розподілені рівномірно β = 0
рис.4.3.б) структура з максимальним ступенем централізації β = 1
Індекс центральності для неорієнтованого графа обчислюється за такими формулами
,
причому всім i = j природним чином довжина мінімального шляху dij = 0.
Складність
Поняття складності структури важко піддається формалізації і має суб'єктивний відтінок. Складність структури визначатимемо складністю аналізу її властивостей. Якщо функціонування системи уявити як процес переробки вхідних впливів у вихідні, спрямовані відповідно від вхідних елементів системи до вхідних, можна припустити, що вивчати властивості цього процесу тим важче, чим різноманітніше шляху, які ведуть від входу до виходу системи. Взявши це припущення за основу, показник (критерій складності) можна обчислити за такою формулою
, де
m1 та m2 – число висячих та тупикових вершин у графі структури;
ρij -кількість різних шляхів, що ведуть від i-ої висячої в j-у тупикову.