Граф називається зв'язковим, якщо будь-які дві його неспівпадаючі вершини з'єднані маршрутом. Очевидно, що для зв'язності графа необхідно і достатньо, щоб у ньому для якої-небудь фіксованою вершини u і кожної іншої вершини v існував (u, v)-маршрут. p> Властивості маршрутів, ланцюгів і циклів:
1) Всякий незамкнутий (u, v)-маршрут, містить в собі просту (u, v)-ланцюг. Зокрема, будь-яка (u, v)-ланцюг, містить в собі просту (u, v)-ланцюг. Причому, якщо (u, v)-маршрут містить в собі вершину w (w? u і w? v), то в загальному випадку, проста (u, v)-ланцюг може не містити в собі вершину w. p> 2) Всякий непростий цикл можна розбити на два або більше простих. Причому для замкнутого маршруту таке твердження не вірно. p> 3) Всяка непроста (u, v)-ланцюг, може бути розбита на просту (u, v)-ланцюг і один або більше простих циклів. Причому для незамкнутого маршруту таке твердження не вірно. p> 4) Для будь-яких трьох вершин u, w, v з існування (u, w)-ланцюга їх і (w, v)-ланцюга, слід існування (U, v)-ланцюга. Причому може не існувати (u, v)-ланцюга, що містить вершину w. p> 5) Об'єднання двох незбіжних простих (u, v)-ланцюгів містить простий цикл. p> 6) Якщо граф містить 2 незбіжних циклу із загальним ребром e, то після видалення цього ребра граф як і раніше містить цикл. p> Якщо два графа ізоморфні:
1) то вони одного порядка;
2) у них однакове кількість ребер;
3) для довільного i, 0? i? n-1, (N - порядок графів) кількість вершин ступеня i, у обох графів однакове;
4) у них збігаються обхвати;
5) у них однакове кількість простих циклів мінімальної довжини (по кількості ребер).
Число ребер маршруту - його довжина. Ейлером цикл - цикл графа, що містить всі його ребра. Ейлеров граф - граф, що має Ейлеров цикл. p> Теорема. Мультіграф володіє ейлеровой ланцюгом тоді і тільки тоді, коли він зв'язний і число вершин непарного ступеня одно 0 або 2. Гамільтонів цикл - простий цикл, що проходить через всі вершини. p> ОРІЄНТОВАНИЙ МАРШРУТ ДОВЖИНИ k в орграфе з v у w у орграфе G = (V, E) - послідовність дуг виду (v, w1), (w1, w2), (w2, w3), ..., (wk-1, w), т . е. кінець кожної дуги, крім останньої, збігається з початком наступного. Для спрощення маршрут зручно представляти послідовністю вершин, які його представляють, проте слід пам'ятати про однаковому напрямку дуг, що входять у маршрут: v, w1, w2, w3, ..., wk-1, w.
ОРІЄНТОВАНА ЛАНЦЮГ (ШЛЯХ) - це орієнтований маршрут, в якому всі дуги різні. p> Маршрут називається Циклічні, якщо його початок і кінець збігаються. p> Циклічний шлях називається КОНТУРОМ.
Вершина w досяжні з v, якщо існує (v, w) - шлях. Орграф називається зв'язковим, якщо існують шляхи для всіх пар різних вершин графа. Матриця зв'язку, зв'язності, досяжності C = A (R *) визначається аналогічно графам. Зауважимо, однак, що для орграфов відношення R * НЕ Є СТАВЛЕННЯМ ЕКВІВАЛЕНТНОСТІ на V і, отже, не здійснює розбиття V!
Нехай В«D - безліч всіх орграфов, аВ« G - безліч всіх графів.
Ми можемо визначити відображення В«F:В« D ГЁ В«G наступним чином.
Нехай G = (V, E) in В«D. Тоді безліч вершин F (G) in В«G збігається з V, а безліч дуг F (G) визначається застосуванням таких операцій на E:
a) видаляються всі петлі з Е;
б) (v, w) замінюються на [v, w] для всіх (v, w) in E.
Тоді F (G) є графом, пов'язані з орграфом G.
Для орграфов поняття зв'язності є більш змістовним, ніж для графів. Розрізняють три важливих типу зв'язності орграфа:
а) G СИЛЬНО зв'язний, якщо для кожної пари різних вершин v, w in V існує маршрут з v у w і назад.
Б) G односторонньому зв'язний, якщо для кожної пари різних вершин v, w in V існує маршрут з v у w або назад.
В) G СЛАБКО зв'язний, якщо граф F (G) зв'язний;
Очевидно, що справедливо слідування:
G сильно зв'язний ГЁ G односторонньо зв'язний ГЁ G слабко зв'язний.
В) + Г v2Гџ + б) + Г v2Г + а) + Г v2Г +
v1 v3 v1 v3 v1Гџ --- v3
У термінах матриці зв'язності C = A (R *) орграф G сильно зв'язний тоді і тільки тоді, коли Cij = 1 для всіх I, j in Nn; G односторонньо зв'язний тоді і тільки тоді, коли Cij = 1 або Cji = 1 для всіх I, j in Nn.
Затвердження
Орграф є сільносвязний тоді і тільки тоді, коли в ньому є остовно циклічний маршрут.
Якщо G = (V, E) - орграф, те можна розбити V шляхом визначення відносини еквівалентності RO наступним чином: vROw, якщо v = w або існують маршрути з v у w і назад. Якщо {Vi: I in Np} - розбиття V і {Ei: I in Np, а Ei = (Vi * Vi) П E} є відповідними множинами дуг, то підграфи Gi = (Vi, Ei), I in Np називаються СИЛЬНО зв'язних компонентів G.
Очевидно, що RO <= R * і A (RO) може бути визначено з A (R *) як A (RO) ij = A (R *) ij & A (R *) ji (& - символ операції кон'юнкції); граф G зв'язний тоді і тільки тоді, кол...
