正答4
解説
正解は4です。
最早結合点時刻とは、その結合点から始まる作業を最も早く開始できる日です。
複数の矢印が流れ込む結合点では、先行するすべての作業が終わらないと次へ進めないため、到達経路のうち最大の値をとります。
図の作業は、A(1から2、3日)、B(1から3、2日)、C(2から3、1日)、D(2から4、4日)、E(2から5、2日)、F(3から5、2日)、G(4から6、1日)、H(5から6、1日)です。
さらに、結合点4から結合点5へ所要日数0日のダミー作業(破線)があります。
【計算】
結合点1の最早結合点時刻は0日です。
結合点2は、Aを経由して0+3=3日です。
結合点3は、Bを経由すると0+2=2日、Cを経由すると3+1=4日なので、大きいほうの4日です。
結合点4は、Dを経由して3+4=7日です。
結合点5は、Eを経由すると3+2=5日、Fを経由すると4+2=6日、ダミー作業を経由すると7+0=7日です。
最大値をとるので、結合点5の最早結合点時刻は7日です。
【選択肢別解説】
1:× 4日は、BとFだけを通る経路(2+2)の値です。
最早結合点時刻は最大値をとるので誤りです。
2:× 5日は、AとEを通る経路の値です。
ほかにもっと時間の掛かる経路があるので誤りです。
3:× 6日は、A、C、Fを通る経路の値です。
ダミー作業を経由する経路を見落としています。
4:○ A、D、ダミー作業を通る経路が7日で最も長く、結合点5の最早結合点時刻は7日です。
【ポイント】
ダミー作業は所要日数0ですが、作業の順序関係(Dが終わらないとHを始められない)を表すので、見落とさないことが重要です。
最早結合点時刻は前から順に最大値、最遅結合点時刻は後ろから順に最小値をとって求めます。