2011-09-09

点の数、辺の数、面の数

とはいえ、一応、メモ
１次元最小全域木では、頂点数に対して、辺の数は(木だから)
- これは、このように考える
- 点があって、辺がない状態から、辺を１つ増やすと、点が２つ結ばれる
- それに連結するように辺を１つ増やすと、連結な点の数が１つ増える
- したがって、辺の数とつながっている点の数をペアで表せば(1,2),(2,2+1),(3,2+1+1),...,(n-1,n)となり、n-1本でn個の頂点がつながる
- 連結作業の回数が(n-1)回である
２次元最小全域木では？
- 初めに、３頂点を選び、３本の辺、１個の三角形を作るところから始める
- ついで、この三角形の辺を共有する三角形を連結することで、点を増やすと、点が１個増えて、辺は２個増える。三角形は１個増える
- したがって、三角形の数、辺の数、点の数を数のトリオで表せば、(1,3,3)が初期状態で、(1+1,3+2,3+1),(1+1+1,3+2+2,3+1+1),...,(n-2,3+2*(n-3),n)=(n-2,2n-3,n)
- 連結作業の回数が(n-2)回である
３次元最小全域木では？
- 初めに、４頂点を選び、４個の点、６本の辺、４個の面、１個の四面体を作るところから始める
- ついで、この四面体の面を共有する四面体を連結することで、点を増やすと、点が１個増えて、辺は３本増えて、面は３面増えて、四面体が１個増える
- したがって、四面体の数、三角形の数、辺の数、点の数を数のトリオで表せば、(1,4,6,4)が初期状態で、(1+1,4+3,6+3,4+1),(1+1+1,4+3+3,6+3+3,4+1+1),...,(n-3,4+3*(n-4),6+3*(n-4),4+(n-4))=(n-3,3n-8,3n-6,n)
- 連結作業の回数が(n-3)回である

~~-さらに高次にすると…~~
~~--連結作業の回数が(n-k)回であって~~
~~--(n-k,(n-(k-1))+(n-k),(n-(k-2))+(n-(k-1))+(n-k),(n-(k-3))+(n-(k-2))+(n-(k-1))+(n-k),...,(n-1)+(n-2)+...(n-k),n)~~
~~-これがk=n-1になると~~
~~--(1,3,6,...,n(n-1)/2,n)= $(\frac{2(2-1)}{2},\frac{3(3-1)}{2},\frac{4(4-1)}{2},...,\frac{n(n-1)}{2},n)$ になるようだ~~

さて、１次元最小全域木を下敷きにして、２次元最小全域木を、それを下敷きにしてさらに３次…と高次化するとしたときのプロセスを考える
点だけがあるとき、ある基準で、「２つの」「点」を選んで、そこに「辺」を１本置く
「辺」があって、「全域」になっていないので、「辺」とそれに連結している「点」とを核として、核を広げて行く
まだ核に含まれていない「辺」があるとき、その「辺」を核に加えることができるかどうかを判断したい
加えられるのは、その「辺」の１端の「点」は核に含まれる
その「辺」の両端の２個の「点」は、「０次元的なもの〜点」に連結している(「点そのものである」)。また、「０次元的なもの〜点」が連結している、それより１次元低い「-1次元のもの」を共有するとき(「-1次元のもの」は『無』なので、この表現は、なにも共有しなくてもよい、ということである。しかしながら、より高次のときと表現をそろえるために、ここではあえてこのように書くことにする)、この「辺」は加える候補となる
これを繰り返して「全域」となったら、それが、１次元全域木である
さて、２次元全域木を作る。１次元全域木を下敷きにして作る
２次元全域木の核をまず作る
それは「三角形」である
１個の「三角形」である核からスタートする
これに「辺」を付け加える
付け加えられる「辺」は核に含まれない
付け加えられる「辺」の１端の「点」は核に含まれる
その「辺」の両端の２個の「点」は「１次元的なもの〜辺」に連結している(１次元全域木のレベルで)が、その「１次元的なもの〜辺」が「0次元的なもの〜点」を持ち、それらが共有されているとき、この「辺」は付け加えることができる
「辺」を付け加えると、新たに、「三角形」が１個できる
このようにして２次元全域木ができる
さて、３次元全域木を作る。２次元全域木を下敷きにして作る
３次元全域木の核をまず作る
それは「四面体」である
１個の「四面体」である核からスタートする
これに「辺」を付け加える
付け加えられる「辺」は核に含まれない
付け加えられる「辺」の１端の「点」は核に含まれる
その「辺」の両端の２個の「点」は「２次元的なもの面(三角形)」に連結している(２次元全域木レベルで)が、その「２次元的なもの〜面(三角形)」が「１次元的なもの〜辺」を持ち、それらが、共有されているとき、この「辺」は付け加えることができる
「辺」を付け加えると、新たに「四面体」が１個できるとともに、「面」が２個付け加わる