Центры и центроиды
Эксцентриситете (v) вершины v в связном графе G определяется как
max d (u, v) по всем вершинам и в G. Радиусомr (G) называется наименьший из эксцентриситетов вершин. Заметим, что наибольший из эксцентриситетов равендиаметруграфа. Вершина v называетсяцентральной вершиной графаG, если e(v)=r(G);центр графаG — это множество всех центральных вершин.
На рисунке представлено дерево, у которого показан эксцентриситет каждой вершины. Это дерево имеет диаметр 7, радиус 4, а его центр состоит из двух вершин u и v с эксцентриситетом 4. Смежность вершин uиvв этом случае была обнаружена Жорданом и независимо Сильвестром.
Теорема.Каждое дерево имеет центр, состоящий или из одной вершины, или из двух смежных вершин.
Доказательство. Утверждение очевидно для деревьев К1и K2.
Покажем, что у любого другого дерева Т те же центральные вершины, что и у дерева Т', полученного из Т удалением всех его висячих вершин. Ясно, что расстояние отданной вершины и дерева Т до любой другой вершины и может достигать наибольшего значения только тогда, когда v — висячая вершина.
Таким образом, эксцентриситет каждой вершины дерева Т' точно на единицу меньше эксцентриситета этой же вершины в дереве Т. Отсюда вытекает, что вершины дерева Т, имеющие наименьший эксцентриситет в Т, совпадают с вершинами, имеющими наименьший эксцентриситет в Т', т. е. центры деревьев Т и Т' совпадают.
Если процесс удаления висячих вершин продолжить, то мы получим последовательность деревьев с тем же центром, что и у Т. В силу конечности Т мы обязательно придем или к К1, или к К2. В любом случае все вершины дерева, полученного таким способом, образуют центр дерева Т, который, таким образом, состоит или из единственной вершины, или из двух смежных вершин.
Ветвь к вершине u дерева Т- это максимальное поддерево, содержащее и в качестве висячей вершины. Таким образом, число ветвей кuравно deg u . Вес вершины и дерева Т определяется как наибольшее число ребер по всем ветвям кu. На рисунке указаны веса невисячих вершин одного дерева. Понятно, что вес каждой висячей вершины равен 14, т. е. числу ребер.
Вершина v называется центроидной вершиной дереваТ, если v имеет наименьший вес;центроид дерева Т состоит из всех таких вершин. Жордан доказал также теорему о центроиде дерева, напоминающую его результат о центрах.
Теорема.Каждое дерево имеет центроид, состоящий или из одной вершины, или из двух смежных вершин.
Наименьшие деревья с одной и двумя центральными и центроидными вершинами показаны на рисунке.
Деревья блоков и точек сочленения
Связный граф с большим числом точек сочленения похож на дерево. Эту черту графа можно оттенить четче, если сопоставить с каждым связным графом соответствующее дерево.
Для связного графа G с множеством блоков {Bi} и множеством точек сочленения {сj} граф блоков и точек сочлененияbc (G) определяется как граф, у которого множеством вершин служит {В,} U {Cj} и две вершины смежны, если одна соответствует блоку Bi,
а другая - точке сочленения сj, причем сj, принадлежит Вj. Таким образом,
bc(G) - двудольный граф. Это понятие было введено в работе Харари и Принса, а также в статье Галлаи.
Теорема.G - граф блоков и точек сочленения некоторого графа Н тогда и только тогда, когда он является деревом, в котором расстояние между любыми двумя висячими вершинами четно.
Имея в виду эту теорему, мы будем говорить о дереве блоков и точек сочленения графа.