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

150 графа G называется диаметром графа G, который обозначают d(G), d(G)= maxd(v,u). Таким образом, диаметр графа G равен длине наибольшей V.UEG простой цепи графа. Радиусом r(G) называется наименьший из эксцентриситетов вершин графа С; r(G) = =mine(u). U^G Вершина v называется центральной вершиной графа G, если e(v) = ''(G)- Центр графа G - это множество всех центральных вершин. На рис. 5.23, б) построен граф, для которого d(G)~l, r(G)=A, а центр состоит из двух вершин у и ц. Теорема 5.14. Каждое дерево имеет центр, состоящий или из одной вершины, ипи из двух смежных вершин. Доказательство. Утверждение очевидно для 1 и 2-х вершинных графов. Покажем, что у любого дерева Т те же центральные вершины, что и у дерева Г', полученного из Г удалением всех его висячих вершин. .Ясно, что расстояние от данной вершины v любого дерева Т до любой другой вершины и может достигать наибольшего значения только тогда, когда и - висячая вершина. Таким образом, эксцентриситет каждой оставшейся в Т' вершине точно на единицу меньше эксцентриситета этой же вершины в Т. Отсюда следует, что вершины дерева Г, имеющие наименьший эксцентриситет в Т, совпадают с вершинами, имеющими наименьший эксцентриситет в Т', т.е. центры деревьев Г и Г' совпадают. Если процесс удаления висячих вершин продолжить, то получим последовательность деревьев с тем же центром, что и у дерева Т. В силу конечности Г обязательно придем к 1 или 2-х вершинному дереву. В любом случае все вершины дерева, полученного таким образом, образуют центры дерева Г, и этот центр состоит или из единственной вершины, или из двух смежньгх вершин. Зри в корень. К. Прутков § 13. Ориентированные деревья Ориентированньш деревом (или ордеревом, или корневым деревом) называется орграф со следующими свойствами; 1) существует единственная вершина, полустепень захода которой равна 0. Она называется корнем ордерева; 2) полустепень захода всех остальных вершин равна 1; 3) каждая вершина достижима из корня. На рис. 5.24 приведены всевозможные ордеревья с тремя (рис 5.24, а) и с четырьмя (рис 5.24, б) вершинами.