2グラフの最遠共通木対とその能動回路区間解析への応用(グラフ,ネットワークとアルゴリズムおよび一般)

概要

論文の詳細を見る
2グラフ(電流グラフと電圧グラフ)の最遠共通木対は、グラフの基本分割と関連してよく知られている単一グラフにおける最遠木対の拡張であり、共通に持つ木枝の数が最小になるような共通木の対である。単一グラフの場合と異なり、このような共通木対を求める多項式オーダーのアルゴリズムは知られていないが、異なった2つのグラフのそれぞれにおける2本の木の計4本の木を取り扱う必要があるので、どのようなアルゴリズムでもかなり複雑であることが予想される。ここでは、能動回路から導かれる2グラフが並列枝や直列枝を持つことに着目した簡単な発見的アルゴリズムを示している。その基本的方策は、グラフに含まれる並列枝あるいは直列枝を求め、そのそれぞれの枝を共通木対のそれぞれに割り当て、並列枝あるいは直列枝がないときは、枝と分割して並列枝あるいは直列枝を作ろうというものである。さらに、能動回路の区間解析に2グラフ法を適用し、アルゴリズムによって得られた共通木対を用いた解析結果例を示す。
社団法人電子情報通信学会の論文
1994-11-17