2024-03-29T08:25:04Z
https://niigata-u.repo.nii.ac.jp/oai
oai:niigata-u.repo.nii.ac.jp:00003310
2022-12-15T03:36:26Z
423:424:425
453:454
容量空間における最適勢力圏図
容量空間における最適勢力圏図
An Optimal Territory Map on a Capacity Space
田村, 裕
仙石, 正和
篠田, 庄司
copyright(C)1989 IEICE
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|)で可能となるネットワークを容量空間から構成する.
電子情報通信学会
1989-08
jpn
journal article
http://hdl.handle.net/10191/22435
https://niigata-u.repo.nii.ac.jp/records/3310
http://www.ieice.org/jpn/trans_online/
AN10013345
09135707
電子情報通信学会論文誌. A, 基礎・境界
電子情報通信学会論文誌. A, 基礎・境界
J72-A
8
1327
1335
https://niigata-u.repo.nii.ac.jp/record/3310/files/J72-A_8_1327-1335.pdf
application/pdf
717.9 kB
2019-07-30