PQ fa
Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt hozzászólók, és jelentősen eltérhet a 2015. szeptember 17-én felülvizsgált
verziótól ; az ellenőrzések 4 szerkesztést igényelnek .
A PQ fa egy adatstruktúra egy permutációs csoport megjelenítésére . Ez egy gyökeres sík fa . A benne lévő lógó csúcsok permutálható elemeket képviselnek. A többi csúcs vagy , vagy feliratú . A megjelölt csúcsoknak legalább 3, a megjelölt csúcsoknak pedig legalább 2 gyermekük van. A PQ-fában megengedett a tetszőlegesen megjelölt csúcs leszármazottainak átrendezése és a megjelölt csúcs leszármazottainak sorrendjének megfordítása .
A PQ-fák olyan permutációk keresésére szolgálnak, amelyek korlátozásai fokozatosan, egyenként ismertek. Ilyen problémák merülnek fel a DNS újraalkotásakor és a gráf síkságának ellenőrzésekor.
Cikkek
- Booth, Kellogg S. és Lueker, George S. Testing for the consecutive one property, interval graphs and graph planarity using PQ-tree algoritms // Journal of Computer and System Sciences. - 1976. - 1. évf. 13 , sz. 3 . — P. 335–379 . - doi : 10.1016/S0022-0000(76)80045-1 .
- Shih, Wei-Kuan és Hsu, Wen-Lian. Új síksági teszt (angol) // Theoretical Computer Science (folyóirat). - 1999. - 1. évf. 223 . - P. 179-191 . - doi : 10.1016/S0304-3975(98)00120-0 . Az eredetiből archiválva: 2006. szeptember 12.
- Mehta, DP and Sahni, S. 32. PQ Trees, PC Trees, and Planar Graphs // Handbook of Data Structures and Applications. — Taylor és Francis, 2004. — ISBN 9781420035179 .
- 3.2. Síksági vizsgálat // Planar Graphs: Theory and Algorithms / szerk. T. Nishizeki és N. Chiba. - Észak-Hollandia, 1988. - ISBN 0-444-702121 .