хопленням. p> Властивості маршрутів, ланцюгів та ціклів:
) Будь-який незамкненій (u, v)-маршрут містіть в Собі прості (u, v)-ланцюг. Зокрема, будь-який (u, v)-ланцюг містіть в Собі прості (u, v)-ланцюг. До того ж, ЯКЩО (u, v)-маршрут складає в Собі вершину w (), то в загально випадка прості (u, v)-ланцюг может НЕ містіті в Собі вершину w. p align="justify"> 2) Будь-який непрості цикл можна розкласті на два чі больше простих. Альо для замкненому маршруту таке Твердження невірне.
) Будь-який непросто (u, v)-ланцюг может буті Розбитий на прості (u, v)-ланцюг та один або больше простих ціклів. Для замкненому маршруту це Твердження невірне.
) Для будь-яких трьох вершин u, w, v Із Існування (u, w)-ланцюга ту (w, v)-ланцюга слідує Існування (u, v)-ланцюга. До того ж, чи не может існуваті (u, v)-ланцюга, что містіть вершину w.
) Про єднання двох простих (u, v)-ланцюгів, что НЕ співпадають, має простий цикл.
) Если граф має в Собі 2 цикли, что НЕ співпадають, Із спільнім ребром е, то после видалений цього ребра граф все одне має цикл.
Граф назівається зв язнім, ЯКЩО будь-які Дві его вершини, что НЕ співпадають, з'єднані маршрутом. Очевидно, что для зв язності графу звітність, и Достатньо, щоб у ньом для деякої фіксованої вершини u и кожної Іншої вершини v існував (u, v)-маршрут.
Коженая Максимальний зв язній підграф графа G назівається зв язною компонентів (чі просто компонент) графа G. Слово В«МаксимальнийВ» означає Максимальний відносно включення, тоб такий, что не заходити у зв язній підграф з більшою кількістю ЕЛЕМЕНТІВ. Множини вершин зв'язної компоненти назівається ОБЛАСТЬ зв язності.
Для орієнтованого графу вводять Поняття орієнтованого маршрутом, что тепер назівається Шляхом або орієнтованім Ланцюг. Такоже аналогом циклу слугує контур (орієнтований цикл). p align="justify"> Орграф назівають сільнозв язнім, ЯКЩО будь-які Дві его вершин можна досягнутості один з одного. Орграф назівається односторонньозв'язнім, ЯКЩО будь-які Дві вершини его основи з'єднані маршрутом. Орграф назівається незв'язнім, ЯКЩО в его Основі лежить незва язній псевдографом.
Орграф є сільнозв'язнім тоді и Тільки тоді, коли ВІН складає в Собі остовно ціклічній маршрут (тоб такий цикл, что охоплює ВСІ вершини графу).
Орграф є односторонньозв'язнім тоді и Тільки тоді, коли кіль ВІН має осто...
