平成24年度 秋期 ネットワークスペシャリスト試験 午前II 問4

この問題は、ネットワークの最大流問題に該当します。与えられたネットワークで、XからYまでの最大流を求めるには、各経路の容量を考慮しながら最大の流れを確保する必要があります。

手順

1. グラフを確認
   各辺に示された数値が、その辺の最大容量（多重度）を表しています。XからYに至る経路のすべてを考慮します。

2. 経路を分ける
   以下のように、いくつかの経路を特定して、それぞれの経路で流せる流量を計算します： - 経路1: X → A → D → E → Y （最小容量 = 1） - 経路2: X → A → B → E → Y （最小容量 = 2） - 経路3: X → B → E → Y （最小容量 = 2） - 経路4: X → C → F → G → Y （最小容量 = 3） - 経路5: X → C → F → E → Y （最小容量 = 3）

3. 最大流を計算
   各経路の最小容量を合計すると、最大流量は 10 となります。

答え

ウ: 10