Центры и центроиды

Эксцентриситет е (v) вершины v в связном графе G определяется как

max d (u, v) по всем вершинам и в G. Радиусом r (G) называется наименьший из эксцентриситетов вершин. Заметим, что наибольший из эксцентриситетов равен диаметру графа. Вершина v называется центральной вершиной графа G, если e(v)=r(G); центр графа G — это множество всех центральных вершин.

На рисунке представлено дерево, у которого показан эксцентриситет каждой вершины. Это дерево имеет диаметр 7, радиус 4, а его центр состоит из двух вершин u и v с эксцентриситетом 4. Смежность вершин u и v в этом случае была обнаружена Жорданом и независимо Сильвестром.

Теорема. Каждое дерево имеет центр, состоящий или из одной вершины, или из двух смежных вершин.

Доказательство. Утверждение очевидно для деревьев К₁ и K₂.

Покажем, что у любого другого дерева Т те же центральные вершины, что и у дерева Т', полученного из Т удалением всех его висячих вершин. Ясно, что расстояние отданной вершины и дерева Т до любой другой вершины и может достигать наибольшего значения только тогда, когда v — висячая вершина.

Таким образом, эксцентриситет каждой вершины дерева Т' точно на единицу меньше эксцентриситета этой же вершины в дереве Т. Отсюда вытекает, что вершины дерева Т, имеющие наименьший эксцентриситет в Т, совпадают с вершинами, имеющими наименьший эксцентриситет в Т', т. е. центры деревьев Т и Т' совпадают.

Если процесс удаления висячих вершин продолжить, то мы получим последовательность деревьев с тем же центром, что и у Т. В силу конечности Т мы обязательно придем или к К1, или к К2. В любом случае все вершины дерева, полученного таким способом, образуют центр дерева Т, который, таким образом, состоит или из единственной вершины, или из двух смежных вершин.

Ветвь к вершине u дерева Т - это максимальное поддерево, содержащее и в качестве висячей вершины. Таким образом, число ветвей к u равно deg u. Вес вершины и дерева Т определяется как наибольшее число ребер по всем ветвям к u. На рисунке указаны веса невисячих вершин одного дерева. Понятно, что вес каждой висячей вершины равен 14, т. е. числу ребер.

Вершина v называется центроидной вершиной дерева Т, если v имеет наименьший вес; центроид дерева Т состоит из всех таких вершин. Жордан доказал также теорему о центроиде дерева, напоминающую его результат о центрах.

Теорема. Каждое дерево имеет центроид, состоящий или из одной вершины, или из двух смежных вершин.

Наименьшие деревья с одной и двумя центральными и центроидными вершинами показаны на рисунке.