PQ-дерево — структура даних для подання групи перестановок, кореневе планарне дерево. Висячі вершини в ньому відповідають подаваним елементам. Решта вершин мають позначку або . Вершини з позначкою мають принаймні 3 нащадки, а вершини з позначкою мають принаймні 2 нащадки. У PQ-дереві дозволяється як завгодно переставляти нащадків вершини з позначкою і обертати порядок нащадків вершини з позначкою .
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: .
- Shih, Wei-Kuan and Hsu, Wen-Lian. A new planarity test // Theoretical Computer Science (journal). — 1999. — Vol. 223 (16 June). — P. 179–191. — DOI: . з джерела 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. — .
Це незавершена стаття з інформатики. Ви можете проєкту, виправивши або дописавши її. |
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет