PQ-дерево
Перейти до навігації
Перейти до пошуку
PQ-дерево — структура даних для подання групи перестановок, кореневе планарне дерево. Висячі вершини в ньому відповідають подаваним елементам. Решта вершин мають позначку або . Вершини з позначкою мають принаймні 3 нащадки, а вершини з позначкою мають принаймні 2 нащадки. У PQ-дереві дозволяється як завгодно переставляти нащадків вершини з позначкою і обертати порядок нащадків вершини з позначкою .
PQ-дерева використовують для пошуку перестановок, обмеження на які стають відомими поступово, одне за іншим. Такі задачі виникають при відтворенні ДНК і перевірці планарності графа.