Mathematics

Bucky ボール

グラフ解析に対する興味あるものとして、Buckyボールがあります。これは、球面上に60個の点が分布し、かつ各点の最近傍点までの距離がすべて等しい関係を保っているものです。各々の点は、必ず3つの隣り合った点をもっています。Buckyボールは、つぎのように異なる4つの物理モデルに使われています。

• Buckminster Fullerにより発表された測地線ドーム
• C₆₀分子、ほぼ球面型をした60個の原子をもつ炭素の組成物
• 幾何学の中ので、切頭の20面体のもの
• スポーツでのサッカーボール

Buckyボールの隣接行列は60行60列の対称行列Bです。Bは、各行、各列各々3つの非ゼロ要素、総数180個の非ゼロ要素をもっています。この行列は、前述の物理オブジェクトと関連付られた重要なアプリケーションです。例えば、Bの固有値は、C₆₀の化学的な性質を調べるために使います。

Buckyボールの隣接行列を得るには、つぎのように入力します。

B = bucky;

60次で、5%の密度をもって、この行列はスパース手法を必ずしも必要としていません。しかし、これは、興味ある例題を与えます。

つぎのステートメントでBuckyボールの座標を得ます。

[B,v] = bucky;

このステートメントは、3空間内で単位平面上に等分布する60点のxyz座標からなるvを作成します。関数gplot は、これらの点を使って、Buckyボールグラフをプロットします。

gplot(B,v)
axis equal

ここでは、Buckyボールの中のノードをどのように番号付けしているのかわかりません。そのため、結果作成される隣接行列はグラフの表面や結合された対称性が明らかになりません。vで使われている番号付け法は、ボールの構造内の固有の多角形をベースにしています。

一つの多角形の頂点が1から5で番号付けされ、隣接多角形の頂点は6から10、等々になります。つぎの図は、半分のノード(半平面)に付けられた番号を示しています。すなわち、残りの半平面の番号付けは、赤道に関して反転して得られます。gplotの使用は、半分のノードを示すグラフを作成します。ユーザは、for ループを使って、ノード番号を加えることもできます。

k = 1:30;
gplot(B(k,k),v);
axis square
for j = 1:30, text(v(j,1),v(j,2), int2str(j)); end

Buckyボールの隣接行列の中の非ゼロ要素の位置のテンプレートを見るため、関数spyを使います。

spy(B)

このモデルが使うノード番号付け法は、構造の中の12多角形に対応する5つの要素をもった12グループに分けられるspyプロットを作成します。各々のノードは、自分自身の多角形の中で他の2つのノードと別の多角形の中で1つのノードと結合しています。一つの多角形の中で、ノードは連続する番号が付けられているので、Bの1つ上の対角要素と1つ下の対角要素のほとんどのものは非ゼロになります。そして、赤道に関しての番号付けの対称性は、反対角線に対してspyプロットが対称性を示すことで明らかになります。

スパース行列のグラフと特性

Bの行列のベキ乗のspyプロットは、スパース行列演算に関連した2つの重要な考え(full-inとdistance)を示します。spyは、これらの考えを表示する手助けになります。

spy(B^2)
spy(B^3)
spy(B^4)
spy(B^8)

Fill-inは、行列の乗算のような演算で生じます。複数の行列の積は、通常オリジナルのものよりも多くの非ゼロ要素をもちます。それで、より大きなストレージを必要とします。pを増加させると、B^p は、ゼロ要素部分を非ゼロ要素で埋めて、spy(B^p)は、より密になります。

グラフの中の2つのノード間のdistanceは、一つのノードから他のノードを得るために必要となるグラフ上でのステップ数です。Bのp乗のspyプロットは、distance p離れたノードを示します。pを増加すると、pステップでより多くのモードを得ることができます。Buckyボールに対して、B^8は、ほぼ完全なフルの型になります。逆対角要素の線対称の部分のみがゼロになり、これより8回のステップで球面上の反対側の球面を除いて、あるノードから他のどのノードでも得ることができるということを示しています。

隣接行列を使ったグラフ表示

空気の流れに関するモデル