与えられたグラフに対して、以下の3つの問いに答えます。 (1) 頂点aから頂点dへの長さ3の歩道と道の数をすべて列挙する。 (2) グラフの隣接行列Aを書き出す。 (3) グラフが一筆書き(オイラー路)可能かどうか判定する。

1. 問題の内容

与えられたグラフに対して、以下の3つの問いに答えます。

(1) 頂点aから頂点dへの長さ3の歩道と道の数をすべて列挙する。

(2) グラフの隣接行列Aを書き出す。

(3) グラフが一筆書き(オイラー路)可能かどうか判定する。

2. 解き方の手順

(1) aからdへの長さ3の歩道と道の数を数える。

* 歩道：同じ辺を複数回通っても良い

* 道：同じ辺を二度以上通らない

aから出発して、長さ3でdに到達する歩道と道を列挙する。

* a -> b -> a -> d (歩道)

* a -> b -> c -> d (道、歩道)

* a -> c -> b -> d (道、歩道)

* a -> c -> a -> d (歩道)

合計：歩道は4つ、道は2つ。

(2) 隣接行列Aを作成する。

グラフの頂点をa, b, c, dとする。隣接行列Aの(i, j)成分は、頂点iから頂点jへの辺が存在すれば1、存在しなければ0とする。

Aは4x4の行列になる。

$A = \begin{pmatrix}

0 & 1 & 1 & 1 \\

1 & 0 & 1 & 0 \\

1 & 1 & 0 & 1 \\

1 & 0 & 1 & 0

\end{pmatrix}$

(3) オイラー路(一筆書き)が可能かどうか判定する。

オイラー路が存在するための条件は、グラフの次数が奇数の頂点の数が0または2であること。グラフの各頂点の次数を調べると、

* a: 3

* b: 2

* c: 3

* d: 2

次数が奇数の頂点(a, c)が2つあるため、このグラフはオイラー路を持つ。つまり一筆書き可能である。

3. 最終的な答え

(1) 歩道: 4つ、道: 2つ

(2) $A = \begin{pmatrix}

0 & 1 & 1 & 1 \\

1 & 0 & 1 & 0 \\

1 & 1 & 0 & 1 \\

1 & 0 & 1 & 0

\end{pmatrix}$

(3) 一筆書き可能