Дискретная математика

151 Ч I И Л лV N а) б) Рис. 5.24 Пусть, как обычно, п - число вершин,a m - число дуг орграфа. 1) 2 ) 3) 4 ) Теорема 5.15. Ордерево обладает следующими свойствами: т = я - 1; если в ордереве отменить ориентацию ребер, то получится дерево; в ордереве нет контуров; для каждой вершины существует единственный путь, ведущий в эту вершину из корня; 5 ) подграф, определяемый множеством вершин, достижимых из | некоторой вершины v данного ордерева, является ордеревом с корнем v (это j ордерево называется поддеревом вершины v); | 6 ) если в свободном дереве любую вершину назначить корнем и ввести ориентацию ребер от корня к концевым вер1Ш1нам, то получится ордерево. j Докачательство: 1. Каждая вершина достижима из корня и полустепени захода всех вершин кроме корневой вершины,равны единице, следовательно, т = п-1. 2. Пусть G - ордерево, граф G' получен из G отменой ориентации ребер, и - корень. Тогда для V v;,vi е V существуют цепи Z(vi,u) и Zfu.vj) в графе С , поэтому любые две вершины V/,V2 е V соединены цепью Z(vi,vi) = Z(vi,u) uZ(u,v2), следовательно, граф О ' связен. Допустим, что С содержит цикл С и vi,v2 различные вершины этого цикла. Тогда, кроме цепи Z(v,,v2)= Z(v,,u) uZ(u,V2), должна быть другая цепь Z*(vi,v2), соединяющая вершины v; и V2. Следовательно, в графе G одна из вершин v/ или vi должна имегь полустепень захода больше чем единица, что не может быть. Таким образом, допущение неверно и G ' не имеет циклов, т.е. О' - дерево. 3. Следует из 2. 4. От противного. Если бы в G существова1Ш два пути из и в v, то в G' имелся бы цикл. Утверждения 5) и 6) теоремы 5.15 оставляем читателю в качестве упражнений. Концевая вершина ордерева называется листом. Путь из корня в лист называется ветвью. Длина наибольшей ветви ордерева называется высотой