Page 51 - 4386

5 ДЕРЕВО, ЛІС. КІСТЯКОВІ ДЕРЕВА ТА ЛІСИ.

ЦИКЛОМАТИКА ГРАФА.

5.1 Дерево, ліс

Неорієнтованим деревом (або просто деревом) називається

вільний від петель неорієнтований зв'язний ациклічний граф (граф

без циклів, отже без петель і кратних ребер), що має не менше

двох вершин.

Дерево є мінімальним зв'язним графом у тому розумінні, що

видалення хоча б одного ребра приводить до того, що граф стає

незв'язним.

Наприклад, граф, зображений на рис. 5.1 а, є деревом, тому

що він зв'язний і не містить циклів, а граф на рис. 5.1 б не є

деревом, тому що містить цикл v v v .
5 6 9

а б

Рисунок 5.1

Орієнтованим деревом називається вільний від петель

ациклічний орієнтований граф, у якому ніякі дві дуги не заходять

в одну і ту ж саму вершину (рис. 5.2). Необхідно відзначити, що в

орієнтованому дереві з однієї вершини можуть виходити кілька

дуг. Таким чином, якщо існує в орієнтованому дереві шлях від

вершини v до вершини w, то він єдиний. Також, якщо в

50