数理科学コース・ 倉田 和浩 2007/11/3 大学祭オープンラボ グラフ上の散歩パターンの数理 数理科学コース・ 倉田 和浩 2007/11/3 大学祭オープンラボ
グラフとは？ グラフとは、頂点(v1,v2,..,vn)と辺(e1,e2,..em)の集まり. （例：n=6, m=5; 6個の頂点と５個の辺） v3 v2 e2 e1 e3 e5 v1 v6 v4 e4 v5
グラフGとその隣接行列AG AG= グラフGには, 隣接行列AGが１対１に対応する！ 1 第２列 （１，２）成分といいa[1,2 ]と書く v2 1 v1 第１行 AG= v3 頂点viと頂点v jを結ぶ辺があればa[i, j ]=1、なければa [i,j] =0とする.
行列の掛け算 Ａ＝（ａ[i,j]）とB=(b [i,j] )の掛け算: C=(c [i,j])=ABとするとき, c[i,j]=a[i,1]b[1,j]+a[i,2]b[2,j]+..+a[i,n]b[n,j] 第１行 第１列 a[1,1] a[1,2] a[1,3] a[2,1] a[2,2] a[2,3] a[3,1] a[3,2] a[3,3] b[1,1] b[1,2] b[1,3] b[2,1] b[2,2] b[2,3] b[3,1] b[3,2] b[3,3] 例： （１，１）成分の計算 c[1,1]= a[1,1]b[1,1]+a[1,2]b[2,1]+a[1,3]b[3,1]
グラフ上の散歩パターンはいく通り？ 頂点v1から出発してまたv1に戻る長さ4の散歩パターンはいく通り？長さ10の散歩パターンはいく通りあるか？長さ１００だと？？ v2 v4 v1 v3
長さＬの散歩パターンの数を行列の言葉での表現する！ グラフＧに対応する隣接行列をAGとし, AGのL個の積を(AG)L=(a L[i,j])で表す. 命題： 頂点viを出発し頂点vjに到達するような散歩パターンのうち長さＬのものの総数はちょうどa L[i,j] 個である. ◆行列の積を計算するだけで, 自動的に長さＬの散歩パターンの総数がわかる！
長さＬの散歩パターンの総数の漸近的ふるまい 一般に, a L [I,j]はLが十分大きいとき, ある定数c＞０とｄ＞０があって,およそ次のような増大パターンをもつ: a L [i,j] ～ ｃ ｄＬ ◆散歩パターンの多い・少ないは, ほぼ定数dによって決定される！ 極限で見えてくるパターン！！
グラフＧと定数dの関係は？ 実は, dはグラフGに対して, その隣接行列AGの最大固有値である！ 問題： どんなグラフが散歩パターンが多いのか？ 例えば, 下のG1,G2のように, 頂点の数と辺の数を指定したら, どのグラフがもっとも散歩パターンが多いといえるか？ Ｇ１ Ｇ２
行列の固有値とは？ A x1 x1 x2 x2 x3 x3 x4 x4 = a 行列Ａに対して(例えば,n=4として） x1 x2 x3 x4 x1 x2 x3 x4 A = a となるような定数 a と （ゼロベクトルでない）ベクトル が存在するとき,aを行列Aの固有値といい, そのベクトルを固有ベクトルという.
ペロン・フロベニウスの定理 グラフに対応する隣接行列AGには, 必ず正の固有値dで最大のものが存在する. またその固有ベクトルの成分はすべて正となる.
最適化問題？ グラフを道路網と考えて,さらに１本の道路を増設する計画を立てるとしよう. さて, どの道を増設するのがもっともよいか？ 散歩パターンを迂回路パターンに置き換えて,どの道を増設した道路網がもっとも迂回路パターンが多いか？という問題ととらえる. (現実には,無駄な迂回路はとらないであろうが。。。）
どっちを増設するほうがよいか？
他の応用例 昼食メニュー（中華・和食・イタリアン）の好みのパターンから通常だいたいどのメニューを選ぶかの比率を当てる！ Googleのページランク(InternetのＨＰのランク付け）