PQ-дерево

PQ-дерево — структура даних для подання групи перестановок, кореневе планарне дерево. Висячі вершини в ньому відповідають подаваним елементам. Решта вершин мають позначку ${\displaystyle P}$ або ${\displaystyle Q}$. Вершини з позначкою ${\displaystyle Q}$ мають принаймні 3 нащадки, а вершини з позначкою ${\displaystyle P}$ мають принаймні 2 нащадки. У PQ-дереві дозволяється як завгодно переставляти нащадків вершини з позначкою ${\displaystyle P}$ і обертати порядок нащадків вершини з позначкою ${\displaystyle Q}$.

Граф (a) і його PQ-дерево (b)

PQ-дерево, яке описує вкладений список [1 (2 3 4) 5]

PQ-дерева використовують для пошуку перестановок, обмеження на які стають відомими поступово, одне за іншим. Такі задачі виникають при відтворенні ДНК і перевірці планарності графа.

Статті

• Booth, Kellogg S. and Lueker, George S. Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms // Journal of Computer and System Sciences. — 1976. — Vol. 13, no. 3 (16 June). — P. 335–379. — DOI:10.1016/S0022-0000(76)80045-1.
• Shih, Wei-Kuan and Hsu, Wen-Lian. A new planarity test // Theoretical Computer Science (journal). — 1999. — Vol. 223 (16 June). — P. 179–191. — DOI:10.1016/S0304-3975(98)00120-0. з джерела 12 вересня 2006.
• Mehta, D.P. and Sahni, S. 32. PQ Trees, PC Trees, and Planar Graphs // Handbook of Data Structures and Applications. — Taylor & Francis, 2004. — .
• 3.2. Planarity testing // Planar Graphs: Theory and Algorithms / ed. by T. Nishizeki and N. Chiba. — North-Holland, 1988. — .