FindMaximumFlow
FindMaximumFlow[g,s,t]
グラフ g の始点 s と目的頂点 t の間の最大フローを求める.
FindMaximumFlow[m,s,t]
辺容量行列 m のグラフ内の頂点指標 s と t の間の最大フローを求める.
FindMaximumFlow[data,{s1,…},{t1,…}]
複数の始点 s1, …と複数の目的頂点 t1, …の間の最大フローを求める.
FindMaximumFlow[data,source,target,"property"]
"property"の値を返す.
FindMaximumFlow[{vw,…},…]
規則 vw を使ってグラフ g を指定する.
詳細とオプション
- FindMaximumFlowは,容量の制約に従って,始点から目的頂点への最大フローを求める.
- デフォルトで,最大フローが返される.
- FindMaximumFlowでは,行列とSparseArrayオブジェクトを使うことができる.
- 無向グラフの場合,辺には同時に同じ容量の両方向へのフローがあるとみなされる.
- 自己ループは無視され,平行の辺は合併される.
- FindMaximumFlow[data,source,target,"OptimumFlowData"]は,OptimumFlowDataオブジェクト flowdata を返す.このオブジェクトは,flowdata["property"]の形式で追加的な特性を抽出するのに使うことができる.
- FindMaximumFlow[data,source,target,"property"]を使って"property"の値を直接与えることができる.
- 最適フローデータに関連する特性には次がある.
-
"EdgeList" フローに貢献している辺のリスト "FlowGraph" フローに貢献している頂点と辺のグラフ "FlowMatrix" 頂点ペアの間の辺のフローの行列 "FlowTable" 辺のフローのフォーマットされた表 "FlowValue" フローの値 "ResidualGraph" フローの残差グラフ "VertexList" フローに貢献している頂点のリスト - 使用可能なオプションには次がある.
-
EdgeCapacity Automatic 各辺の容量 VertexCapacity Automatic 各頂点の容量 - デフォルト設定のEdgeCapacity->Automaticでは,ある辺の辺容量は,可能な場合はグラフ g のEdgeCapacityで,その他の場合は1であるとみなされる.
- デフォルト設定のVertexCapacity->Automaticでは,頂点の頂点容量は,可能な場合はグラフ g のVertexCapacityで,その他の場合はInfinityであるとみなされる.
- FindMaximumFlowは,無向グラフ,有向グラフ,多重グラフ,混合グラフに使うことができる.
例題
すべて開くすべて閉じるスコープ (10)
FindMaximumFlowは無向グラフに使うことができる:
FindMaximumFlowは大きいグラフに使うことができる:
オプション (2)
EdgeCapacity (1)
デフォルトで,辺の容量は,指定可能な場合はそのEdgeCapacity特性であり,指定可能ではない場合は1であるとみなされる:
EdgeCapacity->capacities を使って辺の容量を設定する:
VertexCapacity (1)
デフォルトで,頂点の容量は,指定可能な場合はそのVertexCapacity特性であり,指定可能ではない場合はInfinityであるとみなされる:
VertexCapacity->capacities を使って頂点の容量を設定する:
アプリケーション (7)
輸送網 (3)
ネットワークの接続性 (2)
特性と関係 (5)
2つの頂点間の頂点連結度はFindMaximumFlowで求めることができる:
テキスト
Wolfram Research (2012), FindMaximumFlow, Wolfram言語関数, https://reference.wolfram.com/language/ref/FindMaximumFlow.html (2015年に更新).
CMS
Wolfram Language. 2012. "FindMaximumFlow." Wolfram Language & System Documentation Center. Wolfram Research. Last Modified 2015. https://reference.wolfram.com/language/ref/FindMaximumFlow.html.
APA
Wolfram Language. (2012). FindMaximumFlow. Wolfram Language & System Documentation Center. Retrieved from https://reference.wolfram.com/language/ref/FindMaximumFlow.html