PQ-дерево
PQ-дерево — структура данных для представления группы перестановок. Это корневое планарное дерево. Висячие вершины в нем представляют переставляемые элементы. Остальные вершины имеют пометку либо , либо . Вершины с пометкой имеют по крайней мере 3 потомка, а вершины с пометкой имеют по крайней мере 2 потомка. В PQ-дереве разрешается как угодно переставлять потомков вершины с пометкой и обращать порядок потомков вершины с пометкой .
PQ-дерево, описывающее вложенный список
[1 (2 3 4) 5]
[1 (2 3 4) 5]
Граф (a) и его PQ-дерево (b)
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. — 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. — 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. — ISBN 9781420035179.
- 3.2. Planarity testing // Planar Graphs: Theory and Algorithms / ed. by T. Nishizeki and N. Chiba. — North-Holland, 1988. — ISBN 0-444-702121.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.