На головну

Виділення зв'язкових (сильних компонент) в Орграф. побудова конденсації

  1.  Види парної кореляційно-регресійного зв'язку. Парна лінійна корреляционно- регресійна модель і її побудова.
  2.  Зовнішній вигляд і побудова робочої області ресурсів
  3.  Зовнішній вигляд і побудова рядка введення повідомлення і часткового меню чату
  4.  Вибір (виділення) файлів і папок
  5.  Вибір турбогенераторів і побудова графіків навантаження
  6.  ВИДІЛЕННЯ РЕЧОВИН
  7.  Виділення води рослиною. Гутація, транспирация; фізіологічні значення цих процесів.

сильна зв'язність. Дві вершини в орієнтованому графі сильно пов'язані, якщо існує шлях з першої в другу і з другої в першу. Компонента сильної зв'язності графа - максимальне безліч вершин орієнтованого графа таке, що для будь-яких двох вершин з цієї множини існує шлях як з першої в другу, так і з другої в першу.

конденсація графа - Уявлення вихідного графа у вигляді конденсованого, в якому кожна вершина відповідає сильно зв'язковий компоненті вихідного графа.

Граф, що виходить в результаті стягування (видалення ребра і ототожнення його кінцевих вершин) всіх дуг сильно зв'язкових компонент орієнтованого графа

Для прикладу розглянемо орграф на ріс.1.17а і складемо для нього частину множин  (Ріс.1.17б) і матриця досяжності  (Ріс.1.17в).

Очевидно, що безліч  визначає безліч вершин, досяжних з  і для яких  є досяжною. Таким чином,  лежить хоча б на одному шляху з в  . Такі вершини називаються істотними щодо кінцевих вершин и  , а все  називається надлишковим щодо шляху з в .

Граф (орграф) називається зв'язковим (сильно зв'язковим), Якщо для будь-яких ,  існує маршрут (шлях) з в .

односторонньо зв'язковим називається орграф, якщо для будь-яких ,  існує шлях з в  або з в .

орграф називається слабо зв'язковим, Якщо зв'язковим є асоційований з ним неорієнтовані граф. Якщо граф (орграф) не є зв'язковим (слабо зв'язковим), то він називається незв'язним.

Якщо у вихідному графі можна виділити підграф  , Такий, що  досяжна з и  (Т. Е. Все вершини взаімодостіжіми), то такий підграф називається сильною (зв'язковий) компонентою (СК).

Очевидно, що елементи СК визначаються безліччю  . нехай  . Знайдемо чергову СК  , так щоб  . Отримаємо безліч вершин нової СК  . Продовжимо процес виділення СК до тих пір поки вони вичерпаються. Тоді сформуємо граф  такий, що  є виділені СК, а дуга  існує в  тоді і тільки тоді, коли в  існує дуга  така, що  , а  , Причому така, що  . Отриманий таким чином граф  називається конденсацією. На ріс.1.18б представлені всі СК графа  на ріс.1.18а, а конденсація  представлена ??на ріс.1.18в

Якщо покласти, що для графа  побудована матриця досяжності  , То можна запропонувати ефективний метод виділення всіх СК і побудови конденсації.

Для цього введемо матрицю  , Де символ  позначає кронекерово або пряме твір матриць, при якому елементи матриці (  ) Визначаються співвідношенням  . Тоді для елементів матриці  справедливо: .

Оскільки всі вершини  досяжні і контрдостіжіми для себе ж (  ), То  . Якщо ж  для  це означає що и  , А отже вершина  досяжна з  , А вершина  досяжна з  а отже вони взаімодостіжіми і входять в одну СК.

Так для графа на ріс.1.18 матриці и  мають вигляд

.

Тоді алгоритм виділення СК і побудови конденсації може мати наступний вигляд: (далі  - Безліч вершин конденсації,  - Безліч задіяних вже в СК вершин,  - Поточна СК,  -поточна число СК в графі.

Крок 1. Установка початкових значень: .

Крок 2. Контроль для виходу: Якщо  йти в кінець, (крок 4), інакше до кроку 3.

Крок 3. Виділення СК: Вважаємо  . для ,  , формуємо , ,  . Переходимо до кроку 2.

Крок 4. Закінчення.

, .

Для графа 1.18 в результаті роботи алгоритму отримаємо таблицю:

Для матриці суміжності  розміром 3х3 отримаємо відмінні від нуля елементи:

 , Т. К. Існує дуга, наприклад  , Така, що и ;

 , Т. К. Існує дуга, наприклад  , Така, що и ;

 , Т. К. Існує дуга, наприклад  , Така, що и .

Інші елементи дорівнюють нулю. тоді ,

що і відображено на малюнку 1.18. б і 1.18в.

Тепер для конденсації графа, оскільки це вже ациклический граф можна побудувати ієрархічну структуру, в якій вершини розташовані за рівнями  так, що дуги вихідного графа (або конденсації)  спрямовані так, що для , ? .



 Концепція об'єктно-орієнтованого програмування. |  ІІ. Практична частина

 Обгрунтування алгоритму Террі |  Доведення твердження «б». |  Призначення та класифікація систем вентиляції. Кондиціювання Повітря. |  Поведінка фірм на конкурентних ринках. Рівновага Курно. Рівновага і нерівновага Стакельберга |  Наближення функції за методом найменшого квадрата. нелінійна регресія |  Обробка подій в VB |  Найкоротші шляхи в графі. Способи їх відшукання в залежності від типу графа |  Нормування та методи розрахунку штучного освітлення приміщень. |  Моделі взаємодії споживачів і виробників на ринках. Паутинообразная модель встановлення рівноважної ціни. |  Точні і наближені методи розв'язання систем лінійних рівнянь. |

© um.co.ua - учбові матеріали та реферати