Спирина, М.С. Дискретная математика

ключением корневой, называются листьями. На рис. 2.14 листьями являются, например, вершины V4, Vl3 и V20. При п = 2 дерево со­ стоит из корня и листа и имеет вид отрезка. Пусть (?], G2, Gk — непересекаюшиеся деревья, т.е. V/, j е € (1, ..., к) (?,П Gj=0 . Тогда упорядоченное объединение деревьев к G = |JG, представляет собой несвязный граф, называемый лесом. 1=1 Компонентами связности леса являются деревья. Остовом связно­ го графа G называется любой его подграф, содержащий все вер­ шины графа G и являющийся деревом (говорят: «покрывающим его деревом»). Кодеревом Т остова Т графа G называется дополнение Т до G, т. е. такой его подграф, который содержит все его вершины и только те ребра, которые не входят в Т. Тогда 67= T{J Т = Т ® Т . Иначе говоря, кодеревом остова Т ( V, Xt) графа G( V, X) будет остов Т (V, X \X i). Очевидна двойственность: (т )' = Т. Дерево может быть представлено расслоенным на ярусы (уров­ ни), при этом ветвям, попавшим в один ярус, соответствует оди­ наковая длина пути исходного графа. Число путей в каждом дере­ ве соответствует числу висячих вершин (листьев). Например, в графе на рис. 2.14 двадцать листьев и двадцать путей от V0. При описании деревьев принято использовать термины: отец, сын, предок, потомок. Каждая вершина дерева называется узлом, причем каждый узел является корнем дерева, имеющего п поддеревьев (п е [0, «)). Тогда узел без поддеревьев называется листом и является висячей вер­ шиной. Узел к -го яруса называется отцом узла (к+ 1)-го яруса, если они смежны. Узел (к+ 1)-го яруса называется сыном узла к-го яруса. Два узла, имеющие одного отца, называются братьями (рис. 2.15). Упорядоченным деревом называется дерево, в котором поддере­ вья каждого узла образуют упоря­ доченное подмножество. Для упоря­ доченных деревьев принята терми­ нология: старший и младший сын для обозначения соответственно первого и последнего сыновей не­ которого узла. В информатике принято исполь­ зовать подмножество множества деревьев, когда каждый узел либо является листом, либо образует два поддерева: левое и правое. Такой вид деревьев называется бинарны­ ми деревьями и используется при делении множества на два взаимо- К0 (предок) V2 (потомок) 4 (отец V6 и V7) V6 (старший V-j (младший сын К4) сын К4) Рис. 2.15. Иллюстрация род­ ственных связей —упорядочен­ ное дерево 82