Arbre PQ

Un arbre PQ représente un ensemble des 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, il existe des sous-ensembles de permutations qui ne sont pas représentables de cette manière; en effet, 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[1] - [5] - [6].

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

Les feuilles sont étiquetées par les éléments à permuter. Si les feuilles d'un arbre PQ sont toutes enfants d'un nœud P, tous les ordres sont possibles. Si les feuilles sont toutes enfants d'un nœud Q, seuls l'ordre de gauche à droite et l'ordre inverse de droite à gauche 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ées 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]. Etudions cet arbre PQ pour voir quel est l'ensemble de permutations correspondant. Pour le fils P, on autorise donc les permutations :

234, 243, 324, 342, 423, 432.

Pour le nœud racine, qui est un noeud Q, on distingue deux :

• Les permutations obtenues où les enfants sont pris dans l'ordre de gauche à droite : 1, puis P puis 5. On concatène 1, avec une permutation pour le fils P puis 5, i.e. on considère les permutations : 12345, 12435, 13245, 13425, 14235, 14325
• Les permutations obtenues où les enfants sont pris dans l'ordre de droite à gauche : 5, puis P puis 1. On considère les permutations : 52341, 52431, 53241, 53421, 54231, 54321.

Pour résumer, 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 la notion d'arbre PQ. Comme un arbre PQ, un arbre PC 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.