« [P2P]P2P・DHT懇親会 in 関西(京都.6/7[木]) | トップページ | [P2P]Skype&BitTorrent日本オフィスツアーの開催について »

2007.06.25

[数学]グラフ(図形)の頂点を一意に番号付けする方法の提案

P2Pの関連で複雑系ネットワークについても色々と考えているのだが、あるとき図形やグラフの頂点を一意に番号付けできるか、もしできるのであればその方法はなんだろうか、と考えることがあった。この前の土曜日の夜ふと今の問題が頭に浮かび、2時間ぐらい眠れなくなった。今回はある制限下で図形またはグラフの頂点を番号付けする方法を提案したい。またこの番号付けは平行移動、回転する変換(すなわち図形の形を崩さない変換、アフィン変換の例)に対して不変としたい。

制限は以下の通り
・ユークリッド空間に図形は存在する
・同一座標には高々ひとつの頂点しか存在しない

ただし、後でわかるように距離空間で内積が定義できれば、今回の方式は成り立つ(あるいは拡張できる)事が予想される。

ここでは2次元を考えてみる。おそらく多次元でも拡張可能だろう。

番号付けの手順
1.各頂点の座標の平均(すわなち重心)を求める。これをGと呼ぶ事にする。
2.各頂点の中でGから一番近い(*距離)点を求める。この点をAとする。
3.GからみてAを基点に時計回りの方向に存在する各頂点について順次番号付けをする。ただし、GからみてAを基点に同じ角度に複数頂点が存在する場合、Gから近い点から番号付けをする。

この方法で問題になるのは、Gから一番近い点が複数存在する場合である。今その点をB、Cとしよう。次のような処理でどちらを最初に番号付けするか決める。

1.GからみてBを基点に時計回りの方向に存在する各頂点を順次番号付けする。これをB1,B2....とする。
2.GからみてCを基点に時計回りの方向に存在する各頂点を順次番号付けする。これをC1,C2....とする。
3.b1=(B-G)・(B1-G)、c1=(C-G)・(C1-G)を計算する。ただし・は内積を表す。b1<c1であれば、Bを最初に番号付けする。b1=c1ならb2,c2を計算し同様の処理をする。
4.頂点の数をNとすると、b1=c1、b2=c2、.....b{n-1}=c{n-1}ならGを中心B⇒Cに回転することにおける対称性(回転対称性)が存在することになる。ゆえに BとCをどちらを最初に番号付けしても問題ない。

回転や平行移動に対して距離や内積は不変である事に注意。今回の方法は実は相似変換(拡大・縮小)しても番号付けは不変である。興味のある方は一般的なアフィン変換について考えて欲しい。

*ただしここで言う不変のニュアンスについては注意が必要。というのは、重心から一番近い点が複数ある場合で回転対称性がある図形の一部では、番号付けの始点が複数パターンありうるからである。

問題はN次元に拡張した場合、角度をどう考えるか、あるいはGから一番近い点が複数存在するときのロジックをどう拡張するかということが課題である。もしかすると外積やそのノルムなどを利用する事になるかもしれない。

なお一番やりたかったのは、リンクの情報しかない一般的なグラフの頂点の番号付けである。もはや頂点には座標の概念がない。おそらく隣接行列を用い、Jordanの標準形をうまく利用して番号付けをすることになるだろう。こちらももう少し考えてみたい。

|

« [P2P]P2P・DHT懇親会 in 関西(京都.6/7[木]) | トップページ | [P2P]Skype&BitTorrent日本オフィスツアーの開催について »

P2P」カテゴリの記事

コメント

コメントを書く



(ウェブ上には掲載しません)


コメントは記事投稿者が公開するまで表示されません。



トラックバック

この記事のトラックバックURL:
http://app.cocolog-nifty.com/t/trackback/18781/15559960

この記事へのトラックバック一覧です: [数学]グラフ(図形)の頂点を一意に番号付けする方法の提案:

« [P2P]P2P・DHT懇親会 in 関西(京都.6/7[木]) | トップページ | [P2P]Skype&BitTorrent日本オフィスツアーの開催について »