Реферат Курсовая Конспект
Центроид дерева - раздел Транспорт, Лекция № 12. НЕОРИЕНТИРОВАННЫЕ ГРАФЫ Ветвь К Вершине V Дерева – Это Максимальный Подгр...
|
Ветвь к вершине v дерева – это максимальный подграф, содержащий v в качестве висячей вершины. Вес вершины k – наибольший размер ее ветвей. Центроид (или центр масс) дерева C – множество вершин с наименьшим весом: C = {v| c(v) = }.
Вес любого листа дерева равен размеру дерева. Высота дерева с корнем, расположенным в центроиде, не больше наименьшего веса его вершин.
Свободное дерево порядка n с двумя центроидами имеет четное количество вершин, а вес каждого центроида равен n/2.
Теорема 14.3 (Жордана). Каждое дерево имеет центроид, состоящий из одной или двух смежных вершин.
Пример 14.1. Найти наименьший вес вершин дерева, изображенного на рис. 14.1, и его центроид.
Рис. 14.1
Решение. Очевидно, что вес каждой висячей вершины дерева порядка n равен n – 1. Висячие вершины не могут составить центроид дерева, поэтому исключим из рассмотрения вершины 1, 2, 4, 6, 12, 13 и 16. Для всех остальных вершин найдем их вес, вычисляя длину (размер) их ветвей.
Число ветвей вершины равно ее степени. Вершины 3, 5 и 8 имеют по две ветви, размеры которых равны 1 и 14. К вершине 7 подходят четыре ветви размером 1, 2, 2 и 10. Таким образом, ее вес . Аналогично вычисляются веса других вершин: , , . Минимальный вес вершин равен 8, следовательно, центроид дерева образуют две вершины с таким весом: 11 и 15.
– Конец работы –
Эта тема принадлежит разделу:
Основные определения Каждое ребро e из E инцидентно ровно двум вершинам и... Циклы... Маршрут в котором начало и конец совпадают циклический Циклический маршрут называется циклом если он цепь...
Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: Центроид дерева
Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:
Твитнуть |
Новости и инфо для студентов