FindMaximumFlow

FindMaximumFlow[g,s,t]

グラフ g の始点 s と目的頂点 t の間の最大フローを求める.

FindMaximumFlow[m,s,t]

辺容量行列 m のグラフ内の頂点指標 st の間の最大フローを求める.

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では,ある辺の辺容量は,可能な場合はグラフ gEdgeCapacityで,その他の場合は1であるとみなされる.
  • デフォルト設定のVertexCapacity->Automaticでは,頂点の頂点容量は,可能な場合はグラフ gVertexCapacityで,その他の場合はInfinityであるとみなされる.
  • FindMaximumFlowは,無向グラフ,有向グラフ,多重グラフ,混合グラフに使うことができる.

例題

すべて開くすべて閉じる

  (2)

グラフ中の2つの頂点間の最大フローを求める:

"s""t"の間の最大フローを求める:

フローをハイライトする:

スコープ  (10)

FindMaximumFlowは無向グラフに使うことができる:

有向グラフに使う:

多重グラフ:

混合グラフ:

辺の容量を示したグラフ:

規則を使ってグラフを指定する:

辺の容量行列の最大フローを計算する:

複数の始点と複数の終点間の最大フローを計算する:

最大フローの特性を求める:

最大フローの値:

フローに貢献している辺のリスト:

辺のフローの行列:

フローを表示する:

FindMaximumFlowは大きいグラフに使うことができる:

オプション  (2)

EdgeCapacity  (1)

デフォルトで,辺の容量は,指定可能な場合はそのEdgeCapacity特性であり,指定可能ではない場合は1であるとみなされる:

EdgeCapacity->capacities を使って辺の容量を設定する:

VertexCapacity  (1)

デフォルトで,頂点の容量は,指定可能な場合はそのVertexCapacity特性であり,指定可能ではない場合はInfinityであるとみなされる:

VertexCapacity->capacities を使って頂点の容量を設定する:

アプリケーション  (7)

輸送網  (3)

1940年におけるソビエトの鉄道網に基づいて,ソビエト連邦西部を発して東欧の目的地に輸送可能な貨物の最大量を求める:

指標を与えられた都市{1,5,6,7,9,12,13,18}から{44,40}までの最大フローの値:

フローを可視化する:

1日の客車数を含む,カナダの6都市を結ぶ鉄道網:

バンクーバーからウィニペグまで運行することができる最大客車数を求める:

都市間の客車数:

客車のフローを示す:

以下の指定された容量の地域的な電力配電回路網で,ワンチャイに送ることができる最大電力を求める:

フローを示す:

ネットワークの接続性  (2)

アメリカ中西部のある都市の,社会福祉問題に関心がある10の組織間の情報のフローを表す有向ネットワーク.COUNからCOMMへの可能な最大情報フローを求める:

最大フローを求め,そのグラフを描く:

ある町の住人は7人で,クラブが4つと政党が3つある.住民はそれぞれ少なくとも1つのクラブの会員である.各人が所属できる政党は厳密に1つだけである.均衡のとれた議会では,各クラブが議会でそのクラブを代表する人物を1名指名しなければならないが,その場合,政党 に所属する議員数が最大で 人でなければならない.均衡のとれた議会にすることが可能かどうかを求める:

最大フローの値が4に等しいので,この町の議会は均衡がとれていると言える:

フローグラフは,可能な均衡のとれた議会構成とするためのメンバーが R1R2R4R5であることを示している:

割当て問題  (2)

ある企業にはさまざまな種類の仕事がある.被雇用者は数ある仕事の複数に適しているが,各人は一度に一つの仕事にしか行うことができない.一度に行える仕事の最大数を求める:

すべての被雇用者からすべてのタスクへの最大フローによって,同時に行える仕事の数が得られる:

可能な仕事の割当てを示す:

ある女性の集団があり,各人が特定のグループの男性を好むとする.好みにあった場合にのみマッチングするとして最大マッチを求める:

各人を1回だけマッチングしたいので,頂点の容量を1に制限する:

可能なマッチング:

特性と関係  (5)

内点については,入フローの合計は出フローの合計と等しい:

内点の入フロー:

内点の出フロー:

自己ループのあるグラフは単純グラフとして扱われる:

2つの頂点の辺連結度は最大フローの値に等しい:

2つの頂点間の頂点連結度はFindMaximumFlowで求めることができる:

Wolfram Research (2012), FindMaximumFlow, Wolfram言語関数, https://reference.wolfram.com/language/ref/FindMaximumFlow.html (2015年に更新).

テキスト

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_2024_findmaximumflow, author="Wolfram Research", title="{FindMaximumFlow}", year="2015", howpublished="\url{https://reference.wolfram.com/language/ref/FindMaximumFlow.html}", note=[Accessed: 22-November-2024 ]}

BibLaTeX

@online{reference.wolfram_2024_findmaximumflow, organization={Wolfram Research}, title={FindMaximumFlow}, year={2015}, url={https://reference.wolfram.com/language/ref/FindMaximumFlow.html}, note=[Accessed: 22-November-2024 ]}