Разлагане на дървета
Групиране на дървета или клъстериране на дървета (Дехтер & Перла[14]) трансформира произволен-AR проблем в ациклична форма в представяне под формата на двойна графика чрез образуване на клъстери от променливи, чиято графика на връзките има структурата deревете. -ary ER проблем се нарича ацикличен, ако неговата графика на основното ограничение има следнотоИмоти:
- акордалност: всеки цикъл, съдържащ поне 4 върха сдържи акорд (ръб, свързващ 2 непоследователни върха на цикъл).
- съответствие: всяка от максималните клики на графиката съответстваедно ограничение в ER проблема.
Алгоритъм за триангулация (Тарджан & Янакакис[петнадесет]) може да се използваизползва се за постигане на посочените свойства с помощта на две стъпки: а) Намерете подреждането с максимална степен (максимална мощност) и б) повтаря сеСилно добавете ръбове между върховете, свързващи върховете с болкапоръчка съгласно посочената поръчка. На фигури 10.12 a и b (от (Дехтер & Перла[16])), съответно, основната графика на ограниченията на ER проблема е показана преди и след процеса на триангулация.
Максималните кликвания на тази графика са клъстери, които сналагат ограничения върху трансформирания ER проблем (виж фигура 10.10 а).
Фигура: 10.9. Изграждане на хордова първична графика.
За да се изгради дърво от това представяне, е достатъчно да се премахнат ненужните ръбове от графиката, т.е. онези ръбове, премахването на които не засяга набора от решения.
В двойна графика дъгата е излишна, ако множеството променливи, с които е обозначена, е общо за всички дъги на отделен път междув очакване на крайните върхове на дъгата.
Фигура: 10.10. Изграждане на дърво от двойна графика.
На фиг. 10.10 б) показва един начин за конструиране на дърво за проблема с ER.