東京大学 情報理工学研究科 数理情報学 2016年8月実施 第5問

Author

hari64boli64

Description

頂点集合 と枝集合 からなる連結無向グラフ を考える。 頂点 に接続する枝の本数を と書く。 ただし、 は自己閉路や多重枝は無いものとする。 行列 を

と定義する。以下の設問に答えよ。

(1) 行列 のべき乗 の 成分は何を表わすか。

(2) 2 頂点間の距離をその 2 頂点を結ぶ経路の最小枝数で定める。任意の 2 頂点間の距離は、 の相異なる固有値の個数より小さいことを示せ。

(3) 行列 の非零固有値に対応する固有ベクトル について、 となることを示せ。

(4) 行列 の固有値はすべて非負実数であることを示せ。

(5) 関数 を

と定義し、 に関する微分方程式系

を考える。初期値 に対する解 の極限 を求め、収束の速さについて論じよ。

Kai

(1)

頂点 から頂点 へ長さが の経路の数

(2)

ケーリーハミルトンの定理より、背理法

(3)

(4)

(5)

より、 となる。

の固有値が全て非負実数の為、 となる。

また、収束の速さは の固有値に依存する。