Arbre PQ

Un arbre PQ représente ses permutations via les réarrangements autorisés des enfants de ses nœuds : les enfants d'un nœud P peuvent être permutés de manière arbitraire. Les enfants d'un nœud Q peuvent être replacés en ordre inverse, mais ne peuvent pas être réorganisés autrement. Un arbre PQ représente tous les réarrangements de feuilles qui peuvent être obtenus par une séquence quelconque de ces deux opérations. Un arbre PQ qui a de nombreux nœuds P et Q peut représenter des sous-ensembles compliqués de l'ensemble de tous les réarrangements possibles. Cependant, tous les arrangements peuvent ne pas être représentables de cette manière; par exemple, si un arrangement est représenté par un arbre PQ, l'inverse de l'arrangement doit également être représenté par le même arbre.

Les arbres PQ sont utilisés pour résoudre des problèmes où le but est de trouver un ordre qui satisfait diverses contraintes. Dans ces problèmes, les contraintes sur l'ordre sont ajoutées une à la fois, en modifiant la structure arborescente PQ de telle sorte qu'elle ne représente que les commandes satisfaisant la contrainte. Les applications des arbres PQ incluent la création d'une carte de contig à partir de fragments d'ADN[2], les réarrangements[3]^,[4], les tests sur une matrice pour les propriétés consécutives[1], la reconnaissance des graphes d'intervalle[1] et le test de planarité d'un graphe^{[réf. nécessaire]}[5]^,[6].

L'arbre PQ représentant [1 (2 3 4) 5].

Si les feuilles d'un arbre PQ sont toutes enfant d'un nœud P, tous les ordres sont possibles. Si les feuilles sont toutes enfant d'un nœud Q, seul l'ordre et son inverse sont autorisés. Si des nœuds a,b,c sont connectés à un nœud P, qui est connecté à un nœud P racine, toutes les autres feuilles étant connectés directement à la racine, alors tout ordre où a,b,c sont contigus est autorisé.

Lorsqu'une présentation graphique n'est pas disponible, les arbres PQ sont notés à l'aide de listes imbriquées entre parenthèses. Chaque paire de crochets représente un nœud Q et chaque paire de parenthèses arrondies représente un nœud P. Les feuilles sont les éléments non parenthésés. L'arbre représenté ci-contre est équivalent à la liste [1 (2 3 4) 5]. Cet arbre PQ représente les douze permutations suivantes sur l'ensemble {1, 2, 3, 4, 5} :

12345, 12435, 13245, 13425, 14235, 14325, 52341, 52431, 53241, 53421, 54231, 54321.

La notion d'arbre PC, développée par Wei-Kuan Shih et Wen-Lian Hsu[7], est une généralisation de l'arbre PQ. Comme l'arbre PQ, il représente les permutations par le réarrangement des nœuds d'un arbre, les éléments étant représentés aux feuilles de l'arbre. Contrairement à l'arbre PQ, l'arbre PC n'est pas enraciné. Les nœuds adjacents à un nœud étiqueté P peuvent être réorganisés arbitrairement comme dans l'arbre PQ, tandis que les nœuds adjacents à un nœud étiqueté C ont un ordre cyclique fixe et ne peuvent être réorganisés qu'en inversant cet ordre. Ainsi, un arbre PC ne peut représenter que des ensembles ordonnés clos par permutation circulaire ou inversion d'un arrangement. Cependant, un arbre PQ sur n éléments peut être simulé par un arbre PC sur n + 1 éléments, où l'élément additionnel sert de racine à l'arbre PC. Les opérations de structure de données nécessaires pour exécuter un algorithme de test de planarité sur des arbres PC sont un peu plus simples que les opérations correspondantes sur des arbres PQ.