PQ木は、要素の集合における順列の族を表す木ベースのデータ構造で、 1976年にケロッグ・S・ブースとジョージ・S・ルーカーによって発見され命名されました。 [ 1 ]これは根付きラベル付き木であり、各要素は葉ノードの1つで表され、葉以外のノードはそれぞれPまたはQのラベルが付けられます。APノードには少なくとも2つの子があり、Qノードには少なくとも3つの子があります
PQ木は、そのノードの子ノードを任意に並べ替えることで、その順列を表現します。Pノードの子ノードは任意の順序で並べ替えることができます。Qノードの子ノードは逆順に並べ替えることはできますが、それ以外の順序で並べ替えることはできません。PQ木は、これら2つの操作を任意の順序で実行することで実現できるすべてのリーフノードの順序を表現します。多数のPノードとQノードを持つPQ木は、すべての可能な順序の集合の複雑な部分集合を表現することができます。ただし、すべての順序集合がこの方法で表現できるわけではありません。例えば、ある順序をPQ木で表現する場合、その逆の順序も同じ木で表現する必要があります。
PQ木は、様々な制約を満たす順序付けを求める問題を解くために使用されます。これらの問題では、PQ木構造を、制約を満たす順序付けのみを表すように修正することで、順序付けに関する制約を一つずつ追加していきます。PQ木の応用としては、DNA断片からコンティグマップを作成する、[ 2 ]、行列の連続する一の性質をテストする、区間グラフを認識する、グラフが平面グラフであるかどうかを判断するなどがあります。[ 1 ]
例と表記
PQツリーのすべてのリーフがルートPノードに直接接続されている場合は、あらゆる順序付けが可能です。すべてのリーフがルートQノードに直接接続されている場合は、1つの順序とその逆の順序付けのみが可能です。ノードa、b、cがPノードに接続され、さらにそのPノードがルートPノードに接続され、他のすべてのリーフノードがルートに直接接続されている場合は、a、b、cが連続する任意の順序付けが可能です。
グラフィカルな表現が不可能な場合、PQ木は入れ子になった括弧付きリストで表記されることが多い。対応する角括弧のペアはそれぞれQノードを表し、対応する丸括弧のペアはそれぞれPノードを表す。葉はリストの括弧外の要素である。左の図は、この表記法では[1 (2 3 4) 5]と表される。このPQ木は、集合{1, 2, 3, 4, 5}における以下の12個の順列を表す。
- 12345、12435、13245、13425、14235、14325、52341、52431、53241、53421、54231、54321。
PCツリー
Wei-Kuan ShihとWen-Lian Hsuによって開発された PC 木は、PQ木のより最近の一般化です。PQ 木と同様に、PC 木は木内のノードの順序を変更することで順列を表現し、要素は木の葉で表現されます。PQ 木とは異なり、PC 木には根がありません。P というラベルの付いた葉以外のノードに隣接するノードは、PQ 木の場合と同様に任意に順序を変更できますが、C というラベルの付いた葉以外のノードに隣接するノードは、固定の循環順序を持ち、この順序を逆にすることによってのみ順序を変更できます。したがって、PC 木は、集合内の循環順列または順序の反転も集合内に含まれるような順序の集合のみを表現できます。ただし、n個の要素を持つ PQ 木は、 n + 1 個の要素を持つ PC 木でシミュレートでき、追加の要素は PC 木の根として機能します。 PCツリー上で平面性テストアルゴリズムを実行するために必要なデータ構造操作は、PQツリー上の対応する操作よりもいくらか単純です。[ 3 ]
参照
参考文献
- ^ a b Booth, Kellogg S.; Lueker, George S. (1976). 「PQ木アルゴリズムを用いた連続1の性質、区間グラフ、グラフ平面性のテスト」 . Journal of Computer and System Sciences . 13 (3): 335– 379. doi : 10.1016/S0022-0000(76) 80045-1
- ^ Karp, Richard M. (1993). 「ゲノムのマッピング：分子生物学におけるいくつかの組み合わせ問題」. Kosaraju, S. Rao ; Johnson, David S. ; Aggarwal, Alok (編).第25回ACM計算理論シンポジウム議事録, 1993年5月16日～18日, 米国カリフォルニア州サンディエゴ. Association for Computing Machinery. pp. 278– 285. doi : 10.1145/167088.167170 .
- ^ Shih, Wei-Kuan; Hsu, Wen-Lian (1999). 「新しい平面性テスト」(PDF) .理論計算機科学. 223 ( 1–2 ): 179– 191. doi : 10.1016/S0304-3975(98)00120-0 .
外部リンク
