Arborele PQ

Un arbore PQ  este o structură de date pentru reprezentarea unui grup de permutare . Acesta este un arbore planar înrădăcinat . Vârfurile atârnând în el reprezintă elemente permutabile. Restul vârfurilor sunt etichetate fie , fie . Nodurile marcate au cel puțin 3 copii, iar nodurile marcate au cel puțin 2 copii. Într-un arbore PQ, este permisă rearanjarea descendenților unui vârf marcat în mod arbitrar și inversarea ordinii descendenților unui vârf marcat .

Arborii PQ sunt folosiți pentru a găsi permutări, restricțiile asupra cărora sunt cunoscute treptat, una câte una. Astfel de probleme apar la recrearea ADN-ului și la verificarea planarității unui grafic.

Articole

• Booth, Kellogg S. și Lueker, George S. Testarea proprietăților consecutive, a graficelor de interval și a planarității graficului folosind algoritmi PQ-tree  //  Journal of Computer and System Sciences. - 1976. - Vol. 13 , nr. 3 . — P. 335–379 . - doi : 10.1016/S0022-0000(76)80045-1 .
• Shih, Wei-Kuan și Hsu, Wen-Lian. Un nou test de planaritate  (engleză)  // Theoretical Computer Science (jurnal). - 1999. - Vol. 223 . - P. 179-191 . - doi : 10.1016/S0304-3975(98)00120-0 . Arhivat din original pe 12 septembrie 2006.
• Mehta, DP și Sahni, S. 32. PQ Trees, PC Trees, and Planar Graphs // Handbook of Data Structures and Applications. — Taylor & Francis, 2004. — ISBN 9781420035179 .
• 3.2. Testarea planarității // Grafice plane: Teorie și algoritmi / ed. de T. Nisizeki şi N. Chiba. - Olanda de Nord, 1988. - ISBN 0-444-702121 .