グラフの特性量のデータベース(Graphical Characteristics Data Base : GCDB)の開発 -Multi-Layered Cyclic Fence Graph と特性量-

林 佳代子, 福田 詩織里, 長嶋 雲兵, 細矢 治夫

Return

1 はじめに

　化学の構造式に代表されるように、分子の化学的性質の多くはその分子構造に関係付けられている。もともと化学はトポロジカルな情報の記述を基本的表現形式として発展してきたといえる。構造式を一つの数学的表現として考えると、それはグラフであり、一つのグラフは、さまざまな数学的特性量を持つことが知られている [1]。
　グラフとは、いくつかの点と、それらの間を結ぶいくつかの辺とで構成される図形、またはそのような図形で表示される対象物のことであり、LadderGraph,Cyclic Fence Graph (CFG)[2], Multi-Layered Cyclic Fence Graph (MLCFG)[3]などいろいろな系列がある。しかし、有限個の点と辺をもつグラフの種類も「組合せ的爆発」によって膨大な数に膨れ上がっていく。グラフ理論や情報科学の分野では、このような沢山のグラフを識別するために、グラフの形状を比較するだけではなく、各グラフの特徴ともいえる特性量を計算して比較することが多い。 これまで、特性量の比較によって、グラフ間の相関関係が数多く見つけられてきたが、現状において特性量に関するデータは各グラフごとに別々のファイルに保存されており、その比較は全て手作業で行なわれている。よって、グラフの様々な種類の特性量を集めたデータベースの作成は、多くのグラフを機械的に体系付けることが出来る点において大きな意義をもつ。
　本研究で取り上げたMLCFGは、CFGを拡張したものとして、近年定義されたグラフの系列である。六角形を敷き詰めたグラフと同相であることから、グラファイト格子とも関連付けられると考えられる等の化学的な特徴だけでなく、特性多項式やマッチング多項式において漸化関係が見られる。また固有値が全て整数である整数グラフとなるものもあり、グラフ理論的にも興味深い特徴が挙げられ、現在研究がすすめられている。MLCFGには、沢山の種類があるが、その中でも代表的なEm,n,Fm,nは、mとnの組合せによって非常に多くのグラフがあり、互いに同相なものが複雑に絡み合っている。
　そこでわれわれはグラフの特性量を蓄積し公開するデータベースGCDB(Graphical Characteristics Data Base)を作成した。今回公開するGCDBでは、特にMLCFG：Em,n,Fm,nとそれに関連するグラフの間の関係を系統的に調べるために、327種類のグラフの特性量をデータベース化した。現在お茶の水女子大学において、試験公開を開始したので概要を報告する。(http://www.sap.is.ocha.ac.jp/~hayasi/cgi-bin/gcdb.cgi)


 Figure 1. Multi-layered Cyclic Fence Graphs: Em,n, Fm,n

2 Multi-layered Cyclic Fence Graph(MLCFG)

　MLCFG： ＊m,nは、2n個の頂点からなるcycle graph C2nを縦にm個並べてcycle graph の層をm個作り、その層の間をある規則で結ぶことによって得られる。（＊にはcycle graphの層の結び方によってE、Fなどのアルファベットが入る。）MLCFGとしてはいろいろな種類が考えられるが、本研究では、主にその中でも代表的なものである Em,n 、 Fm,n と Gm,n を取り扱う。Figure 1はその例である。
　MLCFGの特徴として、
  1. 　各頂点の次数が3、つまりcubicである。
  2. 　2部グラフである。
  3. 　どの辺も交わらせずにドーナツの表面を覆うことができるトーラスグラフである。
  4. 　対称性が非常に高い。
  5. 　特性多項式や距離多項式において漸化関係がみられる。
  6. 　固有値が全て整数の整数グラフとなるものもある。
  7. 　六角形を敷き詰めたグラフと同相であり、グラファイト格子と関連付けられる。
　などが挙げられ、現在研究がすすめられている。


 Figure 2. E2,3を得る手順。
太線は、グラフ構造を識別しやすくするために用いており、細線との違いはない。

●Em,n
　Em,n は、次のような手順で得られる。Figure 2において、 E2,3 を例に挙げて手順を紹介する。

  1. 　cycle graph C2n（図では C6を、Figure 2の様に縦にm個（図では2個）並べて層を作る。
  2. 　各層の下端の頂点と、その一つ下層の cycle graph の上端の頂点とを結ぶ。
  3. 　最下層の下端の頂点と、その右側に隣接する列の上端の頂点とを結ぶ。
  4. 　最上層の最左列の上端の頂点と最下層の最右列の下端の頂点とを結ぶ。


 Figure 3. F2,3を得る手順。
太線は、グラフ構造を識別しやすくするために用いており、細線との違いはない。


Figure 4. Gm,nの例

●Fm,n
　Fm,nの求め方は以下のとおりである。（Figure 3）Em,nを得る際の手順2において、各層の下端の頂点とその一つ下層の右側に隣接する列の上端の頂点とを結ぶ。次に、最左列の下端の頂点と最右列の上端の頂点とを結ぶ。他の手順は、Em,nと同様にして得られる。
●Gm,n
　Gm,nはFm,nの手順を更に一つ右側にずらしたもの、即ちで層のつなぎ方を2つずつずらして描いたグラフである。Figure 4にその例を示す。
　他にMLCFGとしては、Dm,n、Xm,n[3]が知られているが、ここではふれない。

3 グラフの特性量

　グラフの相関関係を系統的に解析する手段として、グラフの特性量[4]は非常に有効である。GCDBで取り上げた特性量はグラフの名前、頂点数、頂点の次数、辺の数、隣接行列、トポロジカルインデックス、ケクレ数、非隣接数、Z'、マッチング多項式、距離多項式、Sz、ウイーナー数、n歩数、固有値という16種類である。以下にGCDBで取り上げたグラフの特性量について簡単に説明する。また、ここでN はグラフの頂点数を表す。

隣接行列： A   グラフ Gに対して隣接行列は、次のような要素を持つ正方行列として定義される。

　例えば、Figure 1に示したE1,3の隣接行列は、

となる。

非隣接数： p(G,k)   グラフ Gに対して、非隣接数は、どの辺も互いに隣接しないようにk本の辺を選ぶ選び方の数と定義する。k=0,1,...,N/2であり、 p(G,0)=1 と定義される。
　例えば、E1,3の非隣接数は、

となる。

ケクレ数： K   ケクレ数は、グラフ G における N 個全ての頂点を、互いに隣接しない N/2 本の線で覆い尽くす方法の数を指す。非隣接数における p(G,N/2) と同値である。
　例えば、E1,3 のケクレ数は、 K=p(G,3)=6 となる。
トポロジカルインデックス： Z   非隣接数の総和をトポロジカルインデックスとする。定義は以下のとおりである。

特性多項式： PG(X)   グラフ G の特性多項式は、次のように定義される。これは、隣接行列Aの対角項に -X を代入した行列の行列式である。

Z'   Z'は、特性多項式の係数列 ak (k=0,...,N)を用いて次のように定義される。

距離多項式： SG(X)   グラフ G の距離多項式は距離行列 D ([D]ij = iからjまでの最短距離の辺の数 )を用いて、次のように定義される。

Sz   距離多項式の係数列 bk (k=0,...,N)を用いて、次のように定義される。

ウイーナー数： W   ウイーナー数は、距離行列 D の非対角要素の総和の半分であり、次のように定義される。

　（pk ： k 本の辺によって隔てられた頂点の対の数, d ： pk の最大値）
固有値： X   固有値は、特性多項式 PG(X) = 0 の一連の解を指す。

　以上がGCDBの蓄積されたグラフの特性量である。次節でGCDBの概要と使用例について説明する。

4 Graphical Characteristics Data Base (GCDB)の概要と使用例


 Figure 5. GCDBのシステム構成

4. 1 GCDBの構成

　GCDBのシステム構成をFigure 5に示す。GCDBは、WWWブラウザとそれからGCDB本体にデータを引き渡すCGIスクリプトとGCDB本体からなる。データは基本的にSOURCEファイルに蓄積されるが、GCDBのsetupコマンドによりインデックスファイル等高速検索のためのファイルが自動生成される。SOURCEファイルは、特性量計算プログラムが計算したグラフの特性量がある程度蓄積されると、そのデータを取り込みデータベースの再構築を行なう。現在この部分は人手を介せねばならず、自動化されていない。
　GCDBは、データベースの構造設計段階でのフィールド長の設定が不要で、表示の際にデータ長やデータの個数に合わせてフィールド長を自動的に調節する。表示は表形式ではなく、データとデータをカンマ','で区切って表示するため、無駄なスペースをとることを避けることができる。

4. 2 データ項目

　今回公開するGCDBの対象となるグラフは、MLCFGとそれに関連するグラフに限っている。ただし、GCDB自体の構造は、他のグラフの特性量に関するデータも管理することができる構造をとっている。GCDBは以下の１６項目のデータを管理している。

1.グラフの名前(NAME)        9.マッチング多項式(P(PR,CF))
2.頂点数(VTX)10.Z-dash(Z')
3.辺の数(EDG)11.ウイーナー数(W)
4.各頂点の次数(ODR)12.n歩数(pn)
5.隣接行列(A_MTRX)13.距離多項式(S(PR,CF))
6.非隣接数(k,p(G,k))14.Sz(Sz)
7.ケクレ数(K)15.固有値(X)
8.Topological Index(Z)16.コメント(CMNT)

カッコ内の表示はGCDBで実際に使われている項目名である。このうち、1〜5は各グラフを決定するものであり、6〜15は各グラフの特性量である。コメントは、各グラフに関しての特徴、同値なグラフなどの特記事項を挙げるための項目である。また、データのとれていない項目については、NULLを認める。

4. 3 検索コマンド

Table 1 GCDBの検索コマンド一覧
コマンドコマンドの内容
SEARCH・FIND条件を満たすデータの検索
DISPLAY検索データの表示
LIST使用可能なパラメータを調べる
LOOKあるフィールドの指定キーワード登録を調べ、インデックス表示
SETパラメータ値の設定
REMIND現在の検索履歴の表示
END・QUIT検索を終了
WHAT各コマンドの説明
HOW各コマンドの使用法の説明

GCDBで利用できる検索コマンドをTable 1に示す。検索コマンドの詳細はWHATまたはHOWを検索するか、後述するHow to keyword search等をクリックすることで得ることができる。

4. 4 SOURCEファイル



 Figure 6. SOURCEファイルの入力例

　SOURCEファイルでは、全てのグラフに関するデータを管理する。SOURCEファイルにおいて、データ以外に区切り記号として、カンマ（,）、スラッシュ（/）、バックスラッシュ（\）、＠、アスタリスク（*）を用いる。カンマは、同一フィールド内での各データを、スラッシュは一つのグラフにおける各フィールドを区切る役割をする。バックスラッシュは一つのグラフに関するデータ列の最後に入れる。＠は全てのデータ列の最後、つまりSOURCEファイルの最後に入れる。
　また、SOURCEファイルには、一行に半角80字で入力をする。グラフ名に関するデータは必ず行頭から入力する。それに続くデータは80字ずつ改行し、行頭には*を置く。Figure 6に実際の入力例（抜粋）を紹介する。
　このようにGCDBの基本的なデータはSOURCEファイルにテキスト形式で蓄積されているため、少量のデータ修正はエディタで行なうことができる。
　データの追加は、今回登録したデータ生成プログラムから自動的にSOURCEに追加することができる。
　大規模なグラフの特性量の計算には、莫大な計算時間を必要とするので、並列分散処理を有効に利用した特性量計算システムの開発が必要である。

4. 5 GCDBの検索例

　Figure 7にGCDBのフロントページ（検索待ち受け画面）と検索例を示した。
　Search key欄に F[2_3]などのKey wordを入力し、Searchボタンをクリックすると、HIT COUNTが表示される。充分検索件数を絞り込んだ後に、ALL DISPLAYボタンをクリックし、同様なkeyを入力してSearchボタンをクリックすると検索された情報全てが表示される。この時、名前（この例では、F[2_3])の所をクリックするとグラフが表示される。（Figure 8）
　GCDB自体の説明は、画面のSearch GCDB欄をクリックすると表示され、使用法等は画面のHow to keyword Search欄をクリックすることで得られる。画面をクリアするには、resetボタンをクリックすればよい。


 Figure 7. ヒットカウント表示


Figure 8. グラフの図形表示

5 まとめと今後の課題

　MLCFGのグラフの特性量を集めたデータベースGCDBを開発し試験的公開を開始した。グラフの特性量は、グラフが決まるとプログラムを用いて計算することができるが、その計算時間はグラフのサイズの増加に伴い組合せ的に増大する。そのためそれらをデータベースとして蓄積・公開することは意義が大きい。
　今後は、更に多様なグラフの特性量を登録していく必要がある。今回公開するGCDBでは、ヒット件数が０の場合は、そのまま０を報告するが、今後はそのような場合、自動的に特性量計算プログラムを起動して、結果を蓄積するといった自己増殖的なデータベースとして発展させていく必要がある。そのためにはグラフの特性量の自動生成法と計算された特性量の自動登録法の開発が必須である。
　また、グラフの同相関係探索ツールなどGCDBを用いた応用ツールの開発も行なっていく。

参考文献

[ 1] 細矢 治夫, 8^ラフ理論の化学物理への応用,固体物理, Vol.32, No.7, 659-556(1997), Vol.32,No.8, 629-639(1997), Vol.32, No.9, 721-728(1997), Vol.32, No.10, 801-810(1997), Vol.32, No.11, 884-893(1997), Vol.32, No.12, 965-973(1997), Vol.33, No.1, 10-18(1998), Vol.33, No.3, 181-189(1998), Vol.33, No.6, 523-531(1998), Vol.33, No.7, 603-607(1998), Vol.33, No.9, 757-764(1998), Vol.33, No.11,901-908(1998).
[ 2] H. Hosoya, and F. Harary, On the Matching Properties of Three Fence Graphs, J. Math. Chem., 12, 211-218 (1993).
[ 3] H. Hosoya, Y. Okuma, Y. Tsukano, and K. Nakada, Multi-layered Cyclic Fence Graphs: Novel Cubic Graphs Related to the Graphite Network, J. Chem. Inf. Comput. Sci., 35, 351-356 (1995).
[ 4] M. Omote, M. Wakamatsu, S. Hyugaji, U. Nagashima, and H. Hosoya, Tables of Topological Characteristics of Polyhedral Graphs with Eight Vertices, Natl. Sci. Rept. Ochanomizu Univ, 45 (1994).
[ 5] H. Hosoya, Topological Index. A Newly Proposed Quantity Characterizing the Topological Nature of Structural Isomers of Saturated Hydrocarbons, Bull. Chem. Soc. Japan, 44, 2332-2339 (1971).
Return