典型タグ

木の均衡分離点と重心分解

非負重みの各成分を半分以下にする一点を選ぶ。頂点数を重みとし各成分で繰り返すと、対数深さの重心分解を得る。

この典型を扱う単元: 木の均衡分離点から重心分解へ進む

検索別名: centroid decomposition、tree separator、均衡分離点、重み付き重心、重心分解

未知問からこの典型を見つける手掛かり

扱う対象
  • 木
  • 連結成分
  • 部分木サイズ
  • 重心
使う手掛かり
  • separator
  • 再帰
  • 半分以下
  • 除いた各成分
保つ不変量
  • 成分サイズ
  • 親を設定
  • 重心
  • 高さ.*log
求めるもの
  • 分解木
  • 構成
  • 親配列
  • 距離query
適用しない条件
個別の除外条件の記載はありません。扱う対象と使う手掛かりから適用を判断してください。
分類・前提・学習成果

分類と直接の前提

概念上の親: 木モデルと構造

    関連する典型

      学習成果と学習単位

      代表問題

      この典型の考え方を具体的な問題で確かめるための入口です。

      関連問題

      この典型が主タグまたは補助タグとして付いている問題です。