容量空間における最適勢力圏図

裕 田村, 正和 仙石, 庄司 篠田 · Institutional Repositories DataBase (IRDB) · 1989

Vを点といわれる要素からなる空でない集合とし,容量関数といわれるV×VからR^^-_+への関数γが定義されているとき,(V;γ)を容量空間という.また,母点集合といわれるVの部分集合C(要素を母点という)が指定されているものとする.和集合がVとなるVの部分集合族M={T(c)|c∈C}の各部分集合T(c)が互いに素で,母点cを含むが他の母点を含まなければT(c)をcの勢力圏といい,Mを(V;γ)の勢力圏図という.各母点cの勢力圏T(c)に対してf(T(c))をcとT(c)の各点vとの容量(γ(c,v))の総和とする.勢力圏図Mに対してF(M)をf(T(c))の緩和としたとき,最大のF(M)をとる勢力圏図を最適勢力圏図という.本論文では,容量空間における最適勢力圏図の構成と母点集合の変化に伴う最適勢力圏図の修正について考察し,2点間の最大流量を容量関数とする無向ネットワークNにおいてはO(knm log n)の手間で最適勢力圏図を構成できることを示す.但し,k,n,mはそれぞれCの要素数,Nの点数,Nの枝数を表す.また非母点の母点への変更やその逆の場合の最適勢力圏図の修正がO(log |V|)で可能となるネットワークを容量空間から構成する.

Cited by 0 works.

Authors