WOLFRAM

Wolfram言語 ＆ システムドキュメントセンター

割当て問題

ある数学学部が7つのクラスを提供したいと考えている．8人の教授がいて，それぞれ特定のクラスを教えたいと考えている．教授たちが自分の教えたいクラスだけを教えた場合の最大のマッチを求める．

    
教授たちと彼らが教えたいと思うクラスの間で，二部グラフを構築する．
Wolfram Language code: g = [image];
すべての教授からすべてのクラスへの最大フローがマッチを示す：
Wolfram Language code: flowgraph = EdgeAdd[g, Union[Flatten[EdgeList[g] /. {a_b_ :> {"s"a, b"t"}}]]];
Wolfram Language code: VertexDelete[FindMaximumFlow[flowgraph, "s", "t", "FlowGraph"], {"s", "t"}]