ネットワークフロー問題ネットワークフロー問題（ネットワークフローもんだい、英: network flow problems）とは、組合せ最適化の（グラフの辺上に容量の値が課せられた）フローネットワークにおいて各頂点において入るフローと出るフローが同じ量でかつすべての辺において流れるフローがその辺の容量以下となるようなフローを求める問題である[1]。 ネットワークフロー問題における特筆すべき問題としては以下のものが挙げられる:
最大流最小カット定理では最大流問題における最大流の値がフローネットワークの頂点のに分割を考え、そらを結ぶ辺の重みの和が最小となる頂点分割を求める最小カット問題の重みの和の値と一致することが知られている。また、近似最大流最小カット定理は、最大流最小カット定理を多品種流問題に拡張した定理である。無向フローネットワークでのゴモリー・フー木は任意の二つの頂点における最小カットを得ることができる。 フローを構築的に求めるアルゴリズムとしては以下のものが知られている:
これらに挙げられる問題以外を解く方法としては線形計画問題として定式化を与えることが多くの場合で可能であり、それにより線形計画問題を解く最適化ソルバにより解くことが可能である。 脚注関連項目 |
Index:
pl ar de en es fr it arz nl ja pt ceb sv uk vi war zh ru af ast az bg zh-min-nan bn be ca cs cy da et el eo eu fa gl ko hi hr id he ka la lv lt hu mk ms min no nn ce uz kk ro simple sk sl sr sh fi ta tt th tg azb tr ur zh-yue hy my ace als am an hyw ban bjn map-bms ba be-tarask bcl bpy bar bs br cv nv eml hif fo fy ga gd gu hak ha hsb io ig ilo ia ie os is jv kn ht ku ckb ky mrj lb lij li lmo mai mg ml zh-classical mr xmf mzn cdo mn nap new ne frr oc mhr or as pa pnb ps pms nds crh qu sa sah sco sq scn si sd szl su sw tl shn te bug vec vo wa wuu yi yo diq bat-smg zu lad kbd ang smn ab roa-rup frp arc gn av ay bh bi bo bxr cbk-zam co za dag ary se pdc dv dsb myv ext fur gv gag inh ki glk gan guw xal haw rw kbp pam csb kw km kv koi kg gom ks gcr lo lbe ltg lez nia ln jbo lg mt mi tw mwl mdf mnw nqo fj nah na nds-nl nrm nov om pi pag pap pfl pcd krc kaa ksh rm rue sm sat sc trv stq nso sn cu so srn kab roa-tara tet tpi to chr tum tk tyv udm ug vep fiu-vro vls wo xh zea ty ak bm ch ny ee ff got iu ik kl mad cr pih ami pwn pnt dz rmy rn sg st tn ss ti din chy ts kcg ve
Portal di Ensiklopedia Dunia
