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

标签：

• Tokyo-University
• Adjacency-Matrix-and-Walk-Counting
• Spectral-Diameter-Bound
• Laplacian-Positive-Semidefiniteness
• Consensus-Dynamics-and-Algebraic-Connectivity

Author

hari64boli64

Description

頂点集合 $V = \{v_1, v_2, \ldots, v_n\}$ と枝集合 $E$ からなる連結無向グラフ $G = (V, E)$ を考える。 頂点 $v_i$ に接続する枝の本数を $d_i$ と書く。 ただし、$G$ は自己閉路や多重枝は無いものとする。$n \times n$ 行列 $A = (a_{ij}), L = (l_{ij})$ を

$$a_{ij} = \begin{cases} 1 & \text{($ \{v_i, v_j\} \in E$ のとき)}, \\ 0 & \text{(それ以外のとき)} \end{cases}, \quad l_{ij} = \begin{cases} -1 & \text{($ \{v_i, v_j\} \in E$ のとき)}, \\ d_i & (i = j\text{ のとき}), \\ 0 & \text{(それ以外のとき)} \end{cases}$$

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

(1) 行列 $A$ のべき乗 $A^k$ の $(i, j)$ 成分は何を表わすか。

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

(3) 行列 $L$ の非零固有値に対応する固有ベクトル $u = (u_i)$ について、$\sum_{i=1}^{n} u_i = 0$ となることを示せ。

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

(5) 関数 $V : \mathbb{R}^n \rightarrow \mathbb{R}$ を

$$V(x) = \frac{1}{2} \sum_{1 \leq i < j \leq n} a_{ij}(x_i - x_j)^2 \quad (x \in \mathbb{R}^n)$$

と定義し、$x(t) = (x_1(t), x_2(t), \ldots, x_n(t))$ に関する微分方程式系

$$\frac{\text{d}x_i(t)}{\text{d}t} = - \frac{\partial V(x)}{\partial x_i} \bigg|_{x = x(t)} \quad (i = 1, 2, \ldots, n)$$

を考える。初期値 $x(0) = (c_1, c_2, \ldots, c_n)$ に対する解 $x(t)$ の極限 $\overline{x} = \lim_{t \to \infty} x(t)$ を求め、収束の速さについて論じよ。

题目描述

设 $G=(V,E)$ 为连通简单无向图，顶点集 $V=\{v_1,\ldots,v_n\}$，顶点 $v_i$ 的度为 $d_i$。定义邻接矩阵 $A=(a_{ij})$ 与图 Laplacian 矩阵 $L=(l_{ij})$：

$$a_{ij}= \begin{cases} 1,&\{v_i,v_j\}\in E,\\ 0,&\text{其他}, \end{cases}$$

$$l_{ij}= \begin{cases} -1,&\{v_i,v_j\}\in E,\\ d_i,&i=j,\\ 0,&\text{其他}. \end{cases}$$

1. 说明 $A^k$ 的 $(i,j)$ 元所表示的图论量。
2. 两顶点间距离定义为连接它们的路径中最少边数。证明任意两顶点间的距离严格小于 $A$ 的不同特征值个数。
3. 对 $L$ 的任一非零特征值所对应的特征向量 $u=(u_i)$，证明 $\sum_{i=1}^nu_i=0.$
4. 证明 $L$ 的所有特征值均为非负实数。
5. 定义
   $$V(x)=\frac12\sum_{1\le i<j\le n}a_{ij}(x_i-x_j)^2$$
   以及梯度流
   $$\frac{dx_i(t)}{dt} =-\left.\frac{\partial V(x)}{\partial x_i}\right|_{x=x(t)} \quad(i=1,\ldots,n).$$
   对初值 $x(0)=(c_1,\ldots,c_n)$，求 $\bar x=\lim_{t\to\infty}x(t),$ 并讨论收敛速度。

Kai

(1)

頂点 $i$ から頂点 $j$ へ長さが $k$ の経路の数

(2)

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

(3)

$$\begin{aligned} & \sum_{j=1}^{n}{0}=0 \\ \Leftrightarrow & \sum_{j=1}^{n}{0u_j}=0 \\ \Leftrightarrow & \sum_{j=1}^{n}\left(\sum_{i=1}^{n}{L_{ij}} \right)u_j=0 \\ \Leftrightarrow & \sum_{i=1}^{n}\sum_{j=1}^{n}{L_{ij}u_j}=0 \\ \Leftrightarrow & \sum_{i=1}^{n}{(Lu)_i}=0 \\ \Leftrightarrow & \sum_{i=1}^{n}{\lambda u_i}=0 \\ \Leftrightarrow & \sum_{i=1}^{n}{u_i}=0 \\ \end{aligned}$$

(4)

$$\begin{aligned} \boldsymbol{x}^T L \boldsymbol{x} & =\sum_{i,j}x_i L_{ij} x_j \\ & =\sum_{i,j}x_i (D_{ij}-A_{ij}) x_j \\ & =\sum_{i}x_i^2 D_{ii}-\sum_{i<j}x_i x_j A_{ij}- \sum_{i>j}x_i x_j A_{ij} \\ & =\sum_{i}\left(x_i^2 \sum_{j}{A_{ij}}\right)-\sum_{i<j}x_i x_j A_{ij}- \sum_{i<j}x_j x_i A_{ji} \\ & =\sum_{i<j}(x_i^2 -2x_i x_j +x_j^2) A_{ij} \\ & =\sum_{i<j}a_{ij}(x_i -x_j)^2 \\ & \geq 0 \end{aligned}$$

(5)

$\frac{\text{d}\boldsymbol{x}}{\text{d}t}=-L\boldsymbol{x}$ より、$\boldsymbol{x}(t)=e^{-Lt}\boldsymbol{x}(0)$ となる。

$L$ の固有値が全て非負実数の為、$\boldsymbol{\overline{x}}=\lim_{t \to \infty}\boldsymbol{x}(t) = \boldsymbol{0}$ となる。

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