PQ-дерево

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

PQ дерево — структура данных для представления группы перестановок. Это корневое планарное дерево. Висячие вершины в нем представляют переставляемые элементы. Остальные вершины имеют пометку либо P, либо Q. Вершины с пометкой Q имеют по крайней мере 3 потомка, а вершины с пометкой P имеют по крайней мере 2 потомка. В PQ дереве разрешается как угодно переставлять потомков вершины с пометкой P и обращать порядок потомков вершины с пометкой Q.

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. — P. 335–379.
  • Shih, Wei-Kuan and Hsu, Wen-Lian A new planarity test (англ.) // Theoretical Computer Science (journal). — 1999. — Vol. 223. — P. 179–191. — DOI:10.1016/S0304-3975(98)00120-0.
  • Mehta, D.P. and Sahni, S. 32. PQ Trees, PC Trees, and Planar Graphs // Handbook of Data Structures and Applications. — Taylor & Francis, 2004. — ISBN 9781420035179.