基本情報技術者 2011年秋期午前（科目A）問51

問題文

次のアローダイアグラムで表されるプロジェクトがある。結合点5の最早結合点時刻は第何日か。

選択肢

ア：4

イ：5

ウ：6

エ：7（正解）

結合点5の最早結合点時刻は第何日か【午前2 解説】

要点まとめ

結論：結合点5の最早結合点時刻は第7日で、選択肢はエです。
根拠：各前結合点から到達する時刻の最大値を取るため、2→5は5日、3→5は6日、4→5（ダミー）で7日となります。
差がつくポイント：ダミー矢印は所要日数0として扱い、最早時刻は「最大」を取る点を確実に押さえてください。

正解の理由

結合点の最早結合点時刻は、その結合点に入るすべての作業の完了時刻のうち最大値になります。出発点を結合点1とし時刻0とすると、各経路の到達時刻は次の通り計算され、結合点5では最大が7日となるため正解はエです。

よくある誤解

最早時刻を「最小値」で決めてしまう間違い：複数経路のうち最も遅れて到達する経路が決定します。
ダミー作業を無視してしまう誤り：ダミーは0日でも依存関係を作るため、到達時刻に影響します。
中間結合点（例：結合点3）の計算を片方の入力だけで済ませるミス：すべての入力経路を評価する必要があります。

解法ステップ

出発結合点1の時刻を $0$ とする。
結合点2：1→2（A:3日）より $0 + 3 = 3$ 日。
結合点3：1→3（B:2日）で $0 + 2 = 2$ 、2→3（C:1日）で $3 + 1 = 4$ 、最大で $4$ 日。
結合点4：2→4（D:4日）より $3 + 4 = 7$ 日。
結合点5：各経路の到達時刻を計算し最大を取る。
- 2→5（E:2日）より $3 + 2 = 5$ 日
- 3→5（F:2日）より $4 + 2 = 6$ 日
- 4→5（ダミー:0日）より $7 + 0 = 7$ 日
  → 最大値は $7$ 日、よって結合点5の最早結合点時刻は第7日。

（一般式）結合点

j

の最早結合点時刻

E_{j}

は

E_{j} = max_{i \to j} (E_{i} + d_{i \to j})

で与えられます。

選択肢別の誤答解説

ア: 4日 — 結合点3の時刻のみ（または2→5経路のみ）を用いて最大値を取らず、最遅経路を見落としている誤りです。
イ: 5日 — 2→5経路（3+2=5）の値をそのまま答えとしてしまい、3→5や4→5からの到達時刻を評価していないミスです。
ウ: 6日 — 3→5経路（4+2=6）を最大と見なしてしまった場合で、4→5（ダミー）経路の影響を無視しています。
エ: 7日 — 正解。2→4→5 の流れ（3+4+0=7）が最も遅いため最大値となります。

補足コラム

ダミー作業（破線矢印）は所要日数0でありながら依存関係を明示するために使われます。アローダイアグラム（AONではなくAOA形式）ではイベント（結合点）が作業の開始・終了を示し、イベントの最早時刻は「入ってくる作業の完了時刻の最大値」で決まります。クリティカルパスを求める際にもこの最早時刻の計算が基礎になります。

FAQ

Q1. 最早結合点時刻と最早開始時刻の違いは何ですか？
A1. 最早結合点時刻はイベント（ノード）の発生時刻、最早開始時刻は作業（アロー）が始められる時刻です。作業i→jの最早開始は結合点iの最早時刻に一致します。

Q2. ダミー作業に所要日数を設定することはありますか？
A2. ダミーは依存のみを表すため所要日数は0で、スケジュール上の時間を消費しません。ただしネットワークの論理構造に影響を与えます。

Q3. 複数の経路があるとき、なぜ最大値を取るのですか？
A3. その結合点が次の作業を開始できるのは、すべての先行作業が完了した後です。したがって最も遅い完了時刻が制約になります。

関連キーワード: アローダイアグラム、最早結合点時刻、ダミー作業、クリティカルパス法、PERT、CPM、結合点計算、スケジュール管理

← 前の問題へ次の問題へ →

\ せっかくなら /

基本情報技術者を
クイズ形式で学習しませんか？

クイズ画面へ遷移する→

すぐに利用可能！