ノードとエッジを区別しないグラフ

  • 昨日まで高次元最小全域木とかいうものを考えていた
  • 減次元完全グラフの連結によって、すべてのノードを覆うような作り方をもって、そのように呼ぶことにしていた
  • そのような高次元最小全域木では、k次元最小全域木からk+1次元最小全域木に上げるにあたって、2個のk次元完全グラフがk-1次元完全グラフを重なりとしているときに、辺を1本加えることで、k+1次元完全グラフを作る、という操作によって、実施した
  • これを、ごく低次元で考えてみることにする
  • ふつうのノードが2個あるときに、その2個のノードの間に辺を1本引く作業は、「ノード1個という完全グラフ」2個が「0次元完全グラフを共有している」ので辺でつないで、「1本の辺とその両端の2ノードという完全グラフ」を作る作業になっている
  • したがって、「ふつうの木」は、「ノード」が「ノード数1個の完全グラフ」であって、「エッジ」が「ノード数2個の完全グラフ」となっているとみなせば、「ノード」も「エッジ」も1・2次元完全グラフであって、それらがつながっているかどうかという情報で「木」を記述できる
  • k次元最小全域木から、k+1次元最小全域木を作っていく過程では、k+1次元完全グラフがk次元完全グラフを介して連結しつつ、k+1次元完全グラフに含まれるk次元完全グラフが、k+1次元完全グラフ化された部分に含まれていないk次元完全グラフとk-1次元完全グラフを介して連結している、という構造をもっている。
  • k-1,k,k+1次元完全グラフが相互の関係を持って存在しているというように記述できる、ということである