ネットワーク流

ネットワーク流のグラフでのモデル化には、いくつかの要素を付加する必要がある。ソース(湧出点)とシンク(吸収点)と呼ばれる特殊な２点である(ソースとシンクがそれぞれ１つずつの場合もあれば、これらが複数の場合もある)。また、グラフは重み付き有向グラフであるが、エッジには容量と流量が設定される。エッジには流量の上限が存在し、それが容量である。グラフ全体が表現しているネットワーク全体については、総流量という値が存在する。その総流量の最大値を求めるのが、ネットワーク流問題と呼ばれる問題である。エッジに容量・流量以外の値(長さやコスト)を持たせることも可能である。ＡＲＧで言えば、個々の染色体が作るＡＲＧでなく、ハプロタイプで表現される染色体集合についてのＡＲＧを考えた場合、流量の概念が発生する。

• マッチング(ノードが２グループに分けられるときに、それぞれのグループに属するノードの間にペアをつくる)は、補助ノードの追加によりネットワーク流の問題に変換できる