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, Інтернет
PQ derevo struktura danih dlya podannya grupi perestanovok koreneve planarne derevo Visyachi vershini v nomu vidpovidayut podavanim elementam Reshta vershin mayut poznachku P displaystyle P abo Q displaystyle Q Vershini z poznachkoyu Q displaystyle Q mayut prinajmni 3 nashadki a vershini z poznachkoyu P displaystyle P mayut prinajmni 2 nashadki U PQ derevi dozvolyayetsya yak zavgodno perestavlyati nashadkiv vershini z poznachkoyu P displaystyle P i obertati poryadok nashadkiv vershini z poznachkoyu Q displaystyle Q Graf a i jogo PQ derevo b PQ derevo yake opisuye vkladenij spisok 1 2 3 4 5 PQ dereva vikoristovuyut dlya poshuku perestanovok obmezhennya na yaki stayut vidomimi postupovo odne za inshim Taki zadachi vinikayut pri vidtvorenni DNK i perevirci planarnosti grafa StattiBooth 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 z dzherela 12 veresnya 2006 Mehta D P and Sahni S 32 PQ Trees PC Trees and Planar Graphs Handbook of Data Structures and Applications Taylor amp 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 Ce nezavershena stattya z informatiki Vi mozhete dopomogti proyektu vipravivshi abo dopisavshi yiyi