大阪大学 情報科学研究科 情報工学 2022年8月実施 離散構造

Author

祭音Myyura

Description

グラフ (graph) は、 個の頂点 (vertex) の集合 と、頂点のペアにより定義される辺 (edge) の集合 により構成される無向グラフ (undirected graph) である。 また、グラフ は同じ頂点を結ぶ辺を持たず、かつ、任意の2つの頂点間を結ぶ辺は高々一つであるとする。

頂点 と の間に辺が存在するとき、頂点 と は隣接する (adjacent) と呼ぶ。 次の規則で定義される 成分 を持つ 行列 をグラフ の隣接行列 (adjacency matrix) と呼ぶ。

また、隣接する頂点の系列 (, ) を、長さ の歩道 (walk) と呼ぶ。 歩道は同じ頂点を複数含んでも良い。 例えば、下図グラフ において、 は長さ 4 の歩道である。

以下の各問に答えよ。

(1) 上図グラフ の隣接行列 を示せ。

(2) グラフ における、頂点 から の長さ () の歩道の総数を、 で表すこととする。

• (2-1) 上図グラフ について考える。グラフ において、 の値を答えよ。
• (2-2) 上図グラフ において、 の値を答えよ。
• (2-3) グラフ における隣接行列 の 乗を で表す。行列 の 成分を と表現すると、 になることを証明せよ。

(3) 頂点数が の完全グラフ (complete graph) を とする。

• (3-1) 完全グラフ の辺の数を を用いて示せ。
• (3-2) 一般に、 のグラフが を含むかどうかは、隣接行列を用いて判定することができる。隣接行列 の 成分を , の 成分を としたときに、 と を用いて、グラフ が を含むかどうかを判定する方法を理由とともに説明せよ。

(4) のグラフ が連結である (connected) とは、行列 がそのいずれかの成分にも 0 を持たないことを調べることで確認できる。 を の単位行列 (identity matrix) としたときに、隣接行列 , , を用いて空間の を示せ。

Kai

(1)

(2)

(2-1)

よって、 である。

(2-2)

(2-3)

行列 を二乗したとき、その 成分 は、次のように計算される

ここで、 となるのは の時のみである。 隣接行列の定義より、頂点 から への辺が存在し、かつ、頂点 から への辺が存在することがわかる。 よって、長さ 2 の歩道 が存在する。

従って、 は、全ての可能な中間頂点 を通って から への長さ 2 の歩道の個数となることがわかる、すなわち、 である。

次に、 は頂点 から の長さ の歩道の総数を表すと仮定する。

同様に、 は、次のように計算すると、

は頂点 から の長さ の歩道の個数となることがわかる。

(3)

(3-1)

(3-2)

以下の条件を満たす が存在するとき、

グラフ が完全グラフ3 を含むから、各成分 について、

であるかどうかをチェックすれば、グラフ が を含むかどうかはわかる。

(4)

(The idea is to check the value of for each )

or