与えられたグラフ、パスグラフ $P_4$、サイクルグラフ $C_5$ について、それぞれのグラフの直径と、その補グラフの直径を求める。

1. 問題の内容

与えられたグラフ、パスグラフ $P_4$、サイクルグラフ $C_5$ について、それぞれのグラフの直径と、その補グラフの直径を求める。

2. 解き方の手順

1) 与えられたグラフ:

まず、与えられたグラフの頂点に名前を付ける。左下の頂点をA、右下の頂点をB、真ん中の頂点をC、上の左の頂点をD、上の右の頂点をEとする。

グラフの直径は、グラフ内の2頂点間の距離の最大値である。

A-C-D間の距離は2、A-C-E間の距離は2、B-C-D間の距離は2、B-C-E間の距離は2、D-E間の距離は2なので、与えられたグラフの直径は2である。

補グラフは、元のグラフに存在しない辺のみを持つグラフである。この補グラフは、A-B間に辺があり、D-E間に辺がないという元のグラフからわかるように、元のグラフから簡単に作成できる。元のグラフに辺がある頂点間には辺がなく、元のグラフに辺がない頂点間には辺がある。この補グラフでは、A-B間に辺があるため、AからBまでの距離は1である。AからDまでの距離は、A-B-Dで2である。したがって、補グラフの直径は2である。

2) パスグラフ $P_4$:

$P_4$は4つの頂点を持つパスグラフである。4頂点に1,2,3,4と名前を付ける。頂点間の辺は、1-2, 2-3, 3-4である。$P_4$の直径は3 (1-4)である。

$P_4$の補グラフでは、頂点1と3の間、頂点1と4の間、頂点2と4の間に辺がある。この補グラフにおいて、頂点1から4への距離は1である。頂点1から2への距離は2(1-3-2など)。よって直径は2である。

3) サイクルグラフ $C_5$:

$C_5$は5つの頂点を持つサイクルグラフである。5頂点に1,2,3,4,5と名前を付ける。頂点間の辺は、1-2, 2-3, 3-4, 4-5, 5-1である。$C_5$の直径は2である。

$C_5$の補グラフでは、頂点1と3, 1と4, 2と4, 2と5, 3と5の間に辺がある。つまり、$C_5$の補グラフは、$C_5$と同じグラフになる。なので直径は2。

3. 最終的な答え

1) 与えられたグラフ:

グラフの直径: 2

補グラフの直径: 2

2) $P_4$:

グラフの直径: 3

補グラフの直径: 2

3) $C_5$:

グラフの直径: 2

補グラフの直径: 2