名古屋大学 情報学研究科 数理情報学専攻 2018年2月実施 問題3（離散数学）

标签：

• 名古屋大学
• 泰勒级数
• 几何级数
• 邻接矩阵
• 顶点度数
• 数学归纳法

Author

祭音Myyura (co-authored with GPT 6 Astra)

Description

外国人留学生は、英語での回答は可能。

I.

以下の各問に答えよ。

(1)

$$\frac{1}{(1-x)(1-ax)}$$

のマクローリン展開（Maclaurin expansion）を求めよ。

(2)

$$\frac{1-abx^2}{(1-x)(1-ax)(1-bx)(1-abx)}$$

のマクローリン展開を求めよ。

II.

以下の各問に答えよ。

(1) 次の図のグラフ $G$ について、以下の各問に答えよ。

(i) $G$ の隣接行列 $A$ を求めよ。

(ii) $A^2$ を求めよ。

(iii) 頂点 1 と 3 を結ぶ長さ 2 の路がいくつあるかを答えよ。また、その導出方法を述べよ。

(2) $m\ (\ge1)$ 本の辺を持つ連結な単純無向グラフ $G$ の隣接行列を $A$ とする。以下の各問に答えよ。

(i) 主張 1：「行列 $A^2$ の対角成分の総和は $2m$ となる」

主張 1 が正しいか否かを答えよ。正しい場合は証明を与え、そうでない場合は反例を示せ。

(ii) 主張 2：「$A^k\ (k\ge1)$ の $(i,j)$ 要素は $G$ の頂点 $i$ と $j$ を結ぶ長さ $k$ の路（単純路でないものや初等路でもないものも含む）の数と等しい」

主張 2 が正しいか否かを答えよ。正しい場合は証明を与え、そうでない場合は反例を与えよ。

用語

日本語	English・補足
グラフ	graph
無向	undirected
隣接行列	adjacency matrix
対角成分	diagonal elements
頂点	vertex
辺	edge
連結	connected
単純グラフ	simple graph（並列辺も自己ループも含まないグラフ）
並列辺	parallel edges（多重辺（multiple edges）ともいう）
自己ループ	self-loop（ループ（loop）ともいう）
路	path
単純路	simple path
初等路	elementary path
路の長さ	length of a path（路に含まれる辺数）

题目描述

外国留学生可以用英语作答。

I.

回答下列各问。

(1) 求

$$\frac{1}{(1-x)(1-ax)}$$

的麦克劳林展开（Maclaurin expansion）。

(2) 求

$$\frac{1-abx^2}{(1-x)(1-ax)(1-bx)(1-abx)}$$

的麦克劳林展开。

II.

回答下列各问。

(1) 对于上图所示的图 $G$，回答以下问题。

(i) 求 $G$ 的邻接矩阵 $A$。

(ii) 求 $A^2$。

(iii) 回答连接顶点 1 与顶点 3、长度为 2 的路共有多少条，并说明如何得到这一结果。

(2) 设 $A$ 是具有 $m\ (\ge1)$ 条边的连通简单无向图 $G$ 的邻接矩阵。回答以下问题。

(i) 命题 1：“矩阵 $A^2$ 的对角元素之和为 $2m$。”

判断命题 1 是否正确。若正确，给出证明；否则给出反例。

(ii) 命题 2：“$A^k\ (k\ge1)$ 的第 $(i,j)$ 个元素，等于图 $G$ 中连接顶点 $i$ 与顶点 $j$、长度为 $k$ 的路的条数（也包括不是单纯路以及不是初等路的情形）。”

判断命题 2 是否正确。若正确，给出证明；否则给出反例。

术语对照

日语	中文 / English・说明
グラフ	图 / graph
無向	无向 / undirected
隣接行列	邻接矩阵 / adjacency matrix
対角成分	对角元素 / diagonal elements
頂点	顶点 / vertex
辺	边 / edge
連結	连通 / connected
単純グラフ	简单图 / simple graph（既不含平行边，也不含自环的图）
並列辺	平行边 / parallel edges（也称多重边（multiple edges））
自己ループ	自环 / self-loop（也称环（loop））
路	路 / path
単純路	单纯路 / simple path
初等路	初等路 / elementary path
路の長さ	路的长度 / length of a path（路所包含的边数）

Kai

I.

(1)

等比級数の積を用いると、

$$\begin{aligned} \frac{1}{(1-x)(1-ax)} &=\left(\sum_{r=0}^{\infty}x^r\right) \left(\sum_{s=0}^{\infty}a^sx^s\right)\\ &=\sum_{n=0}^{\infty}\left(\sum_{s=0}^{n}a^s\right)x^n. \end{aligned}$$

したがって、求める展開は

$$\boxed{ \begin{aligned} &\frac{1}{(1-x)(1-ax)}\\ &=\sum_{n=0}^{\infty}(1+a+\cdots+a^n)x^n \end{aligned} }.$$

特に、$a\ne1$ と $a=1$ を分けて書けば、

$$\begin{aligned} &\frac{1}{(1-x)(1-ax)}\\ &= \begin{cases} \displaystyle\sum_{n=0}^{\infty}\frac{1-a^{n+1}}{1-a}x^n, & a\ne1,\\[6pt] \displaystyle\sum_{n=0}^{\infty}(n+1)x^n, & a=1. \end{cases} \end{aligned}$$

例えば $|x|<1/\max\{1,|a|\}$ でこれらの級数は収束し、元の関数に等しい。

(2)

(2) の関数を $F(x)$ とし、$S_n(t)=1+t+\cdots+t^n$ とおく。求める展開は

$$\boxed{ F(x)=\sum_{n=0}^{\infty}S_n(a)S_n(b)x^n }.$$

すなわち、各係数は

$$[x^n]F(x) =\left(\sum_{r=0}^{n}a^r\right) \left(\sum_{s=0}^{n}b^s\right).$$

これを示すため、まず $a\ne1$、$b\ne1$ とすると、等比級数により

$$\begin{aligned} &\sum_{n=0}^{\infty}S_n(a)S_n(b)x^n\\ &=\frac{1}{(1-a)(1-b)} \\ &\quad\times\Bigl\{\frac{1}{1-x}-\frac{a}{1-ax}\\ &\qquad-\frac{b}{1-bx}+\frac{ab}{1-abx}\Bigr\}\\ &=\frac{1-abx^2}{(1-x)(1-ax)(1-bx)(1-abx)}. \end{aligned}$$

両辺の各 $x^n$ の係数は $a,b$ の多項式なので、この係数の等式は $a=1$ または $b=1$ の場合にも成立する。係数を閉じた形で書けば、

$$\begin{aligned} &S_n(a)S_n(b)\\ &= \begin{cases} \displaystyle\frac{(1-a^{n+1})(1-b^{n+1})}{(1-a)(1-b)}, & a\ne1,\ b\ne1,\\[7pt] \displaystyle(n+1)\frac{1-b^{n+1}}{1-b}, & a=1,\ b\ne1,\\[7pt] \displaystyle(n+1)\frac{1-a^{n+1}}{1-a}, & a\ne1,\ b=1,\\[7pt] (n+1)^2,& a=b=1. \end{cases} \end{aligned}$$

特に $a=b$ や $ab=1$ でも、有限和による係数表示をそのまま使える。収束する範囲としては、例えば

$$|x|<\frac{1}{\max\{1,|a|,|b|,|ab|\}}$$

を取ればよい。

II.

(1)

(i)

行と列を頂点 $1,2,3,4,5$ の順に並べる。辺の集合は

$$\begin{aligned} E=\{&\{1,2\},\{1,3\},\{1,4\},\{2,3\},\\ &\{2,4\},\{3,4\},\{3,5\},\{4,5\}\} \end{aligned}$$

であるから、隣接行列は

$$\boxed{ A=\begin{pmatrix} 0&1&1&1&0\\ 1&0&1&1&0\\ 1&1&0&1&1\\ 1&1&1&0&1\\ 0&0&1&1&0 \end{pmatrix} }.$$

(ii)

行列積を計算すると、

$$\boxed{ A^2=\begin{pmatrix} 3&2&2&2&2\\ 2&3&2&2&2\\ 2&2&4&3&1\\ 2&2&3&4&1\\ 2&2&1&1&2 \end{pmatrix} }.$$

(iii)

2 本であり、具体的には

$$1\to2\to3,\qquad 1\to4\to3$$

である。長さ 2 の路の中間頂点は、頂点 1 と頂点 3 の両方に隣接している必要があり、そのような頂点は 2 と 4 だけである。行列を用いれば、

$$(A^2)_{13}=\sum_{r=1}^{5}A_{1r}A_{r3}=2$$

からも求められる。

(2)

(i)

主張 1 は正しい。 頂点数を $N$ とする。単純無向グラフの隣接行列は $A_{ij}=A_{ji}\in\{0,1\}$ を満たすため、

$$(A^2)_{ii} =\sum_{j=1}^{N}A_{ij}A_{ji} =\sum_{j=1}^{N}A_{ij} =\deg(i).$$

したがって、対角成分の総和は全頂点の次数の和に等しい。各辺はその両端の次数に 1 ずつ寄与するので、

$$\boxed{\operatorname{tr}(A^2)=\sum_{i=1}^{N}\deg(i)=2m}.$$

(ii)

主張 2 は正しい。 本問では、辺や頂点を繰り返し通るものも含めて「路」を数える。すなわち、隣り合う頂点が辺で結ばれている頂点列（walk）を、始点 $i$ と終点 $j$ を固定して数える。

$W_k(i,j)$ を、頂点 $i$ から頂点 $j$ に至る長さ $k$ の路の数とし、$W_k(i,j)=(A^k)_{ij}$ を $k$ に関する数学的帰納法で示す。

$k=1$ では、$i,j$ の間に辺があるときだけ長さ 1 の路が 1 本存在する。よって $W_1(i,j)=A_{ij}$ である。

$k$ で成立すると仮定する。長さ $k+1$ の路を、最後の 1 辺の直前の頂点 $r$ によって分類すると、

$$\begin{aligned} W_{k+1}(i,j) &=\sum_{r=1}^{N}W_k(i,r)A_{rj}\\ &=\sum_{r=1}^{N}(A^k)_{ir}A_{rj}\\ &=(A^{k+1})_{ij}. \end{aligned}$$

各路の最後から 2 番目の頂点は一意なので、重複や数え落としはない。また、辺や頂点の再使用を許すため、長さ $k$ の路の末尾に辺を付け加える操作に追加の制約はない。以上より、すべての $k\ge1$ について主張が成立する。

Reference

• 名古屋大学大学院情報学研究科 数理情報学専攻 平成30年度入学試験問題（2018年2月8日実施、問題3：PDF 3～4ページ）