PQ дерево
Материал из Википедии — свободной энциклопедии
PQ дерево — структура данных для представления группы перестановок. Это корневое планарное дерево. Висячие вершины в нем представляют переставляемые элементы. Остальные вершины имеют пометку либо P, либо Q. Вершины с пометкой Q имеют по крайней мере 3 потомка, а вершины с пометкой P имеют по крайней мере 2 потомка. В PQ дереве разрешается как угодно переставлять потомков вершины с пометкой P и обращать порядок потомков вершины с пометкой Q.
PQ деревья используются для поиска перестановок, ограничения на которые становятся известны постепенно, одно за другим. Такие задачи возникают при восcоздании ДНК и проверке планарности графа.
[править] Статьи
- 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. — Т. 13. — С. 335–379.
- Shih, Wei-Kuan and Hsu, Wen-Lian A new planarity test // Theoretical Computer Science. — 1999. — Т. 223. — С. 179–191.