全域木

木のグラフにおける相関(2)鎖状のグラフと相関の関係

鎖状のグラフとは、枝分かれのない木グラフのこと ノードは1次元座標で表すこともできて、隣接するノードの位置座標の差をノード間距離と言う このようなノード数Nのグラフがあったとき、それぞれのノードの値を表す長さNのベクトルVを考える Vの値がノード…

木のグラフにおける相関(1)木グラフを線分成分の木として取り扱う

木のグラフがある ノードに値が与えられている 木の上で、この値が順序よく並んでいるのかを評価したい そのために、次のようにする ノードの並びのうち、値が昇順(降順でもよい)になっている鎖状のセグメントに分割する そのセグメントを1つのノードとみた…

木のグラフを操作する

木はグラフ 全域木は、すべてのノードが連結な木グラフ ノード数Nに対してエッジ数はN-1 すべてのノードは少なくても1個の隣接ノードを持つ 辺の取り方を考える 木グラフをだんだんに大きくしていく 初めはノードなし ノード数1個の木グラフを作る N個のノ…

木のグラフを操作する(2)

木を作ってから距離行列を作る すべての辺の長さを1で考えれば、ペアの距離のうち、木の辺の数のペアの距離が1 残りののペアの長さを2,3,...で分配するわけだが、その分配の仕方は、木の構造(枝分かれの様子)と関係する情報になる ペア間距離はigraphパッ…

全域木更新問題

全域木更新問題という問題設定がある→こちら