Page 56 - 4386

3) R(T )=R(T )-1;
2
1
4) якщо L=(v v…ww ) є максимальним ланцюгом у T , то
1
1
1
L =(v…w) – максимальний ланцюг у T ;
2
2
5) D(T )=D(T )-2.
1
2
При розв’язуванні прикладних задач, часто виникає
необхідність у визначенні центра графа і, зокрема, центра дерева.

Розглянемо один досить ефективний алгоритм визначення

центра дерева.

З дерева одночасно вилучаються всі його кінцеві вершини.

Оскільки, при цьому не порушується зв’язність і не з’являються

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

віддаленими вершинами зменшується на 2, тобто парність

діаметра не змінюється. Далі ця операція повторюється доти,

поки не залишиться одна вершина (якщо діаметр початкового

дерева парний) або дві суміжні (якщо непарний). Це і є центром

дерева.

5.4 Кістякові дерева та ліси

Кістяковим (каркасним) деревом зв’язного графа G=(V, E)

називається такий його суграф T=(V, E ), E ⊆E (підграф, що
T
T
містить усі вершини графа), що є деревом.

Кістяковим (каркасним) лісом незв’язного графа G=(V, E)

називається сукупність кістякових дерев зв’язних компонент

графа G.

Кістяковим орієнтованим деревом називається орієнтоване

дерево, що є одночасно і кістяковим деревом.

Кістяковим орієнтованим лісом графа G=(V, E) називається

сукупність кістякових орієнтованих дерев зв’язних компонент

графа G.

55