noshi91のメモ

データ構造のある風景

木の平方分割、出来るもの出来ないもの

アルゴリズム

出来ない分割の例

  • 木に対して、頂点集合を V _ 0, V _ 1, \ldots V _ {k - 1} に分割する
    • V _ i がつながっている: V _ i 内の任意の頂点対のパスは V _ i に含まれる
    • | V _ i | が小さい: | V _ i | \in O ( \sqrt N )
    • k が小さい: k \in O ( \sqrt N )
    • 反例: スターグラフ


出来る分割の例

  • 根付き木に対して、頂点集合を V _ 0, V _ 1, \ldots V _ {k - 1} に分割する

    • V _ i がつながっている: V _ i 内の任意の頂点対のパスは V _ i に含まれる
    • | V _ i | が小さい: | V _ i | \in O ( \sqrt N )
    • 深さが小さい: 任意の頂点について根からのパスは O ( \sqrt N ) 個の V _ i によって被覆される

  • 木に対して、辺集合を E _ 0, E _ 1, \ldots E _ {k - 1} に分割する

    • E _ i がつながっている: E _ i の端点として現れる任意の頂点対のパスは E _ i に含まれる
    • | E _ i | が小さい: | E _ i | \in O ( \sqrt N )
    • k が小さい: k \in O ( \sqrt N )

  • 次数の最大値が d の木に対して、頂点集合を V _ 0, V _ 1, \ldots V _ {k - 1} に分割する

    • V _ i がつながっている: V _ i 内の任意の頂点対のパスは V _ i に含まれる
    • | V _ i | が小さい: | V _ i | \in O ( \sqrt {d N} )
    • k が小さい: k \in O ( \sqrt {d N} )
    • d が小さい木の例: 二分木 ( d \leq 3)


誤りの指摘や有用な例の追加を募集しています。