2015-04-01
453
Центрами деревьев являются вершины максимального типа и только они. Все диаметральные цепи проходят через центры и имеют длину 2k–2, если центр 1; 2k–2, если центра 2.
Корнем дерева называется любая помеченная вершина.
Если в дереве определен корень, все ребра графа можно ориентировать (от корня). Причем, ребро (a, b) ориентируется от a к b, если цепь, связывающая корень с вершиной а не проходит через вершину b, и наоборот.
Ветвью вершины а называется подграф, порожденный множеством В(а) – вершин, связанных с корнем цепями, проходящими через вершину а.
Характеристические числа графа – это цикломатическое число, число внутренней устойчивости и число внешней устойчивости.
Цикломатическое число графа G находится по формуле:
.
Здесь 
– число ребер графа G; 
– число вершин; 
– число компонент связности.
