Відношення досяжності модулів графів. Орграфи та бінарні відносини

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

Досяжність і контрдосяжність

Задач, у яких використовується поняття досяжності, досить багато.

Ось одна з них. Графможе бути моделлю якоїсь організації, в якій люди представлені вершинами, а дуги інтерпретують канали зв'язку. При розгляді такої моделі можна поставити питання, чи може інформація від однієї особи i бути передана іншій особі j , тобто чи існує шлях, що йде від вершин і до вершин j . Якщо такий шлях існує, то кажуть, що на вершинах j досяжнаіз вершин і . Можна цікавитися досяжністю вершин j з вершин i тільки на таких шляхах, довжини яких не перевищують заданої величини або довжина яких менша за найбільше вершин у графі і т. п. завдання.

Досяжність у графі описується матрицею досяжності R=, i, j=1, 2, ... n, деn– число вершин графа, а кожен елемент визначається так:

r ij =1, якщо вершинах j досяжна з i ,

r ij =0, інакше.

Множина вершин R(x i)графаG, досяжних із заданої вершиниx i , складається з таких елементівx i , для яких(i, j)-й елемент в матриці досяжностей дорівнює 1. Очевидно, що всі діагональні елементи в матриціR рівні 1, оскільки кожна вершина із самої шляхом довжини 0. Оскільки пряме відображення 1-го порядку Г +1 (x i) є безліччю таких вершин x j , які досяжні з x i з використанням шляхів довжини 1, то безліч Г + (Г +1 (x i)) = Г +2 (x i) складається з вершин, досяжних з x i з використанням шляхів довжини 2. Аналогічно Г + p (xi) є безліччю вершин, які досяжні з x i за допомогою шляхів довжини p.

Так як будь-яка вершина графа, яка досяжна з x i , повинна бути досяжна з використанням шляху (або шляхів) довжини 0 або 1, або 2, ..., або p, то безліч вершин, досяжних для вершини x i , можна подати у вигляді

R (xi) = (xi) Г +1 (xi) Г +2 (xi) ...Г + p (xi).

Як бачимо, безліч досяжних вершин R(x i)є пряме транзитивне замикання вершиниx i , тобто R(x i) = T + (x i). Отже, для побудови матриці досяжності знаходимо досяжні безлічі R(x i) для всіх вершин x i X. Вважаючи, r ij = 1, якщо x j R (x i) і r ij = 0 в іншому випадку.

Рис. 4.1. Досяжність у графі: а -граф; б – матриця суміжності; в – матриця досяжності; г-матриця контрдосяжності.

Для графа, наведеного на рис. 4.1,а, безлічі досягненьзнаходяться наступним чином:

R (х 1) = (х 1) (х 2, х 5) (х 2, х 4, х 5) (х 2, х 4, х 5) = (х 1, х 2, х 4, х 5) ),

R (х 2) = (х 2) (х 2, х 4) (х 2, х 4, х 5) (х 2, х 4, х 5) = (х 2, х 4, х 5),

R (х 3) = (х 3) (х 4) (х 5) (х 5) = (х 3, х 4, х 5),

R (х 4) = (х 4) (х 5) (х 5) = (х 4, х 5),

R (х 5) = (х 5) (х 5) = (х 5),

R (х 6) = (х 6) (х 3, х 7) (х 4, х 6) (х 3, х 5, х 7) (х 4, х 5, х 6) = (х 3, х 4, х 5, х 6, х 7),

R (х 7) = (х 7) (х 4, х 6) (х 3, х 5, х 7) (х 4, х 5, х 6) = (х 3, х 4, х 5, х 6) , х 7).

Матриця досяжності має вигляд, як показано на рис. 4.1, ст. Матрицю досяжностіможна побудувати за матриці суміжності(рис. 4.1, б), формуючи множини T + (x i) для кожної вершини x i.

Матриця контрдосяжності Q = [q ij], i, j = 1, 2, ... n, де n-число вершин графа, визначається наступним чином:

q ij =1, якщо з вершиниx j можна досягти вершинуx i ,

q ij =0, інакше.

Контрдосяжниммножиною Q (x i) є безліч таких вершин, що з будь-якої вершини цієї множини можна досягти вершину x i . Аналогічно побудові досяжної множини R (x i) можна записати вираз для Q (x i):

Q (xi) = (xi) Г -1 (xi) Г - 2 (xi) ... Г -p (xi).

Таким чином, видно, що Q (xi) – це не що інше як зворотне транзитивне замикання вершини x i, тобто Q (xi) = Т - (xi). З визначень очевидно, що стовпець x i матриці Q (у якому q ij = 1, якщо x j Q (x i), і q ij = 0 в іншому випадку) збігається з рядком x i матриці R, тобто Q = R T де R T - матриця, транспонована до матриці досяжності R.

Матриця контрдосяжностіпоказано на рис. 4.1,г.

Слід зазначити, що оскільки всі елементи матриць RіQ дорівнюють 1 або 0, кожен рядок можна зберігати в двійковій формі, економлячи витрати пам'яті ЕОМ. Матриці RiQ зручні для обробки на ЕОМ, так як з обчислювальної точки зору основними операціями є швидкодіючі логічні операції.

Знаходження безлічі вершин, що входять у шлях

Якщо необхідно дізнатися про вершини графа, що входять у ці шляхи, слід згадати визначення прямого і зворотного транзитивних замикань. Так як T + (x i) - це безліч вершин, в які є шляхи з вершин x i , а T - (х j) - безліч вершин, з яких є шляхи в x j, то T + (x i) T - (x j) - безліч вершин , кожна з яких належить, принаймні, одному шляху, що йде від x i к x j . Ці вершини називаються суттєвими або невід'ємними щодо двох кінцевих вершин x i x j. Всі інші вершини графа називаються несуттєвими чи надлишковими, оскільки їх видалення не впливає на шляху від x i к x j .

Рис. 4.2. Орграф

Так, для графа на рис. 4.2 знаходження вершин, що входять у шлях, наприклад з вершини х 2 у вершинух 4 зводиться до знаходження Т + (х 2) =( х 2 , х 3 , х 4 , х 5 , х 6 ),

Т - (х 4) = (х 1, х 2, х 3, х 4, х 5), та їх перетину T + (х 2) T - (х 4) = (х 2, х 3, х 4, х 5).

Матричний метод знаходження шляхів у графах

Матриця суміжності повністю визначає структуру графа. Зведемо матрицю суміжності до квадрата за правилами математики. Кожен елемент матриці А2 визначається за формулою

a (2) ik = n j = 1 a ij a jk

Доданок у формулі дорівнює 1 тоді і тільки тоді, коли обидва числа a ij і a jk дорівнюють 1, інакше воно дорівнює 0. Оскільки з рівності a ij = a jk = 1 слід існування шляху довжини 2 з вершини x i у вершинух k , що проходить через вершину x j , то (i -й, k-й) елемент матриці А 2 дорівнює числу шляхів довжини 2, що йдуть з x i вх k .

У таблиці 4.1a представлено матрицю суміжності графа, зображеного на рис. 4.2. Результат зведення матриці суміжності квадрат А 2 показаний в таблиці 4.1б.

Так "1", що стоїть на перетині другого рядка та четвертого стовпця, говорить про існування одного шляху довжиною 2 з вершини х 2 до вершин 4 . Справді, як бачимо в графіна рис. 4.2, існує такий шлях: a6, a5. "2" в матриці A 2 говорить про існування двох шляхів довжиною 2 від вершин 3 до вершин 6:a 8 , a 4 іa 10 , a 3 .

Аналогічно для матриці суміжності, зведеної в третій ступінь A 3 (таблиця 4.1в), a (3) ik дорівнює кількості шляхів довжиною 3, що йдуть від x i кх k . З четвертого рядка матриці A 3 видно, що шляхи довжиною 3 існують: один з 4 вх 4 (a 9 , a 8 , a 5), ​​один з 4 в

х 5 (a 9, a 10, a 6) і два шляхи з 4 вх 6 (a 9, a 10, a 3 і a 9, a 8, a 4). Матриця A4 показує існування шляхів довжиною 4 (таблиця 4.1г).

Таким чином, якщо a р ik є елементом матриці A р, то a р ik дорівнює числу шляхів (не обов'язково орцепів або простих орцепів) довжинир, що йдуть від x i кх k .

Завдань, у яких використовується поняття досяжності, досить багато. Ось одна з них. Граф може бути моделлю якоїсь організації, в якій люди представлені вершинами, а дуги інтерпретують канали зв'язку. При розгляді такої моделі можна поставити питання, чи може інформація від однієї особи х i бути передана іншій особі х j, тобто чи існує шлях, що йде від вершини х i до вершини х j. Якщо такий шлях існує, то кажуть, що вершина х j досяжна з вершини х i . Можна цікавитись досяжністю вершини х j з вершини х i тільки на таких шляхах, довжини яких не перевищують заданої величини або довжина яких менша за найбільшу кількість вершин у графі тощо завдання.

Досяжність у графі описується матрицею досяжності R=, i, j=1, 2, ... n де n – число вершин графа, а кожен елемент визначається наступним чином:

r ij =1 , якщо вершина х j досяжна з х i ,

r ij =0 , інакше.

Безліч вершин R(x i) графа G , досяжних із заданої вершини x i складається з таких елементів x j , для яких (i, j) -й елемент в матриці досягненьдорівнює 1. Очевидно, що всі діагональні елементи в матриці R дорівнюють 1, оскільки кожна вершина досяжна з самої шляхом довжини 0. Оскільки пряме відображення 1-го порядку Г +1 (x i) є безліччю таких вершин x j , які можна досягти з x i з використанням шляхів довжини 1, то безліч Г+(Г+1(xi)) = Г+2(xi)складається з вершин, досяжних з x i з використанням шляхів довжини 2. Аналогічно Г +p (x i) є безліччю вершин, які можна досягти з x i за допомогою шляхів довжини p .

Так як будь-яка вершина графа, яка досяжна з x i повинна бути досяжна з використанням шляху (або шляхів) довжини 0 або 1, або 2, ..., або p , то безліч вершин, досяжних для вершини x i , можна подати у вигляді

Як бачимо, безліч досяжних вершин R(xi) являє собою пряме транзитивне замиканнявершини x i , т. Е. R (xi) = T + (xi). Отже, для побудови матриці досяжності знаходимо досяжні безлічі R (x i) для всіх вершин . Вважаючи, r ij =1 якщо і r ij = 0 інакше.

Для графа, наведеного на рис. 4.1 ,а, безліч досяжностей знаходяться наступним чином:

Матриця досяжностімає вигляд, як показано на рис. 4.1, ст. Матрицю досяжностіможна побудувати по матриці суміжності (рис. 4.1 б), формуючи безлічі T + (x i) для кожної вершини x i .

Матриця контрдосяжності Q = [q ij], i, j = 1, 2, ... n, де n – число вершин графа, визначається так:

q ij =1 якщо з вершини x j можна досягти вершину x i ,

q ij =0 , інакше.

G(V,X) з петлями, але без кратних дуг задає бінарне відношення Х на множині V. Повний граф відповідає універсальному співвідношенню. Неорієнтований граф відповідає симетричному співвідношенню. Доповнення графа відповідає доповненню відношення. Зміна напряму дуг відповідає зворотному ставленню.

Орграфи та бінарні відносини один і той же клас об'єктів, описаних різними засобами. Бінарні відносини, функції є базовими засобами побудови переважної більшості математичних моделей, використовують для вирішення практичних завдань, а графи допускають наочне уявлення як діаграми. Це широко пояснює використання діаграм різного типу в кодуванні та проектуванні.

Вершина b орграфа (графа) G називається досяжноюз U в тому і тільки тому випадку, коли U = V або існує шлях (маршрут), що з'єднує U з V (U - початкова вершина, V - кінцева вершина). Отже на безлічі вершин орграфа (графа) визначено як відношення суміжності А, а й ставлення досяжності Т.

Матрицею досяжності Торграфа(графа) G називається T 2 n×n, елементи якої знаходяться з умови: 1, якщо можна досягти з ; 0, якщо не можна досягти з .

Визначення матриці досяжності орграфа як матриці рефлексивного та транзитивного замикання відношення суміжності.

Введене відношення досяжності на вершинах графа G(V,Х): вершина w досяжна з вершини v, якщо v = w або G є шлях з v в w. Інакше висловлюючись, досяжність є рефлексивним і транзитивним замиканням відносини суміжності.

Знайти матрицю суміжності, транзитивне та рефлексивне замикання.

Зв'язність у графах. Слабка, одностороння та сильна зв'язність в орграфах. Матриця зв'язності та сильної зв'язності. Компоненти зв'язності. Визначення матриці сильної зв'язності з урахуванням матриці досяжності.

G(V,Х) називається зв'язковимякщо будь-яка його вершина досяжна з будь-якої іншої вершини.

Орграф G(V,Х) називається односторонньо зв'язковим, якщо для будь-яких двох його вершин, крайня мене одна досяжна з іншої.

Орграф G(V,Х) називається сильно зв'язковимякщо будь-яка його вершина досяжна з будь-якої іншої.

Орграф G(V,Х) називається слабо зв'язковимякщо зв'язковим є відповідний йому не орграф, отриманий в результаті видалення орієнтації дуг.

Орграф, який не є слабо зв'язковим, називається нескладним.

Компонентом сильнодіючого зв'язкуорграфа G(V,Х) називається максимальне, за кількістю входження вершин сильнозв'язковий подграф даного орграфа. Аналогічно визначається компонента зв'язності не орграфа.

Матрицею сильної зв'язностіорграфа (графа) G(V,Х) називається S n×n, елементи якої знаходяться з умови: 1, якщо можна досягти з і досягнуто з ; 0, якщо не досягнуто з і не досягнемо з .

(орграф) сильнозв'язковим або зв'язковим, для цього достатньо визначити наявність 0 у матриці, якщо

0 ні, то граф (орграф) є зв'язковим (сильнозв'язковим) в іншому випадку немає.

Матриця сильної зв'язності може бути побудована з матриці досяжності за формулою

Нехай G = (X, Г) - граф модульної структури, х г, х-. -вершини, що належать X.Якщо у графі Gіснує орієнтований ланцюг від х, до Хрто вершина х,- - досяжна з вершини х,-. Справедливим є наступне твердження: якщо вершина Xjдосяжна з х, ах (- з Хрто X/досяжна з х^Доказ цього факту очевидний. Розглянемо бінарне ставлення на безлічі X,яке визначає досяжність між вершинами графа. Введемо позначення х, -> х, для досяжності вершини х, - з Xj.Ставлення транзитивне. Позначимо через Я(х,) безліч вершин графа G,досяжних з x; . Тоді рівність

визначає транзитивне замикання х стосовно досяжності.

Доведемо таку теорему.

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

Доведення.Припустимо, вершинах, (х,е X)недосяжна з Xj. Тоді х, е X/ і безліч X" = Xх), не порожньо. Оскільки обраний компонент графа пов'язаний, то є вершина х,- ех, і ланцюг /7(х; , xj),провідна від х, до х,-. Виходячи з ациклічності графа G,в X"повинен існувати простий ланцюг Н(х/, xj),де у вершину x fне входять дуги (даний ланцюг може бути порожнім, якщо X"складається лише з х,). Розглянемо ланцюг Я(х/, xj) = Н(х/, х,) U Я (х, xj).Це означає, що модуль x. досягнемо з вершин х, і Xjта обидві вершини не містять вхідних дуг. А це суперечить визначенню графа модульної структури з єдиною кореневою вершиною. Теорему доведено.

Основна вимога забезпечення досяжності - це відсутність неорієнтованих циклів у графі. Виходячи із графа на рис. 1.4, відзначаємо, що граф містить орієнтований цикл та модулі, що відповідають вершинам х 4, х 5,ж 6 ніколи не виконуватимуться. Таким чином, результати теореми 1.1 посилюють вимогу відсутності орієнтованих циклів у графі модулів.

Для аналізу матричного уявлення відношення досяжності графа модульної структури розглянемо граф матриці досяжності, наведеної на рис. 1.1.

Коефіцієнт а, у = 1, якщо модуль, що відповідає індексу /, досягнемо з модуля, відповідного індексу / i.Наступні результати ґрунтуються на відомій теоремі з теорії графів.

Рис. 1.4.

Теорема 1.2. Коефіцієнт ту l-йступеня матриці суміжності До визначає кількість різних маршрутів, що містять / дуг і що зв'язують вершину X/ свершиною ^-орієнтованого графа.

Розглянемо такі три наслідки з цієї теореми.

Наслідок 1.1.Матриця М = "? J M t,де М- матриця суміжності орієн-

тованого графа з пвершинами, збігається з точністю до числових значень коефіцієнтів з матрицею досяжності А.

Доведення.В орієнтованому графі, що містить пвершин, максимальна довжина шляху без дуг, що повторюються, не може перевищувати п.Тому послідовність ступенів матриці суміжності М 1 де i = 1,2,

я визначає кількість всіх можливих шляхів у графі з кількістю дуг п. Нехай коефіцієнт т 1)матриці Мвідмінний від нуля. Це означає, що існує ступінь матриці М>,у якої відповідний коефіцієнт т ()також відмінний від нуля. Отже, існує шлях, що йде від вершини Xjдо Хртобто. вершина ^ досяжна з х гДане слідство визначає зв'язок матриці викликів графа модульної структури, що збігається з матрицею суміжності А/, з матрицею досяжності Ата визначає алгоритм побудови останньої.

Наслідок 1.2.Нехай для деякого iу послідовності ступенів матриці суміжності М*існує коефіцієнт т Х1> 0. Тоді у вихідному графі існує орієнтований цикл.

Доведення.Нехай m (i > 0 для деякого I.Отже, Xjдосяжна з x vтобто. Існує цикл. Відповідно до теореми 1.2 даний цикл має / дуг (загалом повторюваних).

Наслідок 1.3.Нехай п-яступінь матриці суміжності М пациклічного графа збігається з нульовою матрицею (усі коефіцієнти дорівнюють нулю).

Доведення.Якщо граф ациклічний, то в ньому максимально простий шлях не може мати більше, ніж п- 1 дуг. Якщо в М пє коефіцієнт, відмінний від нуля, то повинен існувати шлях, що складається з пдуг. А цим шляхом може бути лише орієнтований цикл. Отже, всі коефіцієнти М пдля ациклічного графа дорівнюють нулю. Дане слідство надає необхідну та достатню умову відсутності циклів у графі модульної структури.

Для ациклічних графів відношення досяжності еквівалентно частковому строгому порядку. Транзитивність відношення досяжності розглянуто вище. Антисиметричність випливає з відсутності орієнтованих циклів: якщо вершина х)досяжна з x vто протилежне неправильно. Введемо позначення х х > Хрякщо вершина Xjдосяжна з вершини x v

Нехай G =(X, Г) - ациклічний граф, який відповідає певній модульній структурі. Розглянемо убутний ланцюг елементів частково впорядкованої множини X:

де через знак ">" позначено відношення досяжності. Оскільки Xзвичайно, то ланцюг обривається х п > x i2 > ... > x in.Вершина x jnнемає вихідних дуг, тобто. елемент x inмінімальний (йому відповідає модуль, який містить звернення до іншим модулям). Максимальний елемент у множині X – коренева вершина.

• Доказ цієї теореми наводиться у роботі (книга): Лаврищева Є. М., Грищенко В. Н. Складальне програмування. Київ: Наукова думка, 1991. 287 с.

Досяжність і зв'язність у графіках План лекції: Маршрути ланцюга і цикли. Зв'язність графа та компоненти зв'язності. Діаметр радіусу і центр графа.

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

Баранов Віктор Павлович. Дискретна математика. Розділ 3.Графи, мережі, коди.

Лекція 8. Досяжність та зв'язність у графах

лекція 8. ДОСЯГНІСТЬ І ЗВ'ЯЗНІСТЬ У ГРАФАХ

План лекції:

1. Маршрути, ланцюги та цикли.
2. Зв'язність графа та компоненти зв'язності.
3. Діаметр, радіус та центр графа.
4. Матриці досяжності та контрадостижимості.

1. Маршрути, ланцюги та цикли

Орієнтованим маршрутом(або шляхом ) орграф називається послідовність дуг, в якій кінцева вершина будь-якої дуги, відмінною від останньої, є початковою вершиною наступної. На рис. 1 послідовність дуг

, (1)

, (2)

(3)

є шляхами.

Рис. 1.

Орієнтованим ланцюгом(або орцепью ) називається шлях, в якому кожна дуга із користується не більше одного разу. Так, наприклад, шляхи (2) та (3) є орцепями, а шлях (1) не є таким, оскільки дуга в ньому використовується двічі.

Простий називається орцепь, в якій кожна вершина використовується не більше одногоо го разу. Наприклад, орцепь (3) є простий, а орцепь (2) ні.

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

Аналогічно тому, як ми визначили орцепи та прості ланцюги, можна визначити ланцюги та прості ланцюги.

Шлях або маршрут можна також зображувати послідовністю вершин. Напр.і мір, шлях (1) можна записати як: .

Шлях називається замкнутим якщо в ньому початкова вершина дуги збігається з конемгод ної вершиною дуги. Замкнуті орцепи (ланцюги) називаютьсяорциклами (циклами ). Орцикли називають такожконтурами . Замкнуті прості орцепи (ланцюги) зввиються простими орциклами(Циклами). Замкнутий маршрутє неорієнтовноюн ним двійником замкнутого пу ти.

1. Зв'язність графа та компоненти зв'язності

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

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

° ° °

° ° ° ° ° °

° ° ° ° ° °

а Б В

Рис. 2.

Орграф називаєтьсяодносторонньо зв'язковимабо одностороннім якщо в будь-якій парі його вершин хоча б одна досяжна з іншої. Приклад одностороннього графа наведено на рис. 2 б. У цьому графі є орцикл, що включає чотири взаємно досяжні вершини. Вершина має нульовий ступінь заходу, а це означає, що не існує шляхів, що ведуть до цієї вершини. При цьому з досяжна кожна з чотирьох інших вершин.

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

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

Для орграфа визначено три типи компонентів зв'язності:сильна компонентаМак до симально сильний підграф,одностороння компонентамаксимальний односто ронний підграф іслабка компонента¦ максимально слабкий подграф.

Поняття сильної компоненти ілюструє рис. 3.

° ° ° ° ° °

° ° ° °

° ° ° ° ° °

° ° ° ° ° °

° ° °

° ° ° ° °

Рис. 3

Граф, який є односторонньо зв'язковим, містить шість сильних под графів, з яких тільки і є сильними компонін ними. Аналогічно ілюструється поняття однобічної компоненти. У цьому приме ре одностороння компонента збігається із самим графом. Якщо ж змінити орієнта цію дуги, наприклад, на протилежну, то отримаємо слабкий граф з двома односто ронними компонентами, одна з яких утворена вершинами, а інша вер шинами.

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

Графи є зв'язковими та у сумі дають граф. Ці графи називаютьсякомпонентами зв'язностіграфа. Число ще одна числова характеристика графа. Для зв'язкового графа, якщо граф незв'язний, то.

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

1. Діаметр, радіус та центр графа

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

2) ;

3) .

Визначимо відстань від кожної вершини графа до найдальшої від неї вершини

яке називаєтьсяексцентриситетом. Вочевидь, що ексцентриситет всім вершин у повного графа дорівнює одиниці, а вершин простого циклу .

Максимальний ексцентриситет має назвудіаметра графа, а мінімальний |радіусу графа. У повному графі маємо, а в простому циклі.

Вершина називається центральною, якщо. Граф може мати кількаь до таких вершин, а деяких графах всі вершини є центральними. У простому ланцюгу при непарному числі вершин тільки одна є центральною, а при парному їх чиз ле таких вершин дві. У повному графі та для простого циклу центральними є всі вершини. Безліч центральних вершин називаєтьсяцентр графа.

приклад 1. Знайти діаметр, радіус та центр графа, наведеного на рис. 4.

° °

° ° °

° °

° °

Рис. 4.

Для вирішення цього завдання зручно заздалегідь обчислитиматрицю відстанейміж вершин а ми графа. В даному випадку це буде матриця розміром, в якій на місці стоїть відстань від вершини до вершини:

Для кожного рядка матриці знаходимо найбільший елемент і записуємо його спра ва від рисочки. Найбільше з цих чисел дорівнює діаметру графа, найменше |а діус графа. Центр графа становлять центральні вершини та.

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

1. Матриці досягнень і контрадостижимостей

Матриця досягненьвизначається так:

Безліч вершин графа, досяжних із заданої вершини, складається з таких елементів, для яких елемент у матриці дорівнює 1. Це безліч можна представити у вигляді

Матриця контрадостижимостей (зворотних досягнень) Визнач я ється так:

Аналогічно побудові досяжної множини можна сформувати мно ство, використовуючи наступне вираз:

З визначень випливає, що стовпець матриці збігається з рядком мат риці, тобто , де матриця, транспонована до матриці.

приклад 2. Знайти матриці досяжностей і контрадостижимостей для графа, прі веденого на рис. 5.

Рис. 5.

Визначимо безліч досягнень для вершин графа:

Отже, матриці досяжностей і контрадостижимостей мають вигляд:

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

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

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