担当：Defolos
日付：2007-04-28
余因子展開：n次行列Aを行列式としたもの|A|を次のように定義する
ここで、Aのi行j列を取り除いたn-1の行列をA(¬i,¬j)で表すとすると、このとき次をAの成分a[i,j]に関する余因子という
余因子展開は、n次行列A＝[aij]について次式が成り立つ
2*2の行列の余因子展開は次のように簡単に求められる
点にラベルをつけた木を「ラベル付き木」とよぶ
ある木において、「ラベル付き木」とした場合の総数はいくつかが問題となる
これはCayley（ケイリー）の定理としてまとめられている
n点の異なるラベル付の木はnn-2個ある
証明のための準備として、次の２つを定義する
証明のポイント：「AからBを作る連鎖の総数」と「BからAを作る連鎖の総数」が等しいという条件から総数を求める
連鎖としてAからBを作る総数を求める
まずは図のようなグラフAを考える
下図のようにAを、点vに接続していない辺で分離する
この時点で点vの次数はk-1である。点vと点wを結ぶとdeg(v)=kのグラフBが得られる
Aの選び方はT(n,k-1)通りあり、切断する辺の選び方は次の通りある
点vに接続していない辺の選び方 = 木Aの辺の総数 - 点vの次数 = (n-1) - (k-1) = n-k通り
以上より連鎖A→Bの総数はT(n,k-1)(n-k)である
連鎖としてBからAを作る総数を求める
まずは図のようなグラフBを考える
このBのうちの点vを除去したときに得られる、木Bの成分である部分木を(T1,T2,T3...Tk)とする
各部分木に含まれる点の総数はniであり、次の式を満たす
n-1 = Σ[i=1;k] ni
次に点vに接続する辺をひとつ除去し、それによって孤立する部分木をTiとする
Ti以外の孤立しうる部分木をTjとおき、Ti内の任意の点uとTj内の任意の点wを辺で結ぶと、deg(v) = k-1のラベル付き木Aが得られる
ラベル付き木Bの選び方は、点vの次数がkであるため、T(n,k)通りである
また、点wiとTi以外の部分木Tjの任意の点を結ぶ方法は
(点vをのぞく点の総数) - (部分木Tiに属する点の総数) = (n-1) - ni通りである
以上より連鎖B→Aの総数は次の式で表される
T(n,k)Σ[i=1;k](n - 1 - ni) = T(n,k){(n - 1 - n1) + (n - 1 - n2) + ... + (n - 1 - nk)} = T(n,k){(n - 1)k - (n1 + n2 + ... + nk)} = T(n,k)(nk - k - n +1)
これを因数分解することでT(n,k)(n - 1)(k - 1)が得られる
連鎖A→Bと、連鎖B→Aの数は等しいため、次の関係式が得られる
(n - k)T(n,k-1) = (n - 1)(k - 1)T(n,k)
T(n,n-1) = 1であるため、(n - k)T(n,k-1) = (n - 1)(k - 1)T(n,k)をk=n-1, k=n-2, k=n-3...と書き出す
k=n-1の時：T(n,n-2) = (n-1)(n-2)T(n,n-1) = (n-1)(n-2)
k=n-2の時：2T(n,n-3) = (n-1)(n-3)T(n,n-2) = (n-1)^2(n-2)(n-3) つまり T(n,n-3) = 1/2(n-1)^2(n-2)(n-3)
k=n-3の時：3T(n,n-4) = (n-1)(n-4)T(n,n-3) = 1/2(n-1)^3(n-2)(n-3)(n-4) つまり T(n,n-4) = 1/(1*2*3) (n-1)^3(n-2)(n-3)(n-4)
二項定理よりk=k+1のとき次式のように表すことができる
T(n,k) = (n-1)^n-k+1(n-2) / (k-1)(k-2)... = n-2Ck-1(n-1)^n-k-1
従って、T(n)はT(n,k)に関するk=1からk=n-1までの総和である
Σ[k=1;n-1] T(n,k) = Σ[k=1;n-1] n-2Ck-1(n-1)^n-k-1 = Σ[k=1;n-1] n-2Ck-11^k-1(n-1)^(n-2)-(k-1) = {(n-1)+1}^n-2 = n^n-2
以上よりCayleyの定理が証明された
n点のラベル付き木の個数をT(n)とする。このとき以下の問いに答えよ
2(n-1)T(n)はn点からなる木の辺の一辺だけを切って2つのグラフA,Bを作る組み合わせの総数に等しい
A,Bの木を作る方法は次のように表される
まず、任意の一辺を切断する
それで得られる部分木をそれぞれA,Bとする
次にAとBとを結ぶ方法を考える
Aにおける任意の点とBにおける任意の点を選び出し、それらを結ぶ
T(n)はn点からなる木の総数であり、(n-1)はどの辺を切るかという自由度である
nではなくn-1なのは、辺の数はn点のグラフの場合n-1しか存在しないからである
2はAとBを交換することによる自由度である
k点のラベル付き木Aと(n-k)点のラベル付き木Bの結び方の総数は、次の式で表される
これはつまり、Σ[k=1;n-1] nCkk(n-k)T(k)T(n-k)と等しい
故に2(n-1)T(n) = Σ[k=1;n-1] nCkk(n-k)T(k)T(n-k)である
Cayleyの定理で得られたT(n) = n^(n-2)を、Σ[k=1;n-1] nCkkk-1(n-k)n-k-1 = 2(n-1)nn-2に代入する次の式が得られる
2(n-1)nn-2 = Σ[k=1;n-1] nCk k(n-k)kk-2(n-k)n-k-2 = Σ[k=1;n-1] nCk k・kk-2・(n-k)(n-k)n-k-2 = Σ[k=1;n-1] nCk kn-1(n-k)n-k-1
完全グラフの全域木の総数はnn-2個である
完全グラフKnから、各点に接続している辺を適切に除去すると、n点のラベル付き全域木が得られる
逆に、n点のラベル付き木の各点に、すべての点の次数がn-1になるように適切に辺を追加するとKnが得られる
故に、点数nのラベル付き木は完全グラフKnに一対一に対応するため、Cayleyの定理の対象となるラベル付き木と同一であると言える
以上より、Cayleyの定理で得られたnn-2が完全グラフの全域木の総数である
行列木定理(matrix-tree hteorem)：与えられたグラフGのラベル付全域木の個数を与える定理
行列木定理を解説するために、まず点行列を定義する
点行列(vertex matrix)：グラフGの点行列をDと表し、次のように定義する
iとjが等しい時は点viの次数をij要素に入れ、iとjが等しくない場合は-(点viと点vjを結ぶ辺の数)をij要素に入れる
そのため、Dij = Dji である
次のラベル付木の点行列を考える
ここでは1,2,3,4,5をそれぞれA,B,C,D,Eとする
点の数が5であるため、点行列は5*5の行列であるとわかる
まず、i=jの場合を考え、各点の次数を対角成分に格納する
次にD12要素を考える
12要素は-(点1と点2の間の辺の数)を入れるため、AとBの間の辺の数を数える
AB間には辺が存在しないため0を入れる
一方、AC間には1つの辺が存在するため、D13には-1を入れる
同様にしてすべての要素を埋める
グラフGの全域木の本数τ(G)は点行列Dの任意の余因子で与えられる
点行列Dのi行j列を削除して得られる行列をD( i, j)とする
グラフGの全域木の総数は次の式によって与えられる
隣接行列Aが
で与えられるグラフGの全域木の総数τ(G)を求めよ。また、その全域木をすべて図示せよ。
隣接行列は点iと点jを結ぶ辺の本数を第ij要素とするn*nの行列(第2回より)であるため、グラフGは次のようなグラフ
ここから点行列Dを求める
N*N行列の場合i=j=Nと選んで余因子を計算すると、符号は常に+となるため扱いやすい
余因子から行列式を解くと3になるため、グラフGの全域木は3つあることがわかる
グラフGの全域木は次の3つである
今回学んだCayleyの定理の証明を参考にし、次の問いに答えよ
隣接行列Aが次のような行列で与えられるグラフGに関する行列木定理について、次の問いに答えよ
n点からなる木の点vの次数がkであるものの個数はCayleyの定理で得られた次の式で表される
T(n,1) = n-2Ck-1(n-1)n-k-1
問題の与えられた点vが端点になっているものは、kが1の場合である
もしkが1以外だと次の図のように端点ではない
故に求める木の個数は次のように表される
T(n,k) = n-2C0(n-1)n-2 = (n-1)n-2
確率はその事象の数 / 全ての事象の数で表される
サイコロで偶数がでる確率は、サイコロは6面であるため分母に6を入れ、偶数は2,4,6の3つなので分子に3を入れる。よって3/6である
同じように考え、n点からなる木の総数であるnn-2を分母に入れ、例題7.5-1 解答その1で得られた点vの次数k=1である場合の個数を分子に入れると次のようになる
P(n) = T(n,1) / nn-2 = (1 - (1/n))n-2
自然対数eの定理より次の式が得られ、題意が示される
lim[n→∞]P(n) = lim[n→∞](1-(1/n))^n-2 = lim[n→∞](1-(1/n))^n = 1/e
n-2乗とはn乗したものから2乗したものを割ったものであるため、a^(b-c) = (a^b)/(a^c)と表現できる
つまり、(1-(1/n))^(n-2)は(1-(1/n))^n / (1-(1/n))^2と表される
そこからlim[n→∞](1-(1/n))^(n-2) = lim[n→∞](1-(1/n))^n × lim[n→∞](1-(1/n))^(-2)
1/nにおいて、nを無限に近づけると1/無限つまり0として扱えるため、lim[n→∞](1-(1/n))^(-2)＝(1-0)^(-2)=1^(-2)=1が言える
ゆえにlim[n→∞](1-(1/n))^(n-2) = lim[n→∞](1-(1/n))^n×1＝lim[n→∞](1-(1/n))^nと書け、lim[n→∞](1-(1/n))^nは1/eである
与えられた隣接行列AからグラフGを図示すると次のようになる
ここから点行列Dを求める
点行列Dのi=j=4の余因子で表される行列が求める解である
次に第3行で行列式を展開する
以上よりグラフGの全域木の個数τ(G)は7であることがわかる
グラフGの全域木は7個あるが、これらを図示する際の注意点として次のようなものがある
点3と点4をつなぐ辺は2つあり、これらを別々のものとして扱う。つまり、グラフGの辺を色分けして考えると次のようになる
グラフGの全域木7個を図示すると次のようになる
隣接行列と点行列の間には行列δを介した関係が存在する
行列δを次のように定義する
隣接行列Aと点行列Dの間には次のような関係が存在する
D = δ - A
例として例題7.4のグラフGにおいてこの式が成り立つことを確認する
行列δは次のようになる
上の式にδとAをあてはめ、点行列Dを導く
行列δを介して求めた点行列Dと例題7.4で求めた点行列Dが一致することが確認できた
閉路行列Rは次のように定義される
このとき、非対角成分の符号はciとcjの共通な辺上で、2つの閉路の向きが同じであれば正を、逆であれば負を選ぶこととする
ラベル付全域木の個数を数え上げる方式には点行列法と閉路行列法が存在する
これまでのように点行列をもとに全域木を数える方式を点行列法と呼び、上記の閉路行列をもとに全域木を数える方式を閉路行列法と呼ぶ
閉路行列Rを有するグラフGに関する全域木の総数γ(G)は次の式で表される。
γ(G) = |R|
次の隣接行列で与えられるグラフGについて考える
グラフGには2つの閉路c1,c2が存在する
点の順序で向きを指定するとc1=12431、c2=343である
従ってグラフGの閉路行列Rは次のようになる
よってグラフGの全域木の総数τ(G)は次のようになり、点行列法による結果と一致する
行列木定理を用いてCayleyの定理を証明せよ
m*mの対称行列の行列式をbmと定義すると、次のような関係式が成り立つ
bm = (a+1)m-1b1 + (m-1)(a+1)m-1c1
完全グラフの点行列はn*nの対角成分がn-1、それ以外の成分が-1となる行列である
そのため、m=n-1, a=n-1, b1=a, c1=-1を代入する
すなわち、bn-1 = nn-2(n-1) -n(n-2)n-2であり、つまりbn-1 = nn-2である
完全グラフの全域木とn点からなるラベル付木の総数は1対1に対応するため、Cayleyの定理が証明された