юг, може бути розбита на просту (u, v) -ланцюг і один або більше простих циклів. Причому для незамкнутого маршруту таке твердження не вірно.
) Для будь-яких трьох вершин u, w, v з існування (u, w) -ланцюга їх і (w, v) -ланцюга, слід існування (u, v) -ланцюга. Причому може не існувати (u, v) -ланцюга, що містить вершину w.
) Об'єднання двох незбіжних простих (u, v) -ланцюгів містить простий цикл. 6) Якщо граф містить 2 незбіжних циклу із загальним ребром e, то після видалення цього ребра граф раніше містить цикл.
Якщо два графа ізоморфні: 1) то вони одного порядку; 2) у них однакова кількість ребер; 3) для довільного i, 0? I? N - 1, (n - порядок графів) кількість вершин ступеня i, в обох графів однакове; 4) у них збігаються обхвати; 5) у них однакова кількість простих циклів мінімальної довжини (за кількістю ребер).
Граф називається зв'язковим, якщо будь-які дві його неспівпадаючі вершини з'єднані маршрутом. Очевидно, що для зв'язності графа необхідно і достатньо, щоб у ньому для якої-небудь фіксованої вершини u і кожної іншої вершини v існував (u, v) -Маршрут.
Теорема. Граф G=(V, E) зв'язний тоді і тільки тоді, коли безліч його вершин не можна розбити на два непустих підмножини V1 і V2 так, щоб обидві граничні точки кожного ребра перебували в одному й тому самому безлічі.
Всякий максимальний зв'язний підграф графа G називається зв'язковий компонентою (або компонентою) графа G. Слово максимальний означає максимальний щодо включення, тобто не містити в зв'язковому підграфі з великим числом елементів. Безліч вершин зв'язковий компоненти називається областю зв'язності.
Для орієнтованого графа вводиться поняття орієнтованого маршр-та - це послідовність виду (1), в якій ei=(vi, vi + 1). Аналогом ланцюга в цій ситуації служити шлях (орієнтована ланцюг). Аналогом циклу служить контур (орієнтований цикл).
Орграф називається сільносвязний, якщо будь-які дві його вершини досяжні одне з одного. Орграф називається одностороннесвязним, якщо для будь-якої пари його вершин принаймні одна досяжна з іншої. Орграф називається сла-босвязним, якщо будь-які дві вершини його заснування з'єднані маршрутом. Орг-раф називається незв'язним, якщо основу незв'язних псевдографів.
Теорема. Орграф є сільносвязний тоді і тільки тоді, коли в ньому є остовно циклічний маршрут.
Необхідність. Нехай G - сільносвязний орграф і T=(v0, x1, v1, ..., xn, v0) - його циклічний маршрут, що проходить через максимально можливе число вершин. Якщо цей маршрут не є остовне, то візьмемо поза його вершину v. Так як G - сільносвязний орграф, то існують маршрути T1=(v0, y1, ..., v), T2=(v, z1, ..., v0). Але тоді циклічний маршрут T=(v0, x1, v1, ..., xn, v0, y1, ..., v, z1, ..., v0) містить більше число вершин, ніж T, що суперечить вибору маршру-та T. Отже, T - остовно маршрут.
Достатність. Нехай u і v - дві довільні вершини орграфа G, а T=(v0, x, ..., v, y, ..., u, z, ..., v0) - циклічний маршрут. Тоді u досяжна з v спомо-могою маршруту (v, y, ..., u) - частини маршруту T, - а v з u - за допомогою маршруту (u, z, ..., v0, x, ... , v) .3
Теорема. Орграф є одностороннесвязним тоді і тільки тоді, коли в ньому є остовно маршрут.
Теорема. Орграф є слабозв'язаних тоді і тільки тоді, коли в його основу є зв'язний псевдографів.
сільносвязний компонентою орграфа називається його максимальний щодо включення сільносвязний подграф
. Метричні характеристики графа
Нехай G- зв'язний граф, а uі v- дві його неспівпадаючі вершини. Довжина найкоротшого (u, v) -Маршрут називається відстанню між вершинами uі Vи позначається d (u, v). Покладемо d (u, u)=0. Очевидно, що введене таким чином відстань задовольняє наступним аксіомам метрики:
1. d (u, v)? 0;
2. d (u, v)=0 тоді і тільки тоді, коли u=v;
. d (u, v)=d (v, u);
. d (u, v) + d (v, w)=d (u, w) (нерівність трикутника).
Для фіксованої вершини u величина e (u)=max d (uv) називається ексцентриситетом вершини u. Максимальний серед усіх ексцентриситетів вершин називається діаметром графа G і позначається через d (G). Тим самим
dG=max e (u)
Вершина v називається периферійної, якщо e (v)=d (G). Простий ланцюг довжини d (G), відстань між кінцями якої дорівнює d (G), називається діаметральної ланцюгом.
Мінімальний з ексцентриситетів вершин зв'язного графа називається його радіусом і позначається через r (G).
Очевидно, що радіус гра...
