グラフ理論 配布資料 #7 (教科書 pp. 66 〜 82 の内容)
担当 : 井上 純一 (情報科学研究科棟 8-13)
平成 17 年 6 月 6 日

目次
7.4

木の数え上げ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70

7.5

点行列と行列木定理. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75

演習問題 6 の解答例
(1) 図 98 のように問題のグラフの各辺に番号をふると, 辺集合 I : {1, 2, 3}, 辺集合 II : {4, 5, 6} のそれぞれから, 要素を 1 つずつ取り出し, その辺を削除すれば全域木が得られる. 従って, 考えうる全域木のab26153e4cd図 98: 問題のグラフの各辺に番号をふる.
数は 3 × 3 = 9 通りである. ぞれぞれの全域木と削除する辺の組み合わせは A : (1,4), B : (1,5), C :(1,6), D : (2,4), E : (2,5), F : (2,6), G : (3,4), H : (3,5), I : (3,6) であり, それぞれを描くと図 99 のようになる.
(2) 例として図 100(左) のようなグラフを考える. このとき, 辺 e はカットセットになっており (この場合は「橋」とも言える), この辺を削除すると, 連結グラフは点と三角形に分離する. そこで, このグラフの全域木を作るためには, 三角形の各辺を 1 辺だけ削除すればよいので, 可能な全域木は図 100(右) のようになり, 辺 e は全ての全域木に共通に含まれることになる. 従って, このグラフに関しては題意が満たされていることになる.

レポート問題 #5 に関するコメント
小問 2. で, 問題に与えれたグラフがハミルトン・グラフでないことを証明する部分で, 小問 1. の結果, つまり, 「二部グラフで点数が奇数のグラフにはハミルトン閉路が存在しない」ということを用いて, 問題の68

グラフ理論 2005

担当 : 大学院情報科学研究科 井上 純一

ABCDEFGHI

図 99: 可能な全域木.

aeecbee

図 100: ここで考える連結グラフ G(左) とその全域木 (右).
グラフが図 101 のように二部グラフで描くことができ, かつ, このグラフの点数は 11 で奇数であることから「ハミルトン・グラフではない」と結論付けてもよいです. また, 数名の学生さんは, 実際にハミルトン

図 101: ここでハミルトン性を考えていたグラフの二部グラフ表現.
閉路を見つけ出すアルゴリズムを作り, それをプログラミングして計算機に解かせることによりハミルトン・グラフでないことを示していましたが, もちろん OK です. グラフのサイズが大きくなる場合では, こうした「計算機で証明させる」というアプローチがかなり有効になってきます.

Ore の定理はハミルトン・グラフであるための十分条件であるため, Ore の定理を満たしていれば, つまり, 完全グラフのように十分な辺数があれば, ハミルトン閉路があることが示せますが, Ore の定理を満たさない場合, 一般的に言ってハミルトン・グラフか否かを証明することはとても難しくなります. この手のここは 69 ページ目

グラフ理論 2005

担当 : 大学院情報科学研究科 井上 純一「判定問題」では重宝になる必要条件もいくつかあるようですが, それは十分条件と比べて数が少なく, 実用的なものもさほど無さそうです. 必要十分条件についてはまだ何も見つかっていません.
従って, ハミルトン・グラフか否かの証明はグラフの特性に応じてケース・バイ・ケースで取り組まなければならないのですが, おおまかに言えば, まずあたってみる価値のある方法は 2 つあり, 一つは前回の演習問題で紹介した「グラフを二部グラフで表し, その点数が奇数であることで非ハミルトン性を示す」やり方 (方法 1). もう一つは辺数に関して背理法で矛盾を導くという方法 (方法 2) です.
ここでは, この方法 2 を説明しておきましょう. まず, 例として図 102 のような点数 11, 辺数 15 のグラフに対し, 「ハミルトン閉路 C が存在する」と仮定します. その閉路 C 上では各点には必ず 2 本の辺が接続
a1511011b529e1214138c7364d図 102: 背理法を用いて非ハミルトングラフであることを示すのに例として用いるグラフ.
していなければならないことに注目すると, 互いに隣接していない a, b, c, d, 及び, e の 5 点のそれぞれの次数は 3, 3, 4, 3, 3 であるので, C 上に無い辺数は少なくとも (3 − 2) + (3 − 2) + (4 − 2) + (3 − 2) + (3 − 2) = 5(本) であり, 従って, 閉路 C には高々15 − 5 = 10 (本) しか辺が無いことがわかります. しかし, 点数 11 でハミルトン閉路を作る場合にはその閉路の辺数は 11 となりますから, 辺数 10 ではこれは不可能ということになり, 我々が用いた「ハミルトン閉路が存在する」という仮定に矛盾が生じたので図 102 のグラフにはハミルトン閉路が無い, と結論付けることができます.
ちなみに, ピータースン・グラフの場合には二部グラフで描けないので方法 1 ではダメ. また, 辺数が割りと多いので, ここで説明した方法 2 でのアプローチもうまくいきません. ですから「ピータースン・グラフがハミルトングラフではない」ことを示すのは「非常に難しい」ことになるのですが, 情報工学演習

II(B) (グラフ理論) の 問題 3 がこれを問うているので, 1ヶ月くらい時間をかけて考えてみてください (ちなみに, 問題 1 〜 問題 6 の中ではこの問題が最も難しいと思います).

7.4

木の数え上げ点にラベルを付けた木を「ラベル付き木」と言うが, このように各点にラベルを付けて木を区別した場
合, その総数はいくつあるか, ということが問題になる. その答えは Cayley (ケイリー) の定理としてまとめられており, 「n 個の点からなるラベル付き木の総数は nn−2 個である」というように, とても簡単な形で表される. ここではこの定理 (公式) の証明を詳しく追い, 関連する系, 及び, いくつかの例題をとりあげ,その理解を深めて行くことにしよう.

ここは 70 ページ目

グラフ理論 2005

担当 : 大学院情報科学研究科 井上 純一

定理 10.1 (Cayley の定理)

n 点の異なるラベル付の木は nn−2 個ある.

この定理の構成論的な証明 (第 1 の証明) は教科書 pp. 67-68 を見て頂くことにして, ここでは第 2 の証明を詳しく追って行くことにする.

(証明)
まずは準備として• deg(v) = k − 1 の点 v を含むラベル付きの木を A• deg(v) = k の点 v を含むラベル付きのの木を Bと定義しておく.
ここで述べる証明のポイントは「『ラベル付き木 A からラベル付き木 B を作る連鎖 (linkage) の総数』と『逆にラベル付き木 B からラベル付き木 A を作る連鎖の総数』が等しい」という条件 (関係式) から可能なラベル付き木の総数を求める, という点である.
それでは以下で連鎖 : A → B, 及び, 連鎖 : B → A なる操作をそれぞれ見て行くことにしょう. この際, n個の点からなるラベル付き木のある点 v の次数が k であるものの総数を T (n, k) で表しておくことにする.
連鎖 : A → B
図 103 のように A を点 v に接続していない辺で分離し (図 103 の (a) → (b)), 点 v と点 z とを結ぶと (図 103の (b) → (c)), deg(v) = k であるラベル付き木 B が得られる. さて, ラベル付き木 A の選び方は T (n, k − 1)(a)(b)zzvv
cut(c)vz

図 103: 連鎖 : A → B.
通りあり, 1 つの A に対して, 切断する辺の選び方は(点 v に接続していない辺の選び方)= (木 A の辺の本数) − (点 v の次数)
= (n − 1) − (k − 1) = n − k (通り)だけあるから, 連鎖 : A → B の総数は(連鎖 : A → B の総数) = T (n, k − 1)(n − k)となる. 次に連鎖 : B → A を考える.

ここは 71 ページ目

グラフ理論 2005

担当 : 大学院情報科学研究科 井上 純一

連鎖 : B → A
図 104 のように, ラベル付き木 B から点 v, 及び, その接続辺を除去して得られる, 木 B の成分である一連の部分木を (T1 , T2 , · · · , Tk ) とする (図 104 の (a)). ここで各部分木に含まれる点の総数は ni であり, 当然のことながらn − 1 (v 以外の点の数) =k

nii=1を満たしている. このとき, ラベル付き木 B から点 v, 及び, その接続辺の 1 本を除去し (この際にできる成(a)(b)
w1,T1

w1,T1

cutv

v

w2,T2

w2,T2
w3,T3

w3,T3

w1,T1(c)v
w2,T2
w3,T3

図 104: 連鎖 : B → A.
分である部分木を Ti と名付ける)(図 104 の (a) → (b)), Ti 以外の部分木 Tj の任意の点 u と部分木 Ti 内の任意の点 wi を辺で結ぶ (図 104 の (b) → (c)) と deg(v) = k − 1 のラベル付き木 A が得られる.
ここでラベル付き木 B の選び方は T (n, k) 通りであり, 点 wi と Ti 以外の部分木 Tj の任意の点を結ぶ方
法は(点 v を除く点の総数) − (部分木 Ti に属する点の総数)= (n − 1) − ni (通り)だけあるから, 連鎖 : B → A の総数は

T (n, k)k(n − 1 − ni ) =T (n, k){(n − 1 − n1 ) + (n − 1 − n2 ) + · · · + (n − 1 − nk )}

i=1=T (n, k){(n − 1)k − (n1 + n2 + · · · + nk )}=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 に注意して, 上関係式で k = n − 1, n − 2, n − 3, · · · と書き出して行ってみるとここは 72 ページ目

グラフ理論 2005

担当 : 大学院情報科学研究科 井上 純一

k = n − 1 のとき
T (n, n − 2)

= (n − 1)(n − 2)T (n, n − 1) = (n − 1)(n − 2)k = n − 2 のとき(n − 1)(n − 3)T (n, n − 2) = (n − 1)2 (n − 2)(n − 3)

2T (n, n − 3) =つまりT (n, n − 3)=1(n − 1)2 (n − 2)(n − 3)2

k = n − 3 のとき
3T (n, n − 4)

= (n − 1)(n − 4)T (n, n − 3)1(n − 1)3 (n − 2)(n − 3)(n − 4)=2

つまりT (n, n − 4)=1(n − 1)3 (n − 2)(n − 3)(n − 4)
3·2·1が得られる. これを一般化すると, 二項定理より k = k + 1 のとき

T (n, k) ==(n − 1)n−k+1 (n − 2)(k − 1)(k − 2) · · ·n−2 Ck−1 (n − 1)

n−k−1という結果が得られる. 従って, 求めるラベル付き木の総数 T (n) は上記の T (n, k) に関し, k = 1 からk = n − 1 まで和をとることによりT (n) ==n−1

k=1
n−1


T (n, k)n−2 Ck−1 (n − 1)

n−k−1

k=1

=n−1


n−2 Ck−1 1

k−1(n − 1)(n−2)−(k−1)

k=1= {(n − 1) + 1}n−2 = nn−2となり, Cayley の定理が証明された. (証明終わり).
この定理に関する例題を一つ見ておく.

ここは 73 ページ目

グラフ理論 2005担当 : 大学院情報科学研究科 井上 純一

✬✩

例題 15
n 点のラベル付き木の個数を T (n) とする. このとき以下の問いに答えよ.

(1) k 点のラベル付き木と n − k 点のラベル付き木の結び方の総数を計算することにより, 次の関係式を示せ.
2(n − 1)T (n) =n−1
n Ck k(n − k)T (k)T (n − k)k=1(2) 次の関係式を示せ.
n−1
n Ck kk−1(n − k)n−k−1 = 2(n − 1)nn−2k=1

✫✪

(答え)
(1) n 点からなる木の辺を一辺だけ切って, 2 つのグラフ A, B を作る方法は
2 × (n − 1) × T (n) =2(n − 1)T (n)(41)

通り存在する. ここで, T (n) は n 点からなる木の総数であり, 係数 (n − 1) はどの辺を切るかという自由度を, また, 係数 2 はグラフ A, B の交換による自由度を表している.
ところで, k 点のラベル付き木 A と (n − k) 点のラベル付き木 B の結び方の総数は, k 点のラベル付き木の中から一点を選ぶ方法の kT (k) 通りと n − k 点のラベル付き木の中から一点を選ぶ方法の(n − k)T (n − k) 通りを掛け合わせ, これに n 個の点から k (k = 1, 2, · · · , n − 1) 個の点を選んで A, Bを作る場合の数を掛け合わせただけの個数だけ存在するからn−1

n Ck kT (k)(n − k)T (n − k)=k=1n−1n Ck k(n − k)T (k)T (n − k)(42)k=1となる. (41)(42) は等しいので2(n − 1)T (n) =n−1
n Ck k(n − k)T (k)T (n − k)(43)k=1が得られる.

(2) (43) 式において, Cayley の定理 : T (n) = nn−2 等を用いると
2(n − 1)nn−2

==n−1

k=1
n−1


n Ck k(n − k)kn Ck k

k−1k−2(n − k)n−k−2(n − k)n−k−1(44)k=1が得られる.

ここは 74 ページ目

グラフ理論 2005

担当 : 大学院情報科学研究科 井上 純一

この節の最後に Cayley の定理から導かれる系を一つあげておこう.
系 10.2完全グラフ Kn の全域木の総数は nn−2 個である.

(証明)
完全グラフ Kn から, 各点に接続している辺を適切に除去することにより, n 点のラベル付き木 (全域木) が得られ, 逆に, n 点のラベル付き木の各点に, 各点の次数が n − 1 になるよう, 適切に辺を加えることにより完全グラフ Kn が得られる (例えば, 図 105 に K5 の場合を載せた). 従って, n 点のラベル付き木は完全グ
ラフ Kn の全域木に一意に対応し, よって, 完全グラフ Kn の全域木の総数は nn−2 である. (証明終わり).

K5

図 105: 完全グラフ K5 とその全域木.

7.5

点行列と行列木定理

ここで学ぶ 行列木定理 (matrix-tree theorem) は, 与えられたグラフ G のラベル付き全域木の個数を与える実用的な定理である.
具体的に定理とその応用例を見る前に, グラフ G の点行列 (vertex matrix) D を次のように定義する
1.

グラフ G の点行列 D とは, その要素 Dij が
Dij=点 vi の次数(i = j のとき)−(点 vi と点 vj を結ぶ辺の本数) (i = j のとき)で与えられる行列である.
このとき, グラフ G の全域木の本数 τ (G) は行列 D の任意の余因子で与えられる. つまり, 行列 D の第i 行, 第 j 列を削除して得られる行列を D(i, j) とすると
τ (G)= (−1)i+j |D(i, j)|が全域木の本数を与える. ここで, |X| は行列 X の行列式を意味する.
1 この講義では個々のグラフのデータ構造を表現するための行列を既にいくつか取りあげてきたが, この点行列は 5 番目の行列である. 各自, これまでに学んだ「隣接行列」「接続行列」「タイセット行列」「カットセット行列」を復習しておくこと.

ここは 75 ページ目

グラフ理論 2005

担当 : 大学院情報科学研究科 井上 純一

なお, 実用的には行列 D のサイズが N × N ならば, i = j = N と選ぶのが扱いやすく, このとき

τ (G)= |D(N , N )|が全域木の総数となる. 以上の内容を行列木定理と呼ぶ.
この定理の使い方を具体的に見るために, 次のような例題を考えてみよう.

✬✩

例題 16
隣接行列 A が
11 0 1
A =  1 01 10で与えられるグラフ G の全域木の総数 τ (G) を求めよ. また, その全域木を全て図示せよ.
✫✪(答え)
隣接行列 A を持つグラフ G を図示してみると図 106 となる. このグラフ G の点行列 D は, その定義から
123

図 106: 隣接行列 A で与えられるグラフ G.

D=

2−1 −1 −1 2 −1 −1 −1 2であり, その i = j = 3 での余因子が, このグラフ G の全域木の総数 τ (G) を与えτ (G)=2 −1−1 2= 4 − 1 = 3 (個)となる. この 3 つの全域木を描くと図 107 のようになる.

ここは 76 ページ目

グラフ理論 2005

担当 : 大学院情報科学研究科 井上 純一

121321323

図 107: 隣接行列 A で与えられるグラフ G の 3 つの全域木.

✬✩

例題 17

1. 今回の講義で学んだ Cayley の定理の証明を参考にして, 下記の問いに答えよ.
(1) n 個の点からなる木で, 与えられた点 v が端点になっているものは何個あるか ?
(2) n 個の点からなる木の与えられた点 v が端点となっている確率 P (n) を求めよ. また, 点の数 n が無限大のときの P (n) の極限値がlim P (n) =n→∞1eで与えられることを示せ. ただし, e は自然対数の底である.

2. 隣接行列 A がA =0
 1 1
01 10 00 01 201 2 0で与えられるグラフ G に関する行列木定理について以下の問いに答えよ.
(1) グラフ G の点行列 D を求めよ.

(2) 行列木定理により, グラフ G の全域木の総数 τ (G) を求めよ.
(3) (2) で得られた個数だけ存在する全域木を具体的に全て図示せよ.
✫✪

(解答例)
1.(1) 今回の講義で学習した Cayley の定理の証明の過程で得られた関係式 :T (n, k) =n−2 Ck−1 (n − 1)

n−k−1(45)に注目する. これは, n 点からなる木における, ある点 v の次数が k であるものの個数を与えるわけであるから, 問題となっている「与えられた点 v が端点である木の個数」は上関係式で k = 1 と置いたものに等しい. 従って, 求める木の個数はT (n, 1) =n−2 C0 (n − 1)n−2= (n − 1)n−2(46)である.

ここは 77 ページ目

グラフ理論 2005

担当 : 大学院情報科学研究科 井上 純一(2) 求める確率 P (n) は n 個の点からなるラベル付き木の個数 nn−2 で上の結果である T (n, 1) を割ったものに相当するので

P (n) =T (n, 1)=nn−21−n−21n(47)が求める答えである.

(3) 自然対数 e の定義から
lim P (n) =n→∞

n−2

lim

1−1nlim1−1nn→∞= limn→∞1−1nn=1e(48)となり, 題意が示された.

(参考)
P (n) の極限値 :n→∞n1e=(49)の示し方として, 例えば P (n) の対数をとったものの極限値 :lim log 1 −n→∞1nn= lim n log 1 −n→∞1n(50)を考えることによって「間接的」に (49) を示すこともできます. (50) の極限値はこのままでは

lim n = ∞,n→∞

lim log 1 −n→∞1n=0(51)なので, ∞ × 0 を評価することになって厄介なのですが, log(1 − 1/n) を (1/n) で展開すれば

log 1 −

1n=−11−+On 2n21n3(52)1+O2n1n2(53)となりますから,n log 1 −1n= −1 −であり, 極限値 (50) は簡単に

lim log 1 −n→∞1nn= −1(54)のように求めることができます. 従って, n → ∞ のときに上式の log の中身が 1/e に近づくべきことは明らかであり, これで極限値 (49) が示せたことになります.

2. 隣接行列 A により与えられるグラフ G は図 108 のようになる. 従って, 求める点行列 D は
2 −1 −1 0 −1 20 −1 
D = 3 −2 
 −1 0
0 −1 −2 3(55)

ここは 78 ページ目

グラフ理論 2005

担当 : 大学院情報科学研究科 井上 純一

G1324

図 108: 隣接行列 A によって定義されるグラフ G.
である.

i = j = 4 で余因子展開することにより, グラフ G の全域木の個数 τ (G) はτ (G)4+42−1 −1−1−12003+32 −1−1 2=(−1)=(−1)=−2 + 3 · 3 = 7 (個)−1 −120(56)となる.

(3) グラフ G の 7 通りの全域木を図示すると図 109 になる.
(2)
1313131324242424A

図 109: 隣接行列 によって定義されるグラフ G の全域木. ただし, 辺 3 → 4 を削除するか, 辺 4 → 3 を削除するかにより, これ
ら 4 つのグラフの中で辺 34 があるグラフにはそれぞれ 1 つずつ異なるグラフが存在するので, 計 7 つの全域木が得られる.

(注 1)
隣接行列 A と点行列 D の間には, 次に定義する行列 δ を介して一般的な関係が存在する.
行列 δ はその要素 δij がδij=deg(vi ) (i = j のとき)
0(i = j のとき)

(57)で定義される行列であり, この行列と, 隣接行列 A, 点行列 D の間には

D=δ−A(58)なる関係がある. 各自がこの演習問題で扱ったグラフ G において, この関係式が成り立っていることを確認しておくこと.

(注 2)
ここは 79 ページ目

グラフ理論 2005

担当 : 大学院情報科学研究科 井上 純一

ここで取り上げた点行列の行列式を計算することにより, ラベル付き全域木の数を数え上げる方法
を点行列式法と名付けるとすれば, この全域木の個数を勘定する方法としては, もう一つ, 閉路行列式法と呼ばれる方法がある. ここでは, この方法に関していくつかコメントしておこう.
まず, 行列要素 Rij が次のように与えられる閉路行列 R を導入する2 .

閉路 ci を構成する辺の数(i = j)Rij =± (閉路 ci と cj に共通な辺の本数) (i = j)(59)

ここで非対角成分の符号は ci と cj の共通な辺上で, これら 2 つの閉路の向きが同じであればプラスを, 逆であればマイナスを選ぶことに約束する.
すると, この閉路行列 R を有するグラフ G に関する全域木の総数 τ (G) はτ (G)|R|=(60)

つまり, 行列 R の行列式で与えられる. この方法の有効性を確認するために, 前回の演習問題 2. の隣接行列で与えられたグラフ (本配布資料図 108 のグラフ G) に対して, この方法を適用してみよう.
まず, このグラフ G には閉路 c1 , c2 が存在し, それぞれは点の順序でその向きを指定すれば, c1 =12431, c2 = 343 となる. 従って, このグラフ G の閉路行列 R はR

4 1=(61)

1 2である. よって, このグラフ G に対する全域木の総数 τ (G) はτ (G)41=12=7(62)となり, 点行列式法による結果, つまり, 前回の演習問題 2.(2) の答えと一致する.
ところで, あるグラフ G が与えられたとき, その全域木の総数を勘定する必要が生じた際, 上述の点行列式法と閉路行列式法のどちらを使ったらよいのであろうか ? この疑問に対する一般的な答えは
グラフ G に含まれる点の数が閉路の数よりも少ない場合には点行列式法を用い, その逆の場合には閉路行列式法を用いるのがよいということである.
上記指針の正しさを確認するため, 閉路行列式法の点行列法に対する「優位性」が際立ってわかるような例を取りあげ, そのグラフに両方法を適用してみることにしょう.
図 110 に示したグラフ G に対して, まずは閉路行列式を適用してみると, この平面グラフの閉路はいずれも三角形であり, c1 = 1451, c2 = 3453, c3 = 1231 である. 従って, このグラフの閉路行列 R は12Gc3c15c234

図 110: ここで点行列式法と閉路行列式法との計算手数を比較するために用いるグラフ G.

R3 1=  1 30 000 (63)32 この講義に出てきたものとしては 6 番目のグラフ行列.

ここは 80 ページ目

グラフ理論 2005

担当 : 大学院情報科学研究科 井上 純一となる. この行列式は直ちに計算できて, グラフ G の全域木の個数は

τ (G)

=31 0

10

3 00 3=331

13= 3 × 8 = 24(64)と求まる.
一方で点行列式法を使うとなると, 点行列を求めなければならないが, このグラフは 5 点からなるグラフなので, 点行列 D のサイズは 5 × 5 であり, 具体的に次のように与えられる.

D3 −1=  0 −1−1−1−1 −102 −1 00 

−1 3 −1 −1 0 −1 3 −1 0 −1 −1 3(65)

従って, この行列 D の 5 行 5 列における余因子によってグラフ G の全域木の本数が与えられて

3
τ (G)

= (−1)5+5−1−10−1 20 −1−1 0
3 −1−1−10(66)3となる. しかし, 計算の手数から言うと, ここから所望の個数を求めるためには余因子展開法等を使って行列式を計算しなければならない. ここでは実際に展開を実行し, 行列式のサイズを段階的に落としていってみると

2τ (G)==+−1−100−1−10−1−1 3 −1 + 2 −1 0−1 3 −10 −1 3 0 −13 −1−1 0
3 −1++ (−1)+3 2−1 3−1 3−1 3−1 32 −1−1 0= 3{2 × 8 − 3} + {−8 − 1} + {−1 − 5} = 24−(−1)
−1 3
3 −1
3 −10


3 −1−1 3+(67)となり, 確かに閉路行列式法による結果と一致する. しかし, 計算の手間は閉路行列式法の方が少ないことがわかるであろう.

演習問題 7
今回の講義で学んだ行列木定理を用いて Cayley の定理を証明せよ.

ここは 81 ページ目