ネットワーク理論（読み）ネットワークりろん（英語表記）network theory

改訂新版　世界大百科事典

ネットワーク理論 (ネットワークりろん)
network theory

いくつかの頂点とそれらを結ぶ辺の集合から成る図形をグラフという。グラフ構造を有するシステムにおいて，グラフの頂点および辺に対応する要素を流れるものの流れに注目するとき，グラフを特にネットワークと呼ぶ。ネットワーク上の流れ（フロー）をいろいろな条件および評価尺度の下で，最大または最小化するものを求める問題を一般にネットワークフロー問題といい，ネットワーク理論ではそのような問題を考察の対象としている。

　ネットワーク理論の現在における応用範囲は広く，道路網，鉄道網などの交通網や電気回路網，通信網などの工学の諸分野におけるいろいろな問題の分析をはじめとして，社会学，経済学，心理学などの社会科学，人文科学の諸分野におけるネットワーク型モデル分析にまで及んでいる。電気回路網においては，ネットワークの辺に対してそれぞれの素子を流れる電流，電圧を対応させることができるし，交通網においては道路網，鉄道網およびそれらを通過する車両や乗客，貨物の量をそれぞれの辺に対応させることができる。また行動科学，社会心理学などの分野では，いろいろな状態あるいはそれぞれの集団の構成員をネットワークの頂点で表し，それらの間の因果関係，相互関係などを辺で表し，状態あるいは構成員の間のコミュニケーションの程度，影響の度合を定量化した上で，それぞれの辺に対応づけることができる。

　ネットワークを構成する辺が方向性をもつ場合，つまり辺上のフローが一方向のみに限定される場合，そのようなネットワークを有向ネットワークと呼ぶのに対して，そうでない場合には無向ネットワークと呼ぶ。代表的なネットワークフロー問題は，有向あるいは無向のネットワークにおいて，それぞれの辺を流れるフローの最大値（辺の容量という）が与えられている時，ネットワークの一つの頂点sから別の頂点tへの流れの量（フロー値という）を最大にするという問題である。この問題はネットワーク理論の発展の基礎となった問題であって，1956年にフォードL.R.FordとフルカーソンD.R.Fulkersonの2人がsからtへの最大フロー値を与える最大フロー最小カット定理とそれを解く簡単なアルゴリズムとしてのラベリング法を提起することによって，それに対する解答を与えた。

　ネットワークにおける頂点の集合を二つの集合S，Tに分割して頂点s，tがそれぞれS，Tに含まれるようにしたとき，SからTに向かう辺の集合をカットと呼び，そのカットに含まれる辺の容量の和をカット容量という。フォード=フルカーソンの最大フロー最小カット定理は，与えられたネットワークにおける頂点sからtへの最大フロー値がカット容量の最小値に等しいことを主張している。またラベリング法は連結した辺をたどりながらsからtに至る経路でフロー値を増加させることができるものを探し，その経路に沿って，できるだけ多くのものを流すことを繰り返すことによってsからtへの最大フローを求めようとするものである。

　有向または無向のネットワークのそれぞれの辺に対して，容量と同時にその辺上の単位量のフローに対する費用が与えられているとする。頂点sからtへのフロー値がある値に等しいようなフローのうちで，総費用が最小となるものを求める問題が最小費用フロー問題である。解法としては線形計画法の解法である単体法，双対法，主・双対法などにもとづいたものが代表的である。特に主・双対法はsからtへのフロー値を0の状態から出発して，単位量を最小の費用で流すことのできるようなsからtへの経路を求め，その経路上にできるだけ多くを流すことを繰り返しながら，求めるフロー値における最小費用フローを得る方法である。

　ヒッチコック型輸送問題をはじめとするある種の輸送問題，PERT（パート）などの日程計画法，あるいはスケジューリング理論の問題などは最小費用フロー問題と同じである。線形計画問題として定式化できる一般的な問題の中でもかなり多くの種類の問題が，最小費用フロー問題として定式化できるので，最小費用フロー問題はネットワーク理論のいろいろな問題の中でもかなり広い応用範囲を有する。

　上に述べた問題では，すべて1種類のものの流れのみに注目してきた。それに対してネットワーク上の何種類かの異なるものの流れを同時に考慮し，それぞれの辺における各種のフローの値の和が容量を越えないようなフローのうちで，各種のフロー値の和を最大にするものを求める問題を多品種フロー問題という。多品種フロー問題は1品種フロー問題と比べて解くのが難しいが，おもな解法としては大規模な線形計画問題を解くのに用いるダンツィグ=ウルフの分割法を用いたものなどがある。

　2品種フロー問題は二つの頂点の組s₁，s₂とt₁，t₂に対して，s₁からt₁への第1種のフロー値とs₂からt₂への第2種のフロー値の総和をそれぞれの辺の容量に関する制約の下で最大にするという問題である。無向ネットワークにおける2品種フロー問題では，1品種フロー問題の場合の最大フロー最小カット定理に相当する定理が成立することから，簡単な解法アルゴリズムが得られる。しかしながら3品種以上のフロー問題では，そのような定理が成立しないために効率的な解法は得られていない。

　実際上の問題の中には，多品種ネットワークフロー問題として定式化できる問題が非常に多い。ネットワークフロー問題は，ほとんどの場合に線形計画問題として定式化できることから，線形計画法によって解くことができるわけであるが，1品種フローの場合などは，線形計画問題の係数行列の有する構造的特殊性によって非常に容易に解くことができる。それに対して一般の多品種フロー問題では，そのような特殊性がないことが解法上の難しい点である。一般の多品種フロー問題に対する効率的な解法アルゴリズムを得ることは，ネットワーク理論における現在の主要な研究課題の一つである。
執筆者：大山 達雄

出典　株式会社平凡社「改訂新版　世界大百科事典」