Алгоритм разбиения дерева на компоненты связности
Есть дерево, в котором каждая вершина имеет свой вес, нужно разбить дерево на три компоненты связности, в каждой из которых суммарный вес всех вершин одинаков. Подскажите, какой алгоритм стоит использовать? Пока вижу такое решение — перебор всех пар ребер, с последующей проверкой — но это тяжелое решение по производительности.
Эта задача у Вас возникла всё по той же теме: оценка размера 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. Введём функцию:
Для её быстрого вычисления нам понадобятся дополнительные ухищрения. И ещё один предподсчёт.
Источник
Дерево, эквивалентные определения
Для графа [math]G[/math] эквивалентны следующие утверждения:
- [math]G[/math] — дерево.
- Любые две вершины графа [math]G[/math] соединены единственным простым путем.
- [math]G[/math] — связен и [math] p = q + 1 [/math] , где [math]p[/math] — количество вершин, а [math]q[/math] количество ребер.
- [math]G[/math] — ацикличен и [math] p = q + 1 [/math] , где [math]p[/math] — количество вершин, а [math]q[/math] количество ребер.
- [math]G[/math] — ацикличен и при добавлении любого ребра для несмежных вершин появляется один простой цикл.
- [math]G[/math] — связный граф, отличный от [math] K_p [/math] для [math] p \gt 3 [/math] , а также при добавлении любого ребра для несмежных вершин появляется один простой цикл.
- [math]G[/math] — граф, отличный от [math] K_3 \cup K_1 [/math] и [math] K_3 \cup K_2 [/math] , а также [math] p = q + 1 [/math] , где [math]p[/math] — количество вершин, а [math]q[/math] количество ребер, и при добавлении любого ребра для несмежных вершин появляется один простой цикл.
Доказательство эквивалентности
Граф связен, поэтому любые две вершнины соединены путем. Граф ацикличен, значит путь единственен, а также прост, поскольку никакой путь не может зайти в одну вершину два раза, потому что это противоречит ацикличности.
Очевидно, что граф связен. Докажем по индукции, соотношение [math]p = q + 1[/math] . Утверждение очевидно для связных графов с одной и двумя вершинами. Предположим, что оно верно для графов, имеющих меньше [math]p[/math] вершин. Если же граф [math]G[/math] имеет [math]p[/math] вершин, то удаление из него любого ребра делает граф [math] G [/math] несвязным в силу единственности простых цепей; более того, получаемый граф будет иметь в точности две компоненты. По предположению индукции в каждой компоненте число вершин на единицу больше числа ребер. Таким образом, [math] p = q + 1 [/math] .
Очевидно, что если граф связен и ребер на одно меньше, чем вершин, то он ацикличен. Преположим, что у нас есть p вершин, и мы добавляем ребра. Если мы добавили ребро для получения цикла, то добавили второй путь между парой вершин, а значит нам не хватит его на добавление вершины и мы получим не связный граф, что противоречит условию.
[math]G[/math] — ациклический граф, значит каждая компонента связности графа является деревом. Так как в каждой из них вершин на единицу больше чем ребер, то [math] p = q + k [/math] , где [math]k[/math] — число компонент связности. Поскольку [math] p = q + k [/math] , то [math] k = 1 [/math] , а значит [math]G[/math] — связен. Таким образом наш граф — дерево, у которого между любой парой вершин есть единственный простой путь. Очевидно, при добавлении ребра появится второй путь между парой вершин, то есть мы получим цикл.
Поскольку [math] K_p [/math] для [math] p \gt 3 [/math] содержит простой цикл, то [math]G[/math] не может им являться. [math]G[/math] связен, так как в ином случае можно было бы добавить ребро так, что граф остался бы ациклическим.
Докажем, что любые две вершины графа соединены единственной простой цепью, а тогда поскольку [math] 2 \Rightarrow 3 [/math] , получим [math] p = q + 1 [/math] . Любые две вершины соединены простой цепью, так как [math]G[/math] — связен. Если две вершины соединены более чем одной простой цепью, то мы получим цикл. Причем он должен являться [math] K_3 [/math] , так как иначе добавив ребро, соединяющее две вершины цикла, мы получим более одного простого цикла, что противоречит условию. [math] K_3 [/math] является собственным подграфом [math]G[/math] , поскольку [math]G[/math] не является [math] K_p [/math] для [math] p \gt 3 [/math] . [math]G[/math] — связен, а значит есть вершина смежная с [math] K_3 [/math] . Очевидно, можно добавить ребро так, что образуется более одного простого цикла. Если нельзя добавить ребра так, чтобы не нарушалось исходное условие, то граф [math]G[/math] является [math]K_p[/math] для [math] p \gt 3 [/math] , и мы получаем противоречие с исходным условием. Значит, любые две вершины графа соединены единственной простой цепью, что и требовалось.
Если [math]G[/math] имеет простой цикл, то он является отдельной компонентой [math]K_3[/math] по ранее доказанному. Все остальные компоненты должны быть деревьями, но для выполнения соотношения [math] p = q + 1 [/math] должно быть не более одной компоненты отличной от [math]K_3[/math] , так как в [math]K_3[/math] [math] p = q = 3 [/math] . Если это дерево содержит простой путь длины 2, то в [math]G[/math] можно добавить ребро так, что образуются два простых цикла. Следовательно, этим деревом является [math]K_1[/math] или [math]K_2[/math] . Значит [math]G[/math] является [math]K_3 \cup K_1[/math] или [math]K_3 \cup K_2[/math] , которые мы исключили из рассмотрения. Значит наш граф ацикличен. Если [math]G[/math] ациклический и [math] p = q + 1 [/math] , то из [math] 4 \Rightarrow 5 [/math] и [math] 5 \Rightarrow 6 [/math] верно, что [math]G[/math] — связен. В итоге получаем, что [math]G[/math] является деревом по определению.
См. также
Источники информации
- Харари Ф. Теория графов. /пер. с англ. — изд. 2-е — М.: Едиториал УРСС, 2003. — 296 с. — ISBN 5-354-00301-6
- Википедия — дерево(теория графов)
Источник