Деревья Дерево это частный случай графа, наиболее широко применяемый в программировании. Основные определения



жүктеу 123.73 Kb.
бет3/3
Дата11.11.2022
өлшемі123.73 Kb.
#23733
1   2   3
Деревья граф
лекция 8 икт в инклюз, практика 6 граф, 1. Информатика білім беру саласы ретінде, примеры на граф, 3 дәріс, informatikany-bzd-ortamyzda-alatyn-orny
Определение. Граф называется деревом, если он связный и в нем нет циклов.
Одноэлементный граф, т.е. граф, имеющий одну вершину и не имеющий ребер, также считается деревом.
Граф называется лесом (или ациклическим графом), если в нем нет циклов. Очевидно, что каждая компонента связности леса - дерево.
Пример 1. Граф  (рис. 3.19) не является ни деревом, ни лесом. Граф  (рис. 3.20) - дерево. Граф  (рис. 3.21) - лес, состоящий из четырех деревьев.








Рис. 3.19.

Рис. 3.20.

Рис. 3.21.

Пример 2. Представьте диаграммами все (с точностью до изоморфизма) деревья с пятью вершинами.
◄ Имеется три различных (с точностью изоморфизма) дерева с пятью вершинами (рис. 3.22 - 3.24). ►







Рис. 3.22.

Рис. 3.23.

Рис. 3.24.

Деревья обладают рядом характеристических свойств, по наличию или отсутствию каждого их которых в рассматриваемом графе   можно определить, является граф деревом или нет. Перечислим эти свойства:
1) граф  - дерево в том и только в том случае, когда в нем нет циклов и  ;
2) граф  - дерево в том и только в том случае, когда он связный и  ;
3) граф  - дерево в том и только в том случае, когда он связный, и каждое его ребро является мостом;
4) граф  - дерево в том и только в том случае, когда любые две вершины графа  можно соединить простой цепью, притом единственной;
5) граф  - дерево в том и только в том случае, когда в нем нет циклов и добавление к нему нового ребра приводит к образованию единственного простого цикла.
Также приведем одно из характеристических свойств леса: граф  , имеющий  компонент связности, является лесом в том и только в том случае, когда  .


жүктеу 123.73 Kb.

Поделитесь с Вашими друзьями:
1   2   3




©emirb.org 2022
әкімшілігінің қараңыз

    Басты бет