PQ-träd

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 17 september 2015; kontroller kräver 4 redigeringar .

Ett PQ-träd  är en datastruktur för att representera en permutationsgrupp . Detta är ett rotat plant träd . De dinglande hörnen i den representerar föränderliga element. Resten av hörnen är märkta med antingen , eller . Markerade hörn har minst 3 barn och markerade hörn har minst 2 barn. I ett PQ-träd är det tillåtet att omordna avkomlingarna till en vertex markerad godtyckligt och vända ordningen på avkomlingarna till en vertex markerad .

PQ-träd används för att hitta permutationer, vars begränsningar är kända gradvis, en efter en. Sådana problem uppstår när man återskapar DNA och kontrollerar planheten i en graf.

Artiklar