Page 38 - 4386

Приклад 3.6. Визначити точки зчленування та мости для

графа, наведеного на рис. 3.4.

Рисунок. 3.4

Розв'язок.

Точки зчленування є наступними: v , v , v та v .
5
6
3
2
Мости є наступними: e , e та e .
3
1
6
Приклад 3.7. Визначити множини розрізу для графа,
наведеного на рис. 3.5.

Рисунок 3.5

Розв'язок.

Множинами розрізу для даного графа можуть бути наступні:

{e , e }, {e , e }, {e , e }, {е , е , е }, {е , е , е } і т.д.
8
4
7
5
4
5
1
2
3
2
1
6
3.5 Відстань між вершинами. Метрика на графах
Довжина найкоротшого простого ланцюга, що з’єднує
вершини v та w зв’язного графа, називається відстанню між
вершинами v та w і позначається d(v, w).

37