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[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は,無向グラフ,有向グラフ,多重グラフ,混合グラフに使うことができる.
例題
すべて開く すべて閉じる例 (2)
スコープ (10)
FindMaximumFlowは無向グラフに使うことができる:
FindMaximumFlow[[image], 1, 3]FindMaximumFlow[[image], 1, 3]FindMaximumFlow[[image], 1, 3]FindMaximumFlow[[image], 1, 3]FindMaximumFlow[[image], 1, 3]FindMaximumFlow[{1 -> 2, 2 -> 3, 3 -> 1, 3 -> 4}, 1, 3]FindMaximumFlow[(| | | | |
| - | - | - | - |
| 0 | 1 | 6 | 3 |
| 1 | 0 | 2 | 0 |
| 6 | 2 | 0 | 2 |
| 3 | 0 | 2 | 0 |), 1, 4]FindMaximumFlow[[image], {1, 2}, {3, 4, 5}]ℱ = FindMaximumFlow[[image], 1, 4, "OptimumFlowData"];ℱ["FlowValue"]ℱ["EdgeList"]ℱ["FlowMatrix"]//MatrixFormℱ["FlowGraph"]FindMaximumFlowは大きいグラフに使うことができる:
g = ExampleData[{"NetworkGraph", "Internet"}];{VertexCount[g], EdgeCount[g]}FindMaximumFlow[g, 1, 10]//Timingオプション (2)
EdgeCapacity (1)
デフォルトで,辺の容量は,指定可能な場合はそのEdgeCapacity特性であり,指定可能ではない場合は1であるとみなされる:
FindMaximumFlow[[image], 1, 2]EdgeCapacity->capacities を使って辺の容量を設定する:
FindMaximumFlow[[image], 1, 2, EdgeCapacity -> Range[5]]VertexCapacity (1)
デフォルトで,頂点の容量は,指定可能な場合はそのVertexCapacity特性であり,指定可能ではない場合はInfinityであるとみなされる:
FindMaximumFlow[[image], 1, 4]VertexCapacity->capacities を使って頂点の容量を設定する:
FindMaximumFlow[[image], 1, 4, VertexCapacity -> Range[4]]アプリケーション (7)
輸送網 (3)
1940年におけるソビエトの鉄道網に基づいて,ソビエト連邦西部を発して東欧の目的地に輸送可能な貨物の最大量を求める:
railway = \!\(\*GraphicsBox[«5»]\);指標を与えられた都市{1,5,6,7,9,12,13,18}から{44,40}までの最大フローの値:
data = FindMaximumFlow[railway, {1, 5, 6, 7, 9, 12, 13, 18}, {44, 40}, "OptimumFlowData"];data["FlowValue"]data["FlowGraph"]g = [image];バンクーバーからウィニペグまで運行することができる最大客車数を求める:
ℱ = FindMaximumFlow[g, "Vancouver", "Winnipeg", "OptimumFlowData"];ℱ["FlowValue"]Grid[{#, ℱ[#]}& /@ ℱ["EdgeList"], Frame -> All, Alignment -> Left]Panel[Show[{CountryData["Canada", "Shape"], ℱ["FlowGraph"]}, PlotRange -> {{-0.31, 0.083}, {0.04, 0.25}}]]以下の指定された容量の地域的な電力配電回路網で,ワンチャイに送ることができる最大電力を求める:
g = [image];FindMaximumFlow[g, "PowerStation", "WanChai"]FindMaximumFlow[g, "PowerStation", "WanChai", "FlowGraph"]ネットワークの接続性 (2)
アメリカ中西部のある都市の,社会福祉問題に関心がある10の組織間の情報のフローを表す有向ネットワーク.COUNからCOMMへの可能な最大情報フローを求める:
g = [image];FindMaximumFlow[g, "COUN", "COMM"]FindMaximumFlow[g, "COUN", "COMM", "FlowGraph"]ある町の住人は7人で,クラブが4つと政党が3つある.住民はそれぞれ少なくとも1つのクラブの会員である.各人が所属できる政党は厳密に1つだけである.均衡のとれた議会では,各クラブが議会でそのクラブを代表する人物を1名指名しなければならないが,その場合,政党
に所属する議員数が最大で
人でなければならない.均衡のとれた議会にすることが可能かどうかを求める:
g = [image];最大フローの値が4に等しいので,この町の議会は均衡がとれていると言える:
FindMaximumFlow[g, s, t]フローグラフは,可能な均衡のとれた議会構成とするためのメンバーが R1,R2,R4,R5であることを示している:
FindMaximumFlow[g, s, t, "FlowGraph"]割当て問題 (2)
ある企業にはさまざまな種類の仕事がある.被雇用者は数ある仕事の複数に適しているが,各人は一度に一つの仕事にしか行うことができない.一度に行える仕事の最大数を求める:
g = [image];すべての被雇用者からすべてのタスクへの最大フローによって,同時に行える仕事の数が得られる:
ℱ = FindMaximumFlow[g, {"Jesse", "Mark", "Erica", "Toby", "Jami", "Chris"}, {"Library", "QA", "Interface", "Kernel", "Sales"}, "OptimumFlowData", VertexCapacity -> ConstantArray[1, 11]];ℱ["FlowValue"]ℱ["FlowGraph"]ある女性の集団があり,各人が特定のグループの男性を好むとする.好みにあった場合にのみマッチングするとして最大マッチを求める:
g = [image];各人を1回だけマッチングしたいので,頂点の容量を1に制限する:
vc = ConstantArray[1, 8];
ℱ = FindMaximumFlow[g, {"Penny", "Alecia", "Mary", "Mara"}, {"Billy", "Dustin", "Bryan", "Scotty"}, "OptimumFlowData", VertexCapacity -> vc];ℱ["FlowValue"]ℱ["FlowGraph"]特性と関係 (5)
ℱ = FindMaximumFlow[[image], 1, 6, "OptimumFlowData"];(m = ℱ["FlowMatrix"])//MatrixFormTable[Total[m[[All, i]]], {i, 2, 5}]Table[Total[m[[i, All]]], {i, 2, 5}]g = [image];FindMaximumFlow[g, 1, 5]FindMaximumFlow[SimpleGraph[g], 1, 5]g = [image];FindMaximumFlow[g, 1, 7]EdgeConnectivity[g, 1, 7]2つの頂点間の頂点連結度はFindMaximumFlowで求めることができる:
g = [image];VertexConnectivity[g, 1, 4]FindMaximumFlow[g, 1, 4, VertexCapacity -> {EdgeCount[g], 1, 1, EdgeCount[g]}]関連するガイド
-
▪
- 経路,閉路,フロー ▪
- グラフ上の計算 ▪
- グラフとネットワーク
テキスト
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
BibTeX
@misc{reference.wolfram_2026_findmaximumflow, author="Wolfram Research", title="{FindMaximumFlow}", year="2015", howpublished="\url{https://reference.wolfram.com/language/ref/FindMaximumFlow.html}", note=[Accessed: 08-October-2026]}
BibLaTeX
@online{reference.wolfram_2026_findmaximumflow, organization={Wolfram Research}, title={FindMaximumFlow}, year={2015}, url={https://reference.wolfram.com/language/ref/FindMaximumFlow.html}, note=[Accessed: 08-October-2026]}