PQ tree

From Free net encyclopedia

A PQ tree is a special kind of tree data structure. It is a rooted, labeled tree, with non-leaf nodes labelled P or Q. A P node has at least two children, and a Q node has at least three children. A PQ tree represents a set of possible orderings for the leaf nodes. The children of a P node can be reordered in any way. The children of a Q node can be put in reverse order. A PQ tree represents all leaf node orderings that can be achieved by any sequence of these two operations.

Image:Pq-tree-5-leaves.png

Examples: If all the leaves of a PQ tree are connected directly to a root P node then all possible orderings are allowed. If all the leaves are connected directly to a root Q node then only one order (and its reverse) is allowed. If nodes a,b,c connect to a P node, which connects to a root P node, with all other leaf nodes connected directly to the root, then any ordering where a,b,c are contiguous is allowed. A PQ tree with many P and Q nodes can represent complicated subsets of the set of all possible orderings.

PQ trees are used to solve problems where the goal is to find an ordering that satisfies various constraints. Creating a contig map from DNA fragments is one example. Determining if a graph is planar is another. Note that embedding a graph in the plane determines a clockwise ordering for the neighbors of each node.

[edit]

Notation

Where graphical presentation is unavailable PQ Trees are often noted using nested parenthesized lists. Square parentheses represents a Q node and regular ones represents P nodes. Leaves are non-parentheses elements of the lists. The image on the left if represented by [1 (2 3 4) 5].

[edit]

Abstract algebra

PQ Trees represent some subsets of the symmetric group. The PQ Tree [1 (2 3 4) 5] represents the twelve following permutations on the set {1, 2, 3, 4, 5}:

  • 1 2 3 4 5
  • 1 2 4 3 5
  • 1 3 2 4 5
  • 1 3 4 2 5
  • 1 4 2 3 5
  • 1 4 3 2 5
  • 5 2 3 4 1
  • 5 2 4 3 1
  • 5 3 2 4 1
  • 5 3 4 2 1
  • 5 4 2 3 1
  • 5 4 3 2 1

Note that not all subsets of the symmetric group can be represented by a PQ Tree. As an example it is not possible to represent a set containing the identity permutation with also including the reversed identity permutation. Concretely, we can represent {123, 321} by the tree [1 2 3] but we can't represent {123}.

[edit]

Reference

K.S. Booth and G.S. Lueker. Testing for the Consecutive Ones Property, Interval Graphs, and Graph Planarity Using PQ- Tree Algorithms. Journal of Computer and Systems Sciences, 13:335-379, 1976.Template:Compu-sci-stub

Retrieved from "http://www.netipedia.com/index.php/PQ_tree"