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

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

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

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

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

番号付けの手順
１．各頂点の座標の平均（すわなち重心）を求める。これをＧと呼ぶ事にする。
２．各頂点の中でＧから一番近い（＊距離）点を求める。この点をＡとする。
３．ＧからみてＡを基点に時計回りの方向に存在する各頂点について順次番号付けをする。ただし、ＧからみてＡを基点に同じ角度に複数頂点が存在する場合、Ｇから近い点から番号付けをする。

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

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

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

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

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

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