Анотація: Розглядаються питання досяжності для орграфов і способи знаходження матриць досяжності і контрдостіжімості. Розглядається матричний спосіб знаходження кількості шляхів між будь-якими вершинами графа, а також знаходження безлічі вершин, що входять в шлях між парою вершин. Мета лекції: Дати уявлення про досяжності і контрдостіжімості і способах їх знаходження
Досяжність і контрдостіжімость
Завдань, в яких використовується поняття досяжності, досить багато. Ось одна з них. Граф може бути моделлю якоїсь організації, в якій люди представлені вершинами, а дуги інтерпретують канали зв'язку. При розгляді такої моделі можна поставити питання, чи може інформація від однієї особи хi бути передана іншій особі хj, т. Е. Чи існує шлях, що йде від вершини хi до вершини хj. Якщо такий шлях існує, то говорять, що вершина хj досяжна з вершини хi. Можна цікавитися досяжністю вершини хj з вершини хi тільки на таких шляхах, довжини яких не перевищують заданої величини або довжина яких менше найбільшого числа вершин в графі і т. П. Завдання.
Досяжність в графі описується матрицею досяжності R = [rij], i, j = 1, 2, ... n, де n - число вершин графа, а кожен елемент визначається наступним чином:
rij = 1, якщо вершина хj досяжна з хi,
rij = 0, в іншому випадку.
Безліч вершин R (xi) графа G, досяжних з заданої вершини xi, складається з таких елементів xj, для яких (i, j) -й елемент в матриці досяжними дорівнює 1. Очевидно, що всі діагональні елементи в матриці R рівні 1, оскільки кожна вершина досяжна з себе самої путeм довжини 0. Оскільки пряме відображення 1-го порядку Г + 1 (xi) є безліччю таких вершин xj, які досяжні з xi з використанням шляхів довжини 1, то безліч Г + (Г + 1 (xi) ) = Г + 2 (xi) складається з вершин, досяжних з xi з використанням шляхів довжини 2. Аналогічно Г + p (xi) є безліччю верші н, які досяжні з xi за допомогою шляхів довжини p.
Так як будь-яка вершина графа, яка досяжна з xi, повинна бути досяжна з використанням шляху (або шляхів) довжини 0 або 1, або 2, ..., або p, то безліч вершин, досяжних для вершини xi, можна представити у вигляді
.
Як бачимо, безліч досяжних вершин R (xi) являє собою пряме транзитивне замикання вершини xi, т. Е. R (xi) = T + (xi). Отже, для побудови матриці досяжності знаходимо досяжні безлічі R (xi) для всіх вершин 
. Вважаючи, rij = 1, якщо 
і rij = 0 в іншому випадку.
Мал.4.1.
Досяжність в графі: а -граф; б - матриця суміжності; в - матриця досяжності; г-матриця контрдостіжімості.
Для графа, наведеного на Мал. 4.1 , А, безлічі досяжних знаходяться наступним чином:
,
,
,
,
,
,
.
Матриця досяжності має вигляд, як показано на Мал. 4.1 , В. Матрицю досяжності можна побудувати по матриці суміжності ( Мал. 4.1 , Б), формуючи безлічі T + (xi) для кожної вершини xi.
Матриця контрдостіжімості Q = [qij], i, j = 1, 2, ... n, де n - число вершин графа, визначається наступним чином:
qij = 1, якщо з вершини xj можна досягти вершину xi,
qij = 0, в іншому випадку.
Контрдостіжімим безліччю Q (xi) є безліч таких вершин, що з будь-якої вершини цієї множини можна досягти вершину xi. Аналогічно побудові досяжного мно-дружність R (xi) можна записати вираз для Q (xi):
.
Таким чином, видно, що Q (xi) - це є не що інше як зворотне транзитивне замикання вершини xi, т. Е. Q (xi) = Т-xi). З визначень очевидно, що стовпець xi матриці Q (в якому qij = 1, якщо 
, І qij = 0 в іншому випадку) збігається з рядком xi матриці R, т. Е. Q = RT, де RT - матриця, транспонована до матриці досяжності R.
Матриця контрдостіжімості показана на Мал. 4.1 , Г.
Слід зазначити, що оскільки всі елементи матриць R і Q рівні 1 або 0, то кожен рядок можна зберігати в двійковій формі, економлячи витрати пам'яті ЕОМ. Матриці R і Q зручні для обробки на ЕОМ, так як з обчислювальної точки зору основними операціями є швидкодіючі логічні операції.
