Page 35 - 4386

До основних властивостей маршрутів слід віднести

наступні.

1. Будь-який маршрут, що веде з вершини v у вершину w

(v≠w), містить простий ланцюг, що веде з v у w.

2. Будь-який найкоротший маршрут, що веде з вершини v у

вершину w (v≠w), є простим ланцюгом.

3. Довільний цикл містить простий цикл.

4. Якщо в графі для деяких трьох різних вершин v, u та w є

ланцюги, один з яких веде з v в u, а другий – з u в w, то існує

простий ланцюг, що веде з v у w.

5. Якщо в нетривіальному замкненому маршруті всі сусідні

ребра різні, то він містить цикл.

3.3 Зв’язність графів, зв’язні компоненти

Питання зв’язності графа виникає у багатьох практичних

задачах, наприклад, коли граф представляє схему руху

транспорту і необхідно визначити, чи можна проїхати з одного

пункту в інший.

Вершини v і w графа G називаються зв'язаними, якщо існує

маршрут з початком у вершині v та кінцем у вершині w. Маршрут

між зв'язаними вершинами може бути поданий простим

ланцюгом.

Граф G називається зв'язним, якщо будь-які пари його

вершин зв'язані між собою. Таким чином, граф G є зв'язним тоді і

тільки тоді, коли між будь-якими двома його вершинами існує

простий ланцюг.

Приклад 3.5. Граф, зображений на рис. 3.3 а, є незв'язний, а

граф на рис. 3.3 б – зв'язний.

34