Дерева та їх властивості в системі числення понять
Означення дерева. Властивості дерев
Зв’язний ациклічний граф називається (неорієнтованим) деревом. Дерево називається кореневим, якщо в ньому виділена вершина, яка називається коренем.
Остовним деревом графа G називається остовний підграф графа G, який є деревом.Щодо дерев діють наступні твердження:
• граф є деревом тоді і лише тоді, коли будь-які дві його вершини зв’язані лише одним ланцюгом;
• якщо T - дерево і u - його кінцева вершина, то граф T - u - дерево;
• всяке непусте дерево має щонайменше дві кінцеві вершини і одне кінцеве ребро;
• T є деревом;
• Т-не має циклів і має п - 1 ребро;
• T-зв’язний граф і маєп- 1 ребро;
• T- зв’язний граф, і кожне його ребро є мостом;
• Будь-які дві вершини графа T з’єднані рівно одним простим ланцюгом;
• Т-не має циклів, але введення нового ребра в T сприяє виникненню рівно одного циклу;
Якщо T має цикл, то будь які дві вершини цього циклу з’єднані не менше, ніж двома простими ланцюгами. Добавляючи до графа T деяке ребро е, одержимо цикл, оскільки вершини інцидентні ребру е уже зв’язані в T простим ланцюгом.
Якщо G - ліс з п вершинами і k компонентами, тоді G має n - k ребер.
Теорема Келі. Число різних дерев, які можна побудувати на п вершинах, дорівнює п11’2.
204
більш ніж п112 сум.
Застосовуючи процедуру доведення теореми Келі до кожного компонента графа G, одержимо граф, який називається остовним лісом. Число ребер, які при цьому вилучаються, називаються цикломатичним числом або циклічним рангом графа G і позначається C(G). Цикломатичне число є мірою зв’язності графа.
Фундаментальна система циклів графа
З поняттям остовного лісу T графа G тісно пов’язане поняття фундаментальної системи циклів, яка асоціюється з Т.
Нехай T - остовний ліс графа G. Якщо ввести довільне ребро в граф G, яке не входить в Т, то одержимо єдиний цикл. Множина всіх циклів, які одержані в такий спосіб (шляхом введення окремо кожного ребра в граф G, яке не входить до Т), називається фундаментальною системою циклів, асоційованою з Т. У кожному випадку, коли нас цікавить, який остовний ліс розглядається, будемо говорити про фундаментальну систему циклів графа G (рис. 50).
Фундаментальна система циклів, асоційована з остовним деревом графа G
Рис.50
Для фундаментальної системи циклів дійсні такі твердження:
• якщо G = (V, Е) довільний скінчений граф, то число ребер G, які необхідно вилучити для одержання остовного лісу Т, не залежить від
порядку їх вилучення;
• граф G являє собою ліс тоді і лише тоді, коли C(G) = 0;
• всякий ациклічний підграф довільного скінченого графа G = (V, Е) є підграфом остовного дерева графа G;
• всяке дерево порядку n ≥ 2 має щонайменше дві кінцеві вершини.