Основные понятия

Существует несколько эквивалентных определений неориентированного дерева. Неориентированное дерево есть связный граф, содержащий n вершин и n-1 ребер, либо связный граф, не имеющий циклов, либо граф, в котором каждая пара вершин соединена одной и только одной простой цепью.

Если G = (X, A) – неориентированный граф с n вершинами, то остовным деревом (остовом) графа G называется всякий остовной подграф графа G, являющийся деревом. Например, для графа G, показанного на рис.1(а) графы на рис.1(б, в) являются остовами графа G.

Рис.1. Граф G и остовы графа G.

Остов графа G можно также рассматривать как минимальный связный остовной подграф графа G, где «минимальность» понимается в том смысле, что никакое собственное подмножество ребер этого остова не образует связный остовный подграф графа G.

Ориентированное дерево определяется аналогичным образом. Ориентированное дерево представляет собой ориентированный граф без циклов, в котором полустепень захода каждой вершины, за исключением одной (например, вершины x), равна единице, а полустепень захода вершины x (называемой корнем этого дерева) равна нулю.

На рис.2 показан граф, который является ориентированным деревом с корнем в вершине x₁. Из приведенного определения следует, что ориентированное дерево с n вершинами имеет n-1 дуг и связно. Также очевидно, что не всякий ориентированный граф содержит остовное ориентированное дерево.

Рис.2. Ориентированное дерево.

Неориентированное дерево можно преобразовать в ориентированное: надо взять его произвольную вершину в качестве корня и ребрам приписать такую ориентацию, чтобы каждая вершина соединялась с корнем (только одной) простой цепью. Обратно, если T = (X, B) - ориентированное дерево, то , где - множество дуг дерева T без учета их ориентации, является неориентированным деревом.

«Генеалогическое дерево», в котором вершины соответствуют лицам мужского пола, а дуги ориентированы от родителей к детям, представляет собой хорошо известный пример ориентированного дерева. Корень в этом дереве соответствует «основателю» рода (лицу, родившемуся раньше остальных).