Центрированное дерево

Слева центрированное дерево, справа двухцентровое. Цифры показывают эксцентриситет каждого узла.

В дискретной математике центрированное дерево - это дерево только с одним центром , а двухцентровое дерево - это дерево с двумя центрами.

Для графа эксцентриситет вершины v определяется как наибольшее расстояние от v до любой другой вершины (см. Расстояние в теории графов ). Центр графа является вершиной с минимальным эксцентриситетом. Граф может иметь произвольное количество центров. Однако Джордан (1869) доказал, что для деревьев есть только две возможности:

1. У дерева ровно один центр (центрированные деревья).
2. У дерева ровно два центра (двухцентровые деревья). В этом случае два центра смежны.

Доказательство этого факта дает, например, Кнут. ^[1]

Примечания

использованная литература

• Иордания, Камилла (1869). "Sur les Assemblages de lignes" . Journal für die reine und angewandte Mathematik (на французском языке). 70 (2): 185–190.
• Кнут, Дональд Э. (1997). Искусство программирования , Том 1: Основные алгоритмы (3-е изд.). Эддисон-Уэсли Профессионал. ISBN 0-201-89683-4.

внешние ссылки

• Вайсштейн, Эрик В. «Двухцентровое дерево» . MathWorld .
• Вайсштейн, Эрик В. «Центрированное дерево» . MathWorld .

Эта статья о топологии незавершена . Вы можете помочь Википедии, расширив ее .

• v
• т
• е