Вес каждой вершины дерева

Алгоритм разбиения дерева на компоненты связности

Есть дерево, в котором каждая вершина имеет свой вес, нужно разбить дерево на три компоненты связности, в каждой из которых суммарный вес всех вершин одинаков. Подскажите, какой алгоритм стоит использовать? Пока вижу такое решение — перебор всех пар ребер, с последующей проверкой — но это тяжелое решение по производительности.

Эта задача у Вас возникла всё по той же теме: оценка размера PNG (ru.stackoverflow.com/questions/649761/…) ?

Что делать, если решения не существует? Правильно ли я понимаю, что нужно удалить какие-то 2 ребра? В таком случае в дереве окажется 3 компоненты связности. Каков размер дерева?

@hedgehogues, нет, задачи не связаны друг с другом, в случае отсутствия решения просто сообщить об этом (ведь на самом деле его может и не быть) набор данных ограничен только тем, что граф это любое дерево (для простоты полагается что как минимум два ребра есть)

В таких задачах правильное решение и выбор алгоритма критически зависит от того, могут ли веса вершин быть отрицательными. В том числе и в этой задаче. Могут или нет?

Просто если все веса строго положительны, то разбиение (если оно существует) будет однозначным. А если есть нулевые веса, то могут появляться компоненты нулевого веса, которые можно будет гонять туда-сюда. Т.е. появляется неоднозначность в решении. Однозначная задача более «осязаема».

2 ответа 2

Задачка, кажущаяся на первой взгляд, переборной со сложностью (N — число вершин), может быть решена проще, быстрее, за полиномиальное время. Почему это так я хочу описать ниже.

Во-первых, кажущийся переборный алгоритм имеет место для произвольного графа (возможно есть оптимизации и можно решить быстрее). У нас же граф очень специфический. Он намного проще того, что есть в общем случае. Эта простота, например, выражается в отсутствии циклов.

Во-вторых, нам нужно разбить наш граф всего на 3 компоненты связности.

Теперь давайте обсудим: как это разбивать граф на компоненты связности. Мы сразу скажем, что разбиение на компоненты связности — это удаление некоторых рёбер. Приведу пример разбиения на компоненты связности следующего графа:

Получим 2 компоненты связности:

Получим 3 компоненты связности:

Другой пример. Получим 2 компоненты связности (вершина 1 — это заменена на вершину 15):

Получим 3 компоненты связности:

Как можно наблюдать, всегда при удалении 1 ребра, появляется ещё одна компонента связности. Это можно доказать срого. Но воздержимся, дабы не загружать текст. Таким образом, нужно удалить 2 ребра так, чтобы у нас оказалось 3 компоненты связности.

Давайте немного переформулируем задачу. Нам необходимо поставить 2 метки на рёбра так, чтобы в каждой компоненте оказался суммарный вес одинаковым. Что же для этого нужно сделать? ОЧЕВИДНО! Перебрать все пары рёбер. Для этого занумеруем их от 0 до N-1. Переберём все пары рёбер. И для каждой пары будем проверять: правильное ли у нас разбиение или нет. Напишем псевдокод:

# Перебираем все рёбра for i in range edge: for j in range edge: # Если разбиение делит наше дерево на равные по весу части, то заканчиваем выполнение if Splitting(i, j): break 

Очевидно, что сложность такого алгоритма будет полиномиальной

где g(n) — время работы Splitting .

Но что делаь с функцией Splitting(i, j) ? Очевидно, что Splitting(i, j) может отработать за линейное время. Запустим из каждой вершины обход в глубину, причём, если в некоторой вершине мы уже были, то не будем туда заходить больше. Вот и получится, что мы обошли все вершины лишь по одному разу. Т.е. мы обошли каждую компоненту связности единожды. В таком случае, ассимптотическое время работы будет , хотя, по факту, это будет 2N. Внутри DFS (обход в глубину) мы будем считать веса для каждой компоненты связности.

Время работы Splitting можно улучшить следующим образом. Сделаем для этого предподсчёт. Для каждого ребра будем хранить 2 параметра: суммарный вес вершин выше ребра и суммарный вес ниже ребра. Приведём пример:

Т.е. для ребра, соединяющего вершины 15 (она же 1, см. выше) и 3, мы можем посчитать суммарный вес в каждом кластере. Делать это будем следующим образом. Запустим LR-обход дерева и для каждого ребра (Замечу, что рёбра можно ассоциировать с соответствующими вершинами. Например, ребро (11, 10) ассоциируем с вершиной 11, ребро (6, 2) ассоциируем с вершиной 6 и т.д. Далее будем говорить о вершинах, а не о рёбрах).

Продемонстрируем пример обхода:

0 - 10 - 11 - 12 - 13 - 15 (1) - 3 - 4 - 5 - 9 - 2 - 6 - 7 - 8 

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

Пусть мы находимся в вершине 11. И для поддерева этой вершины мы уже посчитали вес (на рисунке она изображена листом, но будем считать, что у неё есть поддерево). Тогда нам необходимо перейти в вершину 10 и подсчитать вес поддерева вершины 10. В порядке LR-обхода, посетим и подсчитаем вес поддерева с корнем в вершине 12, 13. Тогда вес поддерева с корнем в вершине 10, будет суммой весов поддеревьев 11, 12, 13:

Имеем формулу в общем случае:

Для вершины v обозначим вес дерева выше неё:

Теперь, нам нужно вычислить аналогично, для каждой вершины вес дерева выше неё. Для этого будем считать, что выше корневой вершины ничего нет. Тогда ещё раз запустим LR-обход (модифицированный). Модификация будет состоять в том, что мы будем осуществлять все действия ещё при спуске.

Очевидно, что данный алгоритм вычисления вышеуказанных характеристик отработает за время .

Таким образом, для каждой вершины имеем вес дерева ниже неё и вес дерева выше неё.

Теперь нам необходимо научиться быстро узнавать: лежит ли данная вершина v в поддереве другой вершины u. Введём функцию:

Для её быстрого вычисления нам понадобятся дополнительные ухищрения. И ещё один предподсчёт.

Источник

Лекция № 14. Деревья

1. Основные определения

Дерево – связный граф без циклов. Лес (или ациклический граф) – неограф без циклов. Компонентами леса являются деревья. Теорема 14.1.Для неографаGсnвершинами без петель следующие условия эквивалентны:

1. G– дерево;
2. G– связной граф, содержащийn– 1 ребро;
3. G– ациклический граф, содержащийn– 1 ребро;
4. Любые две несовпадающие вершины графаGсоединяет единственная цепь;
5. G– ациклический граф, такой, что если в него добавить одно ребро, то в нем появится ровно один цикл.

Теорема 14.2.НеографGявляется лесом тогда и только тогда, когда коранг графаv(G)=0. Висячая вершина в дереве – вершина степени 1. Висячие вершины называются листьями, все остальные – внутреннимивершинами. Если в дереве особо выделена одна вершина, называемая корнем, то такое дерево называется корневым, иначе – свободным. Корневое дерево можно считать орграфом с ориентацией дуг из корня или в корень. Очевидно, что для любой вершины корневого дерева, кроме корня, . Для корня, для листьев. Вершины дерева, удаленные на расстояние k (в числе дуг) от корня, образуют k-й ярус (уровень) дерева. Наибольшее значение k называется высотой дерева. Если из какой-либо вершины корневого дерева выходят дуги, то вершины на концах этих дуг называют сыновьями (в английской литературе – дочери (daughter)).

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

Ветвь к вершине 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.

1. Десятичная кодировка

Деревья представляют собой важный вид графов. С помощью деревьев описываются базы данных, деревья моделируют алгоритмы и программы, их используют в электротехнике, химии. Одной из актуальных задач в эпоху компьютерных и телекоммуникационных сетей является задача сжатия информации. Сюда входит и кодировка деревьев. Компактная запись дерева, полностью описывающая его структуру, может существенно упростить как передачу информации о дереве, так и работу с ним. Существует множество способов кодировки деревьев. Рассмотрим одну из простейших кодировок помеченных деревьев с выделенным корнем – десятичную. Кодируя дерево, придерживаемся следующих правил.

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

Кодировка в такой форме получается достаточно компактной, однако она не несет в себе информации о номерах вершин дерева. Существуют аналогичные кодировки, где вместо единиц в таком же порядке проставляются номера или названия вершин. Есть деревья, для которых несложно вывести формулу десятичной кодировки. Рассмотрим, например, графы-звезды , являющиеся полными двудольными графами, одна из долей которых состоит из одной вершины. Другое обозначение звезд –. На рис. 14.2 показаны звезды, а также приведены их двоичные и десятичные кодировки. Корень дерева располагается в центральной вершине звезды. Легко получить общую формулу: . (14.1) Рис. 14.2 Если корень поместить в любой из висячих вершин, то код такого дерева будет выражаться большим числом. Более того, существует зависимость. Аналогично рассматриваются и цепи (рис. 14.3). Цепи обозначаются как. Рис. 14.3 В звездах только два варианта расположения корня с различными десятичными кодировками. В цепи же число вариантов кодировок в зависимости от положения корня растет с увеличением n. Рассмотрим самый простой вариант, расположив корень в концевой вершине (листе). Для получим двоичную кодировку 10 и десятичную 2, для– 1100 и 12, для– 111000 и 56, для– 11110000 и 240. Общая формула для десятичной кодировки цепи с корнем в концевой вершине имеет вид . (14.2) Пример 14.2. Записать десятичный код дерева, изображенного на рис. 14.4, с корнем в вершине 3. Рис. 14.4 Решение. На основании правила кодировки, двигаясь по дереву, проставим в код единицы и нули. При движении из корня 3 к вершине 7 проходим четыре ребра. В код записываем четыре единицы: 1111. Возвращаясь от вершины 7 к вершине 2 (до ближайшей развилки), проходим три ребра. Записываем в код три нуля: 000. От вершины 2 к 5 и далее к 8 (меньший номер): 11; от 8 назад к 5 и от 5 к 9: 01; от 9 к корню 3: 000. И, наконец, от 3 к 6 и обратно: 10. В итоге, собирая все вместе, получим двоичный код дерева: 1 111 000 110 100 010. Разбивая число на тройки, переводим полученное двоичное представление в восьмеричное. Получаем . Затем переводим это число в десятичное:.

Для продолжения скачивания необходимо пройти капчу:

Источник