Деревья.. Основные определения

Неориентированным деревом(или просто деревом) называется связный граф без циклов. Этому определению эквивалентны, как легко показать, следующие определения:

а) дерево есть связный граф, содержащий n вершин и n - 1 ребер;

б) дерево есть граф, любые две вершины которого можно соединить простой цепью.

Пример 3.17.

Графы, изображенные на рис. 3.12, являются деревьями.

Рис. 3.12

Если граф несвязный и не имеет циклов, то каждая его связная компонента будет деревом. Такой граф называется лесом. Можно интерпретировать рис. 6.1 как лес, состоящий из трех деревьев.

Остовным деревомсвязного графа G называется любой его подграф, содержащий все вершины графа G и являющийся деревом.

Пример 3.18.

Для графа, изображенного на рис. 3.13а), графы на рис. 3.13б) и 3.13в) являются остовными деревьями.

Рис. 3.13

 

Пусть граф G имеет n вершин и m ребер Так как всякое дерево с n вершинами по определению (см. раздел 6.1) имеет n – 1 ребер, то любое остовное дерево графа G получается из этого графа в результате удаления m –(n – 1) = m – n + 1 ребер. Число g = m – n + 1 называется цикломатическим числомграфа.