Дискретна математика

43. Позн чені і непозн чені гр фи.

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

Означення. Нехай V — не порожня множина. Пара (V, Е), де Е – довільна підмножина множини V2, називається графом (неорієнтованим графом). Елементи множини V називаються вершинами графа, а елементи множини Е - ребрами.

Отже, відповідно до цього означення граф - це скінченна множина V вершин і скінченна множина Е ребер такі, що Е V2. Множини вершин і ребер графа G позначаються в цьому випадку символами VG і EG відповідно. Вершини і ребра графа називаються його елементами. Число |VG| вершин графа G називається його порядком і позначається через |G|. Якщо |G| = n, |EG| = m, то G називають (n,m)-графом.

Легко підрахувати число всіх графів з фіксованою множиною вершин V. Ці графи розрізняються своїми ребрами, і тому їхнє число дорівнює кількості підмножин у V2, тобто 2k, де k = n(n – 1)/2, n = |V|. Однак ці графи не завжди варто розрізняти. Як у застосуваннях теорії графів, так і в самій цій теорії частіше істотно лише те, що є об'єкти (вершини графа) і зв'язки між цими об'єктами (ребра). З цих позицій графи, що утворюються один з іншого зміною найменувань вершин, розумно не розрізняти. Це приводить до поняття ізоморфізму графів.

Означення. Нехай G і H - графи, а : VG VH - бієкція. Якщо для будь-яких вершин u і v графа G їхні образи (u) і (v) суміжні в Н тоді і тільки тоді, коли u і v суміжні в G, то ця бієкція називається ізоморфізмом графа G на граф Н. Якщо такий ізоморфізм існує, то ми пишемо G Н (тоді і Н G) і говоримо, що графи G і Н ізоморфні.

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

Рис.3.1

Рис.3.2 Очевидно, що відношення ізоморфізму графів є відношенням еквівалентності, тому що воно

симетричне, транзитивне і рефлексивне. Отже, множина усіх графів розбивається на класи еквівалентності: графи з одного класу попарно ізоморфні; графи з різних класів не ізоморфні. Ізоморфні графи природно ототожнювати, вважати співпадаючими, тому що їх можна зобразити одним рисунком. Вони могли б розрізнятися конкретною природою своїх елементів, але саме це ігнорується при введенні поняття «граф» описаним вище другим способом.

У деяких ситуаціях усе-таки доводиться розрізняти ізоморфні графи, і тоді використовується «вершинно-позначений граф». Граф порядку n називається вершинно-позначеним, якщо його вершинам присвоєні деякі позначки, наприклад, номери 1,2,...,n. Ототожнивши кожну з вершин графа з її номером (і, отже, множину вершин - з множиною чисел (1,2,...,n), визначимо рівність вершинно-позначених графів G і Н того самого порядку: G = Н тоді, коли EG = EH. На рис.3.3 зображені три різних вершинно-позначених графи.

Рис.3.3 При необхідності підкреслити, що розглянуті графи розрізняються лише з точністю до ізоморфізму,

говорять: «абстрактний граф». Строго говорячи, абстрактний (чи непозначений) граф - клас ізоморфних графів. Число gn непозначених графів порядку n визначається складно. Відома формула Пойа

gn 2k / n!,

що дає асимптотику числа gn. Тут k визначається як і в описаному вище випадку непозначених графів. Ця формула означає, що дві функції g(n) = gn і f(n) = 2k/n! асимптотично рівні, тобто lim g(n)/f(n) = 1.

n

Отже, число вершинно-позначених графів порядку n «приблизно» у n! раз більше числа непозначених. Цей факт здається інтуїтивно ясним: існує рівно n! позначень множини, що складає з n

51

вершин. Однак, не треба думати, що з кожного непозначеного графа виходить n! вершинно-позначених. Наприклад, усі позначки порожнього графа приведуть до одного і того ж позначеного графу; простий ланцюг Рз породжує три, а не шість позначених графів (рис. 3.3). Але все-таки, як правило, кожен непозначений граф приводить до n! вершинно-позначених графів.

Якщо ми хочемо розрізняти конкретну природу елементів графа, причому не тільки вершин, але і ребер, що ігнорується при введенні поняття «граф» описаним вище другим означенням графів, то тоді будемо застосовувати перше з означень, що дозволяє позначати і вершини, і ребра. Особливо справедливо це для мультиграфів, у означенні яких по другому способу Е уточнюється не як довільна підмножина множини V2, а як сім‘я підмножин множини V2. Саме це уточнення дозволяє формально допустити паралельні (кратні) ребра в мультиграфах. Але це аж ніяк не дозволяє розрізняти ці ребра, як це дозволяє реалізувати перше з означень графів.

44. Ступені вершин гр фів т їх вл стивості.

Уведемо важливе для аналізу властивостей графів поняття ступеня вершини і розглянемо деякі важливі властивості графів, обумовлені ступенями.

Означення. Число інцидентних вершині vi ребер будемо називати ступенем вершини і позначати d(vi). Вершину з нульовим ступенем назвемо ізольованою, а зі ступенем рівним 1, - висячою. Ребро, інцидентне висячій вершині, також називається висячим.

d(v1) = 1, отже вершина v1 - висяча;

d(v2) = 3, d(v3) = 3, d(v4) = 3;

d(v5) = 0, отже вершина v5 – ізольована.

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

Легко помітити, що для розглянутих у прикладах графів: а) сума ступенів вершин дорівнює 2m, де m - число ребер графа; б) число вершин непарного ступеня парне.

Виявляється сума ступенів завжди вдвічі більша числа ребер будь-якого графа, а кількість вершин непарного ступеня парна в будь-якому графі. Справедлива наступна

Теорема 3.1. У будь-якому графі :

а) сума ступенів вершин дорівнює 2m, де m - число ребер графа;

б) число вершин непарного ступеня парне.

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

б) нехай число вершин n. Нехай перші r вершин v1,…,vr мають парні ступені, а інші n- r вершин vr+1,…,vn - непарні. Очевидно, це не порушує загальності. Справедливо, що:

Відповідно до пункту а) уся сума в (1) парна. Тому що сума парних чисел парна, то й перший доданок у правій частині (1) парний. Тоді другий доданок у правій частині (1) повинен бути також парним.

52

Але другий доданок – сума непарних елементів. Таким чином, число цих доданків повинне бути парним.

Теорема доведена.

45. Гр фи і підгр фи.

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

Означення. Граф G′ = (V′, E′, Θ΄) називається підграфом графа G = (V, E, Θ), якщо множини V′ і E′ є підмножинами, відповідно, множин V і E такими, що ei E΄, функція Θ визначена для ei і має значення, що збігається зі значенням функції Θ(ei) = (vk, vl), тільки в тому випадку, якщо vk і vl належать множині V΄. Якщо множина E′ - власна підмножина множини Е чи множина V′ - власна підмножина множини V, то граф G′ назвемо власним підграфом графа G. Якщо усі вершини графа G присутні в графі G′ , то граф G′ назвемо кістяковим підграфом графа G.

Скористаємося геометричним способом задання графів для того щоб про демонструвати наочно особливості підграфів.

Приклад 3. Задамо граф і виділимо його власний і кістяковий підграфи.

підграфи

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

Означення. Повним графом назвемо простий граф, у якому кожна пара вершин суміжна.

Очевидно, якщо в повному графі n вершин, то він містить n(n-1)/2 ребер.

Приклад 4. Повні графи на одній (K1), двох (K2), трьох (K3), чотирьох (K4) і п'яти (K5) вершинах.

Знаючи особливості повних графів, легко зрозуміти наступне

Означення. Граф G = (V, E′, Θ′΄) назвемо доповненням простого графа G = (V, E, Θ), якщо ребро (vi,vj) міститься в множині E′ у тому і тільки в тому випадку, якщо воно не міститься в множині Е.

Приклад 5. Задамо граф і його доповнення.

53

Інакше кажучи, додатковий граф (чи доповнення) довільного простого графа G має ту ж множину вершин і будь-які дві різні вершини суміжні в доповненні тоді і тільки тоді, коли вони не суміжні в G.

Очевидно, що доповнення до доповнення графа G дорівнює графу G і Н G, якщо Н G. Граф, ізоморфний своєму доповненню, називається самододатковим. Наприклад, К1 – самододатковим граф. Самододаткові графи складають важливий клас графів, які використовуються зокрема при вирішенні проблеми розпізнавання ізоморфізму графів.

46. М ршрути, цикли, компоненти зв'язності в гр ф х.

Важлива частина проблем теорії графів пов'язана з аналізом можливості переходу по ребрах графа з однієї визначеної вершини (підмножини вершин) в іншу визначену вершину (підмножину вершин).

Означення. Маршрутом у графі називається скінченна послідовність вершин і ребер v0, e1, v1, e2,…,vk- 1,ek,vk, що чергуються, що починається і закінчується вершинами, причому vi-1 і vi є кінцевими вершинами ребра ei, 1≤ i ≤k. Говорять, що маршрут v0, e1, v1, e2,…,vk-1, ek,vk з'єднує вершини v0 і vk чи веде з вершини v0 у вершину vk .

Маршрут v0, e1, v1, e2,…,vk-1,ek,vk іноді будемо називати (v0,vk)-маршрутом. Довжина маршруту – число його ребер.

Частіше використовуються окремі види маршрутів, яким властиві певні корисні для вирішення окремих проблем особливості. Зведемо їх у наступне

Оначення. Маршрут називається ланцюгом, якщо всі його ребра різні. Маршрут називається відкритим, якщо вершини v0 і vk не співпадають. Маршрут називається замкнутим, якщо вершини v0 і vk співпадають. Замкнутий ланцюг називається циклом. Замкнутий ланцюг називається простим циклом, якщо різні всі його вершини, крім v0 і vk (прості цикли на n вершинах іноді позначаються Cn). Відкритий ланцюг називається шляхом чи простим ланцюгом, якщо всі його вершини різні (прості ланцюги на n вершинах іноді позначаються Pn).

Довжина маршруту природним чином переноситься на шлях, цикл, ланцюг. Приклад 6. Нехай граф заданий геометрично:

e1

Означення. Граф G називається зв‘язним, якщо в ньому існує шлях між кожною парою вершин. Нехай граф G = (V, E, Θ) – не зв'язний. Тоді множину його вершин V можна розбити на підмножини

V1,…,Vp такі, що між будь-якими двома вершинами підмножини Vi, i=1,…,p існує шлях, а ніяка вершина підмножини Vi не зв'язана ні з якою вершиною підмножини Vj, i j. Підграфи на підмножинах Vi, i=1,…,p називаються компонентами зв‘язності (компонентами) графа. Очевидно, зв'язний граф G має тільки один компонент зв‘язності, що є графом G.

54

Приклад 7. Приклад графа G, що складається з п'яти компонентів зв‘язності G1, G2, G3, G4 і G5.

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

Означення. Нехай v0, e1, v1, e2,…,vk-1,ek,vk – якийсь (v0, vk)- ланцюг у графі G. Тоді будь-яка його частина vi, ei+1, vi+1,…,vj-1,ej,vj, що починається з вершини vi і закінчується у вершині vj, називається підланцюгом чи (vi, vj)-підланцюгом (v0, vk)-ланцюга.

Очевидна наступна Теорема 3.2. Для зв‘язності графа необхідно і досить, щоб у ньому для якої-небудь фіксованої

вершини vr і кожної іншої вершини vq існував (vr,vq)-шлях.

Компоненти зв‘язності можна визначити і за допомогою підграфів. Усякий зв'язний підграф графа G, що не є власним підграфом іншого зв'язного підграфа графа G, називається компонентом зв’язності (зв'язним компонентом чи просто компонентом) графа G. Множина вершин зв'язного компонента називається областю зв’язності графа.

Уведемо ряд важливих характеристик зв'язного графа G = (V, E, Θ).

Означення. Довжина найкоротшого шляху між парою вершин vr і vq називається відстанню між вершинами vr і vq і позначається d(vr,vq).

Прийнявши d(vr,vr) = 0, можна переконатися, що уведена відстань задовольняє аксіомам метрики. Означення. Граф Gk, де k – натуральне число, називається k-м ступенем графа G, якщо V - його

множина вершин, а незбіжні вершини vr і vq суміжні тоді і тільки тоді, коли для графа G виконується умова d(vr,vr) k.

Означення. Для фіксованої вершини vr максимальна з усіх її відстаней до інших вершин графа G називається ексцентриситетом вершини vr і позначається e(vr).

Означення. Максимальний із всіх ексцентриситетів вершин графа G називається діаметром графа G і позначається d(G).

Означення. Вершина vr називається периферійною, якщо e(vr) = d(G).

Означення. Мінімальний із всіх ексцентриситетів вершин графа G називається радіусом графа G і позначається r(G).

Означення. Вершина vr називається центральною, якщо e(vr) = r (G). Множина центральних вершин графа G називається центром графа G.

47. Опер ції н д гр ф ми, спеці льні гр фи.

Нехай задані графи G1 = (V1, E1, Θ1) і G2 = (V2, E2, Θ2).

Означення. Граф G = (V, E, Θ) назвемо об'єднанням G1 G2 графів G1 і G2, якщо V=V1 V2, E= E1 E2, а функція Θ визначена для ei E і дорівнює Θ1, якщо ei належить E і E1, і дорівнює Θ2, якщо ei належить E і E2.

Означення. Якщо G = (V, E, Θ) граф, то граф G-vi назвемо породженим операцією вилучення вершини vi, якщо він отриманий вилученням вершини vi і всіх ребер, інцидентних цій вершині.

55

Приклад виконання операції наведений нижче.

Означення. Якщо G = (V, E, Θ) граф, то граф G-ei отримується вилученням ребра ei без вилучення його кінцевих вершин.

Тепер розглянемо приклади виконання введених операцій.

Прикл д 10. Граф G і графи, отримані вилученням вершини і ребра. e 2

Означення. Будемо говорити, що пара вершин vi, vj у графі G замикається, якщо вони заміняються такою новою вершиною vk, що всі ребра в G, інцидентні vi чи vj, стають інцидентними новій вершині vk. Під стягуванням будемо розуміти вилучення ребра і замикання його кінцевих вершин.

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

Легко показати, що будь-який непорожній зв'язний граф, відмінний від K1, є таким, що стягується до K2. Але вже нестягуваність шляху на n 3 вершинах до K3 показує, що не будь-який зв'язний граф з n 3 є таким, що стягується до K3.

Означення. Граф H називається отриманим операцією включення вершини v у ребро e графа G, якщо граф H виходить із графа G вилученням ребра e і додавання вершини v і двох ребер, що з'єднують вершину v з вершинами vi і vj такими, що в графі G Θ(e) = (vi, vj).

48. Вл стивості опер цій н д шлях ми, цикл ми, компонент ми.

Сутність введених об'єктів прояснюється після аналізу властивостей результатів виконання над ними операцій над графами.

Теорема 3.3. При u ≠ v усякий (і,v)- маршрут містить простий (і,v)- ланцюг.

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

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

Властивості результатів теоретико-множинної операції об'єднання шляхів характерризує наступна

56

Теорема 3.5. Нехай Р = (v0, e1, v1, e2,…,vk-1,ek,vk) і Р = (v 0, e 1, v 1, e 2,…,v t-1,e t,v t) - незбіжні шляхи,

причому v0 = v 0 = v, vk = v t = u, Р Р . Об'єднання Р и Р містить простий цикл.

Доведення. Нехай vr і v s - перші, рахуючи від v, з неспівпадаючі вершини цих ланцюгів, vq і v p - перші зі співпадаючих вершин, що з‘являються після vr і v s. Очевидно, що такі вершини обов'язково знайдуться. Для vq і v p це випливає з того, що v0 = v 0 = v і Р Р . Для vr і v s у крайньому випадку знайдеться пара vk = v t = u. Тоді об'єднання (vr-1,vq)-підланцюга ланцюга Р и (v s-1, v p)-підланцюга ланцюга Р є простим циклом. Теорема доведена.

Властивості результатів теоретико-множинної операції об'єднання простих циклів характеризує наступна

Теорема 3.6. Якщо С і D - два неспівпадаючих простих цикли, що мають загальне ребро е , то граф (C U D)-e також містить простий цикл.

Доведення. Якщо ребро е інцидентне вершинам vr і vq, то С-e і D-e - незбіжні прості (vr,vq)-ланцюги. Тому необхідне є наслідком теореми 3.5. Теорема доведена.

Теорема 3.7. Кожен граф зображується у виді диз'юнктного об'єднання своїх зв'язних компонентів. Розкладання графа на зв'язні компоненти визначено однозначно.

Доведення. Нехай G = (V, E, Θ) - довільний граф. На множині V визначимо бінарне відношення ~, поклавши vr ~ vq для вершин vr і vq, якщо vr = vq чи в графі G існує (vr, vq)-шлях. Очевидно, що це відношення є відношення еквівалентності. Отже, воно визначає розбиття множині V на класи еквівалентності. Нехай {V1,…,Vp}– таке розбиття. Очевидно, що породжені на підмножинах розбиття підграфи і тільки вони є компонентами графа G. Тому що підмножини {V1,…,Vp} попарно не перетинаються, граф G – диз‘юнктне об'єднання компонентів. Теорема доведена.

Важливе співвідношення між зв‘язністю і доповненням установлює наступна Теорема 3.8. Для будь-якого графа або він сам, або його доповнення є зв‘язним.

Доведення. Нехай G - незв'язний граф, Gi - одна з його компонент зв‘язності, Gj = G\Gi. Тоді для будьяких vr з Gi і vq з Gj у додатковому графі графа G є ребро (vr,vq). Отже, довільна вершина з Gj з'єднана з vr шляхом довжини 1, а довільна вершина з Gi (відмінна від vr) з'єднана з vr шляхом довжини не більш ніж 2. Тепер з теореми 3.2 випливає, що доповнення графа G зв'язне. Теорема доведена.

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

Корисна також і наступна

Теорема 3.9. Нехай G = (V, E, Θ) - зв'язний граф, е E. Тоді:

1)якщо ребро е належить якому-небудь циклу графа G, те граф G-e зв'язний;

2)якщо ребро е не входить ні в який цикл графа G, те граф G-e має рівно дві компоненти. Доведення. 1). Нехай ребро е, інцидентне вершинам vr і vq, належить циклу C графа G. Замінивши в

кожнім (х,у)-шляху, що містить ребро е, підшлях (vr, е, vq) (vr, vq) - шляхом С-e, одержимо (х,у)-шлях, що не містить ребра е. Отже, у графі G будь-які дві незбіжні вершини з'єднані шляхом, що не проходить через ребро е. Але тоді і граф G-e зв'язний.

2). Нехай ребро е, інцидентне вершинам vr і vq, не входить ні в який цикл графа G. Тоді, напевне, вершини vr і vq належать різним компонентам, наприклад, Gi і відповідно Gj, графа G-e. Для довільної вершини х ≠ vr у G існує (х, vr)-шлях. Якщо ребро е в цей шлях не входить, х Gi. У протилежному випадку х Gj. Теорема доведена.

49. Дерев .

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

Означення. Граф назвемо ациклічним, якщо він не містить циклів. Означення. Деревом назвемо зв'язний ациклічний граф.

Означення. Деревом графа G назвемо зв'язний ациклічний підграф графа G. Кістяком графа G назвемо дерево графа G, що містить усі вершини графа G. Зв'язний підграф дерева T назвемо піддеревом дерева Т.

Теорема 3.11. Для графа G з n вершинами і m ребрами наступні твердження еквівалентні:

57

1)G-дерево;

2)існує тільки один шлях між будь-якими двома вершинами G;

3)G - зв'язний і m = n-1;

4)G – ациклічний і m = n-1;

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

що має рівно один цикл.

Доведення.

а) 1=>2. Нехай G – дерево й існує більш одного шляху між якимись двома вершинами. Але якщо є два шляхи, то це означає, що існує цикл, що суперечить означенню дерева. Обернене очевидне.

б) 2 => 3. G - зв'язний, тому що в ньому зв'язані будь-які дві вершини. Покажемо по індукції, що в

Індуктивне припущення. Нехай твердження виконується для графа з числом вершин меншим n. Нехай G утворений додаванням ребра е до G-e. Тоді це ребро повинне утворити єдиний зв'язок між своїми кінцевими вершинами, тобто в G-e не було зв'язку між ними, тобто G-e незв'язний, причому містить дві компоненти G1 і G2 інакше G буде незв'язний. Нехай для G1 – число вершин і ребер відповідно n1, m1; а для G2 – n2, m2. Тоді : n = n1+n2; m = m1+m2+1. Через те, що n1 < n і n2 < n, то індуктивне припущення для G1 і G2 справедливе, тобто:

m1 = n1-1 і m2 = n2-1, а отже m = n1-1+n2-1+1 = n-1. Обернене 3=>2 (с мостійно).

в) 3=>4. Нехай G0=G. Припустимо, що в G0 є цикл. Нехай G1=G-e1, де e1 одне з ребер циклу. Очевидно, що G1 залишається зв‘язним і містить усі n вершин, але m-1 ребер. Якщо G1 має цикли, то продовжимо операції вилучення доти, поки Gp не буде мати циклів. Тобто Gp з m-p ребрами буде зв‘язним і ациклічним. Але тоді Gp – дерево, а це означає, що число ребер у ньому n-1, тобто m-p = n-1. За припущенням, m = n-1. Тоді p = 0, тобто G = G0 – ациклічний граф. Обернене 4=>3 (с мостійно).

г) 4=>5. Нехай G1, G2,…,Gp – компоненти графа G; ni, mi – число вершин і ребер компоненти Gi. Тоді m = m1+…+mp; n = n1+…+np. Через те, що Gi зв'язана (за побудовою) і циклічна (тому що G циклічний), то Gi

– дерево і mi = ni-1. Тому :

Але, за припущенням, m = n-1, тобто p = 1, тобто в G один компонент, а це означає, що G зв'язний. А тому що він і ациклічний, то G дерево. Тоді між будь-якими vi і vj існує єдиний шлях і, отже, якщо додати ребро (vi, vj), то тоді воно зі шляхом утворять єдиний цикл. Обернене 5=>4 (с мостійно).

д) 5=>1. Нехай G – незв'язний. Але тоді vi і vj, якщо вони в різних компонентах і їх зв'язати не утворять цикл. А це суперечить припущенню. Отже, G - зв'язний, а тому що він за умовою ще й ациклічний,

то G - дерево. Теорема доведена.

Варто зазначити, що обернені доведення пунктів а), б), в), г) теореми зайві. Означення. k- деревом назвемо ациклічний граф, що складається з k компонентів.

Означення. Лісом графа G назвемо кістякове k-дерево графа G, де k - число компонентів у графі G. Означення. Рангом (G) графа G назвемо число n-k, де n - число вершин, а k - число компонентів

графа G. Цикломатичне число (G) графа G визначається, як m-n+k, де m - число ребер графа G.

Очевидно, (G)+ (G)=m.

50. Розділяючі множини т розрізи в гр ф х.

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

зпристроєм, системою, якщо якийсь чи якісь складові (елементи, деталі) їх вийдуть з ладу. Це питання - одне

зосновних у сучасній теорії системної надійності. Аналіз системної надійності пов'язаний з побудовою надійних схем, що є графами певного виду. Пристрій чи система, як відомо з теорії систем, виконують функцію, що не зможе виконати жоден з їхніх елементів. З'єднаємо елементи, вихід з ладу одного з яких, виводить з ладу систему (пристрій), послідовно; а елементи, вихід з ладу одного з яких не виводить з ладу систему (пристрій), паралельно. Вихід з ладу системи (пристрою) – це неможливість виконувати її функцію. Тоді одержуємо те, що називається надійнісною схемою у вигляді графа.

Приклад 15. Комп'ютер повинен обчислювати, вводити і виводити інформацію. Тоді, якщо в його складу входять: 1 процесор (ЦП), 1 оперативна пам'ять (ОП), 2 канали (ДО1 і ДО2), до обох з яких приєднано 2 пристрої вводу/виводу (УВВ1 і УВВ2), то надійнісну схему можна зобразити у вигляді:

58