論理回線の最大多重数

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

図のネットワークの各辺には同時使用可能な論理回線の多重度が与えられている。X地点からY地点まで同時に使用できる論理回線の最大本数はいくつか。

X-A:4, X-B:4, X-C:3, A-B:2, B-C:1, A-D:1, B-D:2, B-E:3, C-F:4, D-E:2, D-Y:3, E-Y:3, E-G:4, F-E:2, F-G:3, G-Y:6

ア　8

イ　9

ウ　10

エ　11

IPAの有向ではないネットワーク図を辺と容量で文章化。

正解を表示

ウ

この問題に出てくる用語

最大フロー問題: ネットワークの各区間に、同時に流せる量（容量）の上限があるとき、出発点から到着点まで、全体で同時に最大どれだけ流せるかを求める問題。最大の流量は、ネットワークを出発側と到着側に分ける切り口のうち、容量の合計が最も小さいもの（最小カット）の値に等しい。