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

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

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

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

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