斉次グラフ - ryamadaのコンピュータ・数学メモ

次数３の斉次グラフ()
- ２頂点間に１本のエッジしか引かないものとする。エッジの２頂点は異なるものとする
- $G_3$ のノードを三角形と見立てれば、三角メッシュに相当する
- 四面体は頂点数４の完全グラフであって、 $G_3$ である
- 正八面体は頂点数６の $G_3$ である
- 頂点数 n の $G_3$ はいくつあるのだろう…
- こんな風に考えてみる
- $S_n(k)$ を頂点数 $n$ の $G_k$ の個数とする
- 今、 $S_{n+1}(k)$ は $S_n(k)$ のグラフに1個の頂点を加え、エッジの付け替えをして、 $G_{k+1}$ にすることにより達成するとする。そんな漸化方式で考える
- 1個の頂点を加え、それの次数が $k$ であるとき、 $G_k$ のノードからk個のノードを選ぶ。選ばれた $k$ 個のノードと新く加えるノードとにエッジを引くとともに、選ばれたノードから、それぞれ１本のエッジを除去したい
- エッジを１本除去すると、エッジの両端のノード２個からそれぞれエッジが除去されるので、 $k$ が奇数だとうまくない
- では、ノードを２つ加えることにする。 $k$ 本のエッジを選び、そのエッジはいずれもノードを共有していないようにする。結果、 $k$ 本のエッジ、 $2k$ 個のノードが選ばれ、 $k$ 本のエッジを取り除き、各々のエッジの両端ノードを加える２ノードのそれぞれにエッジを繋ぐ。どちらの端のノードをどちらの新規ノードに繋ぐかは場合わけになる
- このようにすることで、ノード数が奇数の $G_k$ 集合からノードを２つ増やした $G_k$ 集合が作れて、偶数から次の偶数のそれが作れる
- これが、悉皆性を保証しているならば(まだ確認して居ない)、これによって、数え上げ、 $S_n(k)$ は求まりそうだ
等面積曲面の離散表現としての、斉グラフのバリエーション
- 今、ノード数 $n$ の $G_k$ があったとき２個のノードを加えたのち、２個のノードを除去することを考える。ノード数nの $G_k$ が二つ得られる。各ノードが合同の正三角形であるとすれば、何かしらの閉曲面を表している。２つの閉曲面表現としての $G_k$ は辺のつなぎ代えとして表現できるだろう。これが「離散的閉曲面変形」の１表現ではないだろうか？