Page 100 - 4496

2. В G вершини a і b ланцюгом не пов'язані, тоді в
розширеному графі G’ зменшиться на одиницю число
компонент зв’язаності, тобто m’=m+1, p’ = p -1,  ’= .
Для будь-якого графа проробимо таку процедуру:
вилучимо з нього всі ребра й потім уведемо їх по одному. Для
графа без ребер твердження теореми вірно (число циклів і
число ребер рівно 0, число вершин дорівнює числу компонент
зв’язаності). Кожне нове ребро буде приводити до описаних
вище двом випадкам, тобто буде виконуватися твердження
теореми.
Якщо графу зіставити електричну мережу, то  –
найбільше число незалежних різниць потенціалів у мережі
між її вузлами,  – число незалежних колових струмів, які
можуть протікати в цій мережі.

3.18 Операції над графами

Так як граф описує бінарне відношення, то всі операції
над бінарними відношеннями можна трактувати як операції
над графами, у тому числі й теоретико-множинні операції:
доповнення, перетинання, об'єднання. Доповнення
проводиться до повного графа й включає в результат усі дуги,
яких немає у вихідному графі.
Розглядаються спеціальні «графові» операції.
Реберний граф графа G. У ньому кожному ребру G
зіставляється вершина, вершини зв'язуються ребром, якщо в G
зіставлені їм ребра інцидентні.
Граф досяжності графа G. У ньому множина вершин
така ж, що в G, і вершини пов'язані дугою, якщо в графі G між
ними існує шлях. У табл. 3.3 і 3.4 наведені матриці суміжності
графа доповнення й реберного графа для графа, наведеного на
рис.3.18.

97