(57)【要約】【課題】  ネットワークの分割により得られたグループごとの空間的なまとまりを考慮しつつ、グループ間を流れるトラヒック量を小さく抑える。【解決手段】  ネットワーク情報入力手段１１は、分割対象となるネットワークに関するネットワーク情報をネットワーク分割装置１０に入力し、極大木抽出手段１２は、そのネットワーク情報からネットワークの極大木を抽出し、基底算出手段１３は、極大木のエッジからネットワークに属するコサイクル空間の基底を算出し、カットセット算出手段１４は分割されたネットワーク間を流れるトラヒック量が閾値を超えないように基底を組み合わせることで、ネットワークを分割するカットセットを算出し、凸関数計算手段１５は、そのカットセットから作られるノードの部分集合の評価関数となる凸関数を計算し、分割されたネットワークのクラス間分散でカットセットをソートする。【選択図】      図１
2006180126.tif 000002
【特許請求の範囲】
【請求項１】
分割されたネットワーク間を流れるトラヒック量に基づいて、前記ネットワークの分割の候補を抽出する分割候補抽出手段と、
前記分割候補抽出手段にて抽出された前記ネットワークの分割の候補に対して、前記ネットワークを構成するノードの空間的な配置を評価するノード配置評価手段とを備えることを特徴とするネットワーク分割装置。
【請求項２】
前記分割候補抽出手段は、
前記ネットワークを構成するノード間の接続関係および前記ノード間の各エッジを流れるトラヒック量に関する情報を入力するネットワーク情報入力手段と、
前記ノード間の接続関係に基づいて、前記ネットワークの極大木を抽出する極大木抽出手段と、
前記極大木のエッジから前記ネットワークに属するコサイクル空間の基底を算出する基底算出手段と、
前記トラヒック量が閾値を超えないように前記基底を組み合わせることで、前記ネットワークを分割するカットセットを算出するカットセット算出手段とを備え、
前記ノード配置評価手段は、
前記カットセット算出手段にて算出されたカットセットから作られるノードの部分集合の評価関数となる凸関数を計算する凸関数計算手段を備えることを特徴とする請求項１記載のネットワーク分割装置。
【請求項３】
前記極大木抽出手段は、
前記ネットワークの極大木のうち、エッジのトラヒック量の合計が最大となる極大木を選別する極大木選別手段を備えることを特徴とする請求項２記載のネットワーク分割装置。
【請求項４】
前記カットセット算出手段は、
極大木のエッジのトラヒック量の大きさ及び基底の持つエッジの数のいずれか少なくとも一方に基づいて、基底を組み合わせる順序を設定する組み合わせ順序設定手段を備えることを特徴とする請求項２または３記載のネットワーク分割装置。
【請求項５】
前記カットセット算出手段は、
基底を組み合わせる順序に従って基底のすべての組み合わせを表現する木を生成する木生成手段と、
組み合わされた基底が持つ極大木のエッジのトラヒック量の合計に基づいて、前記木の枝刈りを行う枝刈り手段を備えることを特徴とする請求項２から４のいずれか１項記載のネットワーク分割装置。
【請求項６】
前記枝刈り手段は、基底を組み合わせる順序に従って基底を組み合わせた時に、組み合わされた基底が持つ極大木のエッジのトラヒック量の合計が閾値を超えた場合、その基底より下位の基底の組み合わせを省略することを特徴とする請求項５記載のネットワーク分割装置。
【請求項７】
前記カットセット算出手段は、
基底を組み合わせる順序に従って基底のすべての組み合わせを表現する木を生成する木生成手段と、
組み合わされた基底が持つすべてのエッジのトラヒック量の合計およびそれ以降に組み合わされる基底が持つサブエッジの有無またはトラヒック量に基づいて、前記木の枝刈りを行う枝刈り手段を備えることを特徴とする請求項２から４のいずれか１項記載のネットワーク分割装置。
【請求項８】
前記枝刈り手段は、基底を組み合わせる順序に従って基底を組み合わせた時に、組み合わされた基底が持つすべてのエッジのトラヒック量の合計が、それ以降に組み合わされる基底との対称差により消去される可能性のあるサブエッジのトラヒック量を減算しても閾値を超える場合、その基底より下位の基底の組み合わせを省略することを特徴とする請求項７記載のネットワーク分割装置。
【請求項９】
前記ノードの部分集合の評価関数としてノードの数を用いることを特徴とする請求項２から８のいずれか１項記載のネットワーク分割装置。
【請求項１０】
ネットワークを構成するノード間の接続関係および前記ノード間の各エッジを流れるトラヒック量に関する情報を取得するステップと、
前記ノード間の接続関係に基づいて、前記ネットワークの極大木を抽出するステップと、
前記極大木のエッジから前記ネットワークに属するコサイクル空間の基底を算出するステップと、
前記トラヒック量が閾値を超えないように前記基底を組み合わせることで、前記ネットワークを分割するカットセットを算出するステップと、
前記カットセット算出手段にて算出されたカットセットから作られるノードの部分集合の評価関数となる凸関数を計算するステップと、
前記評価関数にて得られた評価結果に基づいて、前記ネットワークの分割位置を提示するステップとをコンピュータに実行させることを特徴とするネットワーク分割プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明はネットワーク分割装置およびネットワーク分割プログラムに関し、特に、ネットワークを構成するノードが空間的にまとまって配置されるようにネットワークを分割する方法に適用して好適なものである。
【背景技術】
【０００２】
ネットワークが膨大になると、ネットワークの容量やセキュリティなどの観点から、ネットワークを分割して管理することが行われている。ここで、従来のネットワーク分割方法では、ネットワークの分割により得られたグループ間を流れるトラヒック量が多いと、管理コストが増大することから、グループ間を流れるトラヒック量が最小となる分割を行うグラフ分割問題に落とす手法がよく用いられている。例えば、非特許文献１には、遺伝的アルゴリズムを解いてネットワークを分割する手法が開示されている。また、非特許文献２には、グループのサイズを制限した時のグラフ分割問題を解く手法が開示されている。
【非特許文献１】野崎、河合「ＷＡＣＮｅｔにおけるネットワーク分割手法の性能評価」、電子情報通信学会総合大会  Ｂ−７−４９、１９９３−３
【非特許文献２】Ｂ．Ｗ．Ｋｅｒｎｉｇｈａｎ“Ａｎ  Ｅｆｆｉｃｉｅｎｔ  Ｈｅｕｒｉｓｔｉｃ  Ｐｒｏｃｅｄｕｒｅ  ｆｏｒ  Ｐａｒｔｉｔｉｏｎｉｎｇ  Ｇｒａｐｈ”、Ｂｅｌｌ  Ｓｙｓｔｅｍ  Ｔｅｃｈｎｉｃａｌ  Ｊｏｕｒｎａｌ，ｖｏｌ．４９，ｐｐ２９１−３０７，１９７０
【発明の開示】
【発明が解決しようとする課題】
【０００３】
しかしながら、従来のネットワーク分割方法では、ネットワークの分割により得られたグループ間を流れるトラヒック量を小さく抑えることはできるが、空間的に離れたノードが同一のグループに入るようにネットワークが分割されることがあり、管理コストが却って増大することがあるという問題があった。
そこで、本発明の目的は、グループごとの空間的なまとまりを考慮しつつ、グループ間を流れるトラヒック量を小さく抑えることが可能なネットワーク分割装置およびネットワーク分割プログラムを提供することである。
【課題を解決するための手段】
【０００４】
上述した課題を解決するために、請求項１記載のネットワーク分割装置によれば、分割されたネットワーク間を流れるトラヒック量に基づいて、前記ネットワークの分割の候補を抽出する分割候補抽出手段と、前記分割候補抽出手段にて抽出された前記ネットワークの分割の候補に対して、前記ネットワークを構成するノードの空間的な配置を評価するノード配置評価手段とを備えることを特徴とする。
【０００５】
これにより、分割されたネットワーク間を流れるトラヒック量が小さくなるようにネットワークの分割の候補を抽出してから、ネットワークを構成するノードの空間的な配置を評価することができる。このため、ノードの空間的なまとまりを考慮しつつ、分割されたネットワーク間を流れるトラヒック量を小さく抑えることが可能となり、ネットワークの管理コストを減らすことができる。
【０００６】
また、請求項２記載のネットワーク分割装置によれば、前記分割候補抽出手段は、前記ネットワークを構成するノード間の接続関係および前記ノード間の各エッジを流れるトラヒック量に関する情報を入力するネットワーク情報入力手段と、前記ノード間の接続関係に基づいて、前記ネットワークの極大木を抽出する極大木抽出手段と、前記極大木のエッジから前記ネットワークに属するコサイクル空間の基底を算出する基底算出手段と、前記トラヒック量が閾値を超えないように前記基底を組み合わせることで、前記ネットワークを分割するカットセットを算出するカットセット算出手段とを備え、前記ノード配置評価手段は、前記カットセット算出手段にて算出されたカットセットから作られるノードの部分集合の評価関数となる凸関数を計算する凸関数計算手段を備えることを特徴とする。
【０００７】
これにより、基底を組み合わせることで、ネットワークを分割するすべてのカットセットを求めることが可能となり、トラヒック量が閾値を超えないようなネットワークの分割の候補を漏れなく抽出することができる。このため、トラヒック量が閾値を超えないようなネットワークのすべての分割の候補に対して、ノードの空間的な配置を評価することが可能となり、ノードの空間的な配置が評価される分割の候補を絞り込むことを可能として、凸関数の計算量を減少させることが可能となるとともに、トラヒック量が閾値を超えないようなネットワークの分割の候補がノードの空間的な配置の評価対象からこぼれ落ちることを防止することができ、ネットワークの分割精度の劣化を抑制しつつ、ネットワークの分割を効率よく行うことが可能となる。
【０００８】
また、極大木のエッジを１本だけ含むカットセットを抽出することにより、基底を求めることが可能となることから、ネットワークの極大木を抽出することで、基底を求めるために必要な計算量の増大を抑制することが可能となるとともに、枝刈りを効率よく行うことができる。
また、請求項３記載のネットワーク分割装置によれば、前記極大木抽出手段は、前記ネットワークの極大木のうち、エッジのトラヒック量の合計が最大となる極大木を選別する極大木選別手段を備えることを特徴とする。
【０００９】
これにより、極大木のエッジのトラヒック量を大きくすることが可能となり、基底を順次組み合わせてカットセットを求める際に、トラヒック量の大きな極大木のエッジをより早い段階でカットセットに組み込ませることが可能となる。このため、基底の組み合わせ回数がより少ない段階で、トラヒック量が閾値を越えるカットセットを求めることができ、カットセットを求める際のそれ以降の基底の組み合わせを不要とすることができる。この結果、トラヒック量が閾値を超えないようなネットワークの分割の候補を漏らすことなく、ネットワークの分割の候補を求めるための計算量を減らすことができ、ネットワークの分割精度の劣化を抑制しつつ、ネットワークの分割を効率よく行うことが可能となる。
【００１０】
また、請求項４記載のネットワーク分割装置によれば、前記カットセット算出手段は、極大木のエッジのトラヒック量の大きさ及び基底の持つエッジの数のいずれか少なくとも一方に基づいて、基底を組み合わせる順序を設定する組み合わせ順序設定手段を備えることを特徴とする。
ここで、極大木のエッジのトラヒック量の大きさに基づいて基底を組み合わせる順序を設定することにより、トラヒック量の大きな極大木のエッジをより早い段階でカットセットに組み込ませることが可能となる。このため、基底の組み合わせ回数がより少ない段階で、トラヒック量が閾値を越えるとともに、それ以降の基底との対称差によりトラヒック量が閾値以下となることのないカットセットを求めることができ、カットセットを求める際のそれ以降の基底の組み合わせを不要とすることができる。この結果、トラヒック量が閾値を超えないようなネットワークの分割の候補を漏らすことなく、ネットワークの分割の候補を求めるための計算量を減らすことができ、ネットワークの分割精度の劣化を抑制しつつ、ネットワークの分割を効率よく行うことが可能となる。
【００１１】
また、基底の持つエッジの数に基づいて基底を組み合わせる順序を設定することにより、組み合わされる可能性のあるサブエッジをより早い段階で減少させることが可能となり、基底の組み合わせ回数がより少ない段階で、基底の対称差により消去される可能性のあるサブエッジの数を減らすことができる。このため、トラヒック量が閾値を越えるカットセットが得られた時に、それ以降のどのような基底を組み合わせてもトラヒック量が閾値以下となることのないカットセットを、基底の組み合わせ回数がより少ない段階で特定することが可能となり、カットセットを求める際のそれ以降の基底の組み合わせを不要とすることができる。この結果、トラヒック量が閾値を超えないようなネットワークの分割の候補を網羅しつつ、ネットワークの分割の候補を求めるための計算量を減らすことができ、ネットワークの分割精度の劣化を抑制しつつ、ネットワークの分割を効率よく行うことが可能となる。
【００１２】
また、請求項５記載のネットワーク分割装置によれば、前記カットセット算出手段は、基底を組み合わせる順序に従って基底のすべての組み合わせを表現する木を生成する木生成手段と、組み合わされた基底が持つ極大木のエッジのトラヒック量の合計に基づいて、前記木の枝刈りを行う枝刈り手段を備えることを特徴とする。
【００１３】
これにより、基底のすべての組み合わせを網羅しつつ、トラヒック量の大きな極大木のエッジをより早い段階でカットセットに組み込ませることが可能となり、基底の組み合わせ回数がより少ない段階で、トラヒック量が閾値を越えるとともに、それ以降の基底の対称差よりトラヒック量が閾値以下となることのないカットセットを求めることができる。このため、トラヒック量が閾値を越えないようなカットセットを求める際に、トラヒック量が閾値を越えないようなカットセットを漏らすことなく、枝刈りされた基底の組み合わせを不要とすることが可能となるとともに、トラヒック量が閾値を超えないようなネットワークの分割の候補がノードの空間的な配置の評価対象からこぼれ落ちることを防止することができ、ネットワークの分割精度の劣化を抑制しつつ、ネットワークの分割を効率よく行うことが可能となる。
【００１４】
また、請求項６記載のネットワーク分割装置によれば、前記枝刈り手段は、基底を組み合わせる順序に従って基底を組み合わせた時に、組み合わされた基底が持つ極大木のエッジのトラヒック量の合計が閾値を超えた場合、その基底より下位の基底の組み合わせを省略することを特徴とする。
これにより、組み合わされた基底が持つ極大木のエッジのトラヒック量の合計に基づいて枝刈りを行うことができ、トラヒック量が閾値を超えないようなカットセットを求めるために必要な時間を短縮することができる。
【００１５】
また、請求項７記載のネットワーク分割装置によれば、前記カットセット算出手段は、基底を組み合わせる順序に従って基底のすべての組み合わせを表現する木を生成する木生成手段と、組み合わされた基底が持つすべてのエッジのトラヒック量の合計およびそれ以降に組み合わされる基底が持つサブエッジの有無またはトラヒック量に基づいて、前記木の枝刈りを行う枝刈り手段を備えることを特徴とする。
【００１６】
これにより、基底のすべての組み合わせを網羅しつつ、組み合わされる可能性のあるサブエッジをより早い段階で減少させることが可能となり、基底の組み合わせ回数がより少ない段階で、トラヒック量が閾値を越えるカットセットを求めることができる。このため、カットセットを求める際のそれ以降の基底の組み合わせを不要とすることが可能となるとともに、トラヒック量が閾値を超えないようなネットワークの分割の候補がノードの空間的な配置の評価対象からこぼれ落ちることを防止することができ、ネットワークの分割精度の劣化を抑制しつつ、ネットワークの分割を効率よく行うことが可能となる。
【００１７】
また、請求項８記載のネットワーク分割装置によれば、前記枝刈り手段は、基底を組み合わせる順序に従って基底を組み合わせた時に、組み合わされた基底が持つすべてのエッジのトラヒック量の合計が、それ以降に組み合わされる基底との対称差により消去される可能性のあるサブエッジのトラヒック量を減算しても閾値を超える場合、その基底より下位の基底の組み合わせを省略することを特徴とする。
これにより、組み合わされた基底が持つすべてのエッジのトラヒック量の合計およびそれ以降に組み合わされる基底が持つサブエッジのトラヒック量に基づいて枝刈りを行うことができ、トラヒック量が閾値を超えないようなカットセットを求めるために必要な時間を短縮することができる。
【００１８】
また、請求項９記載のネットワーク分割装置によれば、前記ノードの部分集合の評価関数としてノードの数を用いることを特徴とする。
これにより、ネットワークの分割で得られた各グループのノードの数の差を小さくすることができ、結果としてトータルの管理コストを下げることができる。
【００１９】
また、請求項１０記載のネットワーク分割プログラムによれば、ネットワークを構成するノード間の接続関係および前記ノード間の各エッジを流れるトラヒック量に関する情報を取得するステップと、前記ノード間の接続関係に基づいて、前記ネットワークの極大木を抽出するステップと、前記極大木のエッジから前記ネットワークに属するコサイクル空間の基底を算出するステップと、前記トラヒック量が閾値を超えないように前記基底を組み合わせることで、前記ネットワークを分割するカットセットを算出するステップと、前記カットセット算出手段にて算出されたカットセットから作られるノードの部分集合の評価関数となる凸関数を計算するステップと、前記評価関数にて得られた評価結果に基づいて、前記ネットワークの分割位置を提示するステップとをコンピュータに実行させることを特徴とする。
【００２０】
これにより、トラヒック量が閾値を超えないようなネットワークの分割の候補を漏らすことなく、ノードの空間的な配置が評価される分割の候補を絞り込むことが可能となる。このため、ノードの空間的なまとまりを考慮しつつ、分割されたネットワーク間を流れるトラヒック量を小さく抑えることが可能となるとともに、ノードの空間的なまとまりを考慮してネットワークを分割した場合においても、計算量の増大を抑制することができる。
【発明の効果】
【００２１】
以上説明したように、本発明によれば、分割されたネットワーク間を流れるトラヒック量が小さくなるようにネットワークの分割の候補を抽出してから、ネットワークを構成するノードの空間的な配置を評価することにより、ノードの空間的なまとまりを考慮しつつ、分割されたネットワーク間を流れるトラヒック量を小さく抑えることが可能となり、ネットワークの管理コストを減らすことができる。
【発明を実施するための最良の形態】
【００２２】
以下、本発明の実施形態に係るネットワーク分割装置およびその方法について図面を参照しながら説明する。
図１は、本発明の一実施形態に係るネットワーク分割装置の概略構成を示す機能ブロック図である。
図１において、ネットワーク分割装置１０は、分割されたネットワーク間を流れるトラヒック量に基づいてネットワークの分割の候補を抽出し、抽出されたネットワークの分割の候補に対して、ネットワークを構成するノードの空間的な配置を評価することができる。ここで、ネットワーク分割装置１０には、ネットワーク情報入力手段１１、極大木抽出手段１２、基底算出手段１３、カットセット算出手段１４および凸関数計算手段１５が設けられている。
【００２３】
ネットワーク情報入力手段１１は、ネットワークを構成するノード間の接続関係およびノード間の各エッジを流れるトラヒック量に関する情報を入力する。なお、ネットワークとしては、例えば、ＩＰ通信を行う公衆通信網を用いることができ、インターネットであってもよい。また、企業間の専用通信網であっても、公衆通信網であってもよいが、高信頼性とセキュリティとを備えた専用通信を提供できるＩＰ−ＶＰＮ（Ｉｎｔｅｒｎｅｔ  Ｐｒｏｔｏｃｏｌ−Ｖｉｒｔｕａｌ  Ｐｒｉｖａｔｅ  Ｎｅｔｗｏｒｋ）のようなインターネットであってもよい。また、ノードは通信の起点や終点や中継点となるもので、ノードとしては、例えば、計算機や移動端末やルータなどを挙げることができる。また、エッジはノード間の結ぶリンクとなるもので、エッジとしては、例えば、光ファイバや同軸ケーブルなどの通信媒体や、無線インターフェースを用いた無線チャンネルなどを挙げることができる。なお、各ノードには、その空間的な位置を特定するための座標を付与することができ、エッジの両端に接続されたノードを指定することで各エッジを特定することができる。
【００２４】
極大木抽出手段１２は、ノード間の接続関係に基づいて、ネットワークの極大木を抽出する。なお、極大木とは、分割前のネットワークのノードを網羅するようにエッジが選択されたループのないネットワークである。ここで、極大木抽出手段１２には極大木選別手段１２ａが設けられ、極大木選別手段１２ａは、ネットワークの極大木のうち、エッジのトラヒック量の合計が最大となる極大木を選別することができる。
【００２５】
基底算出手段１３は、極大木のエッジからネットワークに属するコサイクル空間の基底を算出する。なお、コサイクル空間とは、あるネットワークのカットセット同士の対称差が演算として閉じている空間である。ここで、カットセットとは、ネットワークを構成するノードが２つのグループに分かれるようにネットワークを分割した時に、そのグループ間にまたがるすべてのエッジの集合である。カットセット同士の対称差とは、排他的論理和に対応するもので、２つのカットセットを組み合わせて１つのカットセットを形成する時に、２つのカットセットに共通に含まれるエッジを互いに打ち消しながら、２つのカットセットのいずれか一方に含まれるエッジのみを抽出することである。すなわち、偶数本のカットセットで切られるエッジは消去され、奇数本のカットセットで切られるエッジのみが残される。基底とは、基本となるカットセットを組み合わせることで、ネットワークを分割するすべてのカットセットを表現できるカットセットであり、極大木のエッジを１本だけ含むカットセットは基底となることができる。
【００２６】
カットセット算出手段１４は、分割されたネットワーク間を流れるトラヒック量が閾値を超えないように基底を組み合わせることで、ネットワークを分割するカットセットを算出する。ここで、カットセット算出手段１４には、組み合わせ順序設定手段１４ａ、木生成手段１４ｂおよび枝刈り手段１４ｃが設けられている。
【００２７】
この組み合わせ順序設定手段１４ａは、極大木のエッジのトラヒック量の大きさ及び基底の持つエッジの数のいずれか少なくとも一方に基づいて、基底を組み合わせる順序を設定することができる。木生成手段１４ｂは、基底を組み合わせる順序に従って基底のすべての組み合わせを表現する木を生成することができる。枝刈り手段１４ｃは、組み合わされた基底が持つ極大木のエッジのトラヒック量の合計に基づいて木の枝刈りを行ったり、組み合わされた基底が持つすべてのエッジのトラヒック量の合計およびそれ以降に組み合わされる基底が持つサブエッジの有無またはトラヒック量に基づいて木の枝刈りを行ったりすることができる。なお、サブエッジとは、極大木に含まれないエッジである。
【００２８】
例えば、枝刈り手段１４ｃは、基底を組み合わせる順序に従って基底を組み合わせた時に、組み合わされた基底が持つ極大木のエッジのトラヒック量の合計が閾値を超えた場合、その基底より下位の基底の組み合わせを省略することができる。また、例えば、枝刈り手段１４ｃは、基底を組み合わせる順序に従って基底を組み合わせた時に、組み合わされた基底が持つすべてのエッジのトラヒック量の合計が、それ以降に組み合わされる基底との対称差により消去される可能性のあるサブエッジのトラヒック量を減算しても閾値を超える場合、その基底より下位の基底の組み合わせを省略することができる。
【００２９】
凸関数計算手段１５は、カットセット算出手段１４にて算出されたカットセットから作られるノードの部分集合の評価関数となる凸関数を計算する。なお、凸関数とは、ノードの部分集合とその補集合がそれぞれ空間的にまとまって配置されているかを評価する関数で、凸関数としては、例えば、クラス間分散などを挙げることができる。
図２は、本発明の一実施形態に係るネットワーク分割方法の一例を示すフローチャートである。
【００３０】
図２において、ネットワーク情報入力手段１１は、分割対象となるネットワークに関するネットワーク情報をネットワーク分割装置１０に入力する（ステップＳ１１）。ここで、ネットワーク情報としては、例えば、ネットワークを構成するノードの座標、それらのノード間に接続されたエッジの情報およびそのエッジを流れるトラヒック量に関する情報などを含むことができる。
そして、ネットワーク情報がネットワーク分割装置１０に入力されると、極大木抽出手段１２は、そのネットワーク情報からネットワークの極大木を抽出する（ステップＳ１２）。ここで、ネットワークの極大木を抽出することにより、基底を容易に求めることが可能となり、基底を求めるために必要な計算量の増大を抑制することができる。
【００３１】
なお、極大木を求める場合、エッジのトラヒック量の合計が最大となる極大木を選別することが好ましい。これにより、極大木のエッジのトラヒック量を大きくすることが可能となり、基底を順次組み合わせてカットセットを求める際に、トラヒック量の大きな極大木のエッジをより早い段階でカットセットに組み込ませることが可能となる。このため、基底の組み合わせ回数がより少ない段階で、トラヒック量が閾値を越えるカットセットを求めることができ、カットセットを求める際のそれ以降の基底の組み合わせを不要とすることができる。この結果、トラヒック量が閾値を超えないようなネットワークの分割の候補を漏らすことなく、ネットワークの分割の候補を求めるための計算量を減らすことができ、ネットワークの分割精度の劣化を抑制しつつ、ネットワークの分割を効率よく行うことが可能となる。
【００３２】
次に、基底算出手段１３は、ネットワークの極大木が極大木抽出手段１２にて抽出されると、極大木のエッジからネットワークに属するコサイクル空間の基底を算出する（ステップＳ１３）。ここで、基底を算出することにより、基底となるカットセットを用いてネットワークを分割するすべてのカットセットを求めることができ、計算量の増大を抑制しつつ、ネットワークの分割の候補を漏れなく抽出することができる。
【００３３】
次に、カットセット算出手段１４は、基底算出手段１３にて基底が算出されると、分割されたネットワーク間を流れるトラヒック量が閾値を超えないように基底を組み合わせることで、ネットワークを分割するカットセットを算出する（ステップＳ１４）。なお、分割されたネットワーク間を流れるトラヒック量は、ネットワークを分割するカットセットに含まれるエッジを流れるトラヒック量の合計で表すことができる。
【００３４】
これにより、トラヒック量が閾値を超えないようなネットワークの分割の候補を漏れなく抽出することができ、トラヒック量が閾値を超えないようなネットワークのすべての分割の候補に対して、ノードの空間的な配置を評価することが可能となる。このため、ノードの空間的な配置が評価される分割の候補を絞り込むことを可能として、凸関数の計算量を減少させることが可能となるとともに、トラヒック量が閾値を超えないようなネットワークの分割の候補がノードの空間的な配置の評価対象からこぼれ落ちることを防止することができ、ネットワークの分割精度の劣化を抑制しつつ、ネットワークの分割を効率よく行うことが可能となる。
【００３５】
次に、凸関数計算手段１５は、トラヒック量が閾値を超えないようなカットセットがカットセット算出手段１４にて算出されると、そのカットセットから作られるノードの部分集合の評価関数となる凸関数を計算する（ステップＳ１５）。これにより、分割されたネットワーク間を流れるトラヒック量が小さくなるようにネットワークの分割の候補を抽出してから、ネットワークを構成するノードの空間的な配置を評価することができる。このため、ノードの空間的なまとまりを考慮しつつ、分割されたネットワーク間を流れるトラヒック量を小さく抑えることが可能となり、ネットワークの管理コストを減らすことができる。
【００３６】
そして、分割されたネットワークの凸関数が凸関数計算手段１５にて計算されると、例えば、分割されたネットワークのクラス間分散でカットセットをソートし、分割されたネットワークをランキングして提示することができる（ステップＳ１６）。
なお、ネットワーク情報入力手段１１、極大木抽出手段１２、基底算出手段１３、カットセット算出手段１４および凸関数計算手段１５は、これらの手段で行われる処理を遂行させる命令が記述されたプログラムをコンピュータに実行させることにより実現することができる。
【００３７】
そして、このプログラムをＣＤ−ＲＯＭなどの記憶媒体に記憶しておけば、その記憶媒体をコンピュータに装着し、そのプログラムをコンピュータにインストールすることにより、ネットワーク情報入力手段１１、極大木抽出手段１２、基底算出手段１３、カットセット算出手段１４および凸関数計算手段１５で行われる処理を実現することができる。また、このプログラムをインターネットを介してダウンロードすることにより、このプログラムを容易に普及させることができる。
【００３８】
また、ネットワーク情報入力手段１１、極大木抽出手段１２、基底算出手段１３、カットセット算出手段１４および凸関数計算手段１５で行われる処理を遂行させる命令が記述されたプログラムをコンピュータに実行させる場合、スタンドアロン型コンピュータで実行させるようにしてもよく、ネットワークに接続された複数のコンピュータに分散処理させるようにしてもよい。
【００３９】
図３は、本発明の一実施形態に係るネットワークの構成例を示す図である。
図３において、例えば、ネットワークは、ノードＮ１〜Ｎ７とエッジＥ１〜Ｅ９で構成され、ノードＮ２、Ｎ３間にはエッジＥ１が接続され、ノードＮ１、Ｎ３間にはエッジＥ２が接続され、ノードＮ１、Ｎ４間にはエッジＥ３が接続され、ノードＮ３、Ｎ４間にはエッジＥ４が接続され、ノードＮ３、Ｎ５間にはエッジＥ５が接続され、ノードＮ４、Ｎ５間にはエッジＥ６が接続され、ノードＮ４、Ｎ６間にはエッジＥ７が接続され、ノードＮ５、Ｎ７間にはエッジＥ８が接続され、ノードＮ６、Ｎ７間にはエッジＥ９が接続されている。ここで、エッジＥ１を流れるトラヒック量は１、エッジＥ２を流れるトラヒック量は３、エッジＥ３を流れるトラヒック量は２、エッジＥ４を流れるトラヒック量は５、エッジＥ５を流れるトラヒック量は６、エッジＥ６を流れるトラヒック量は６、エッジＥ７を流れるトラヒック量は３、エッジＥ８を流れるトラヒック量は１、エッジＥ９を流れるトラヒック量は１であるものとする。
【００４０】
図４は、図３のネットワークにおける極大木の例を示す図である。
図４（ａ）において、例えば、図３のネットワークの極大木として、エッジＥ１、Ｅ２、Ｅ５、Ｅ６、Ｅ７、Ｅ８が抽出されたものとする。ここで、これらのエッジＥ１、Ｅ２、Ｅ５、Ｅ６、Ｅ７、Ｅ８で構成されたネットワークは、図３のネットワークを構成するすべてのノードＮ１〜Ｎ７を網羅するとともに、ループになっていないので、これらのエッジＥ１、Ｅ２、Ｅ５、Ｅ６、Ｅ７、Ｅ８で構成されたネットワークは極大木を構成する。
そして、これらのエッジＥ１、Ｅ２、Ｅ５、Ｅ６、Ｅ７、Ｅ８のトラヒック量は、それぞれ１、３、６、６、１、１であるので、図４の極大木のエッジＥ１、Ｅ２、Ｅ５、Ｅ６、Ｅ７、Ｅ８のトラヒック量の合計は１８となる。
【００４１】
一方、図４（ｂ）において、例えば、エッジＥ１、Ｅ３、Ｅ４、Ｅ６、Ｅ８、Ｅ９で構成されたネットワークは、図３のネットワークを構成するすべてのノードＮ１〜Ｎ７を網羅するとともに、ループになっていないので、これらのエッジＥ１、Ｅ３、Ｅ４、Ｅ６、Ｅ８、Ｅ９で構成されたネットワークも極大木を構成することができる。
そして、これらのエッジＥ１、Ｅ３、Ｅ４、Ｅ６、Ｅ８、Ｅ９のトラヒック量は、それぞれ１、２、５、６、１、１であるので、図４の極大木のエッジＥ１、Ｅ３、Ｅ４、Ｅ６、Ｅ８、Ｅ９のトラヒック量の合計は１６となる。
【００４２】
そして、図３のネットワークのすべての極大木のエッジのトラヒック量の合計を調べ、これらの極大木のうち、エッジのトラヒック量の合計が最大となる極大木を選別することができる。例えば、図３のネットワークのすべての極大木のエッジのトラヒック量の合計を調べると、エッジＥ１、Ｅ２、Ｅ５、Ｅ６、Ｅ７、Ｅ８で構成された極大木のトラヒック量が最も大きいので、図３のネットワークの極大木として、エッジＥ１、Ｅ２、Ｅ５、Ｅ６、Ｅ７、Ｅ８で構成された極大木を選択することができる。なお、図３のネットワークのすべての極大木を調べなくても、例えば、ＫｒｕｓｋａｌのアルゴリズムやＰｒｉｍのアルゴリズムを用いてもよい。
【００４３】
図５は、図４（ａ）の極大木を設定した時の基底の例を示す図である。
図５において、カットセットｂ１は、エッジＥ２、Ｅ３にまたがることにより、ノードＮ１のグループとノードＮ２〜Ｎ７のグループとにネットワークを分割するとともに、極大木のエッジＥ２を１本だけ含むため、基底の要素となる。カットセットｂ２は、エッジＥ３、Ｅ４、Ｅ６、Ｅ９にまたがることにより、ノードＮ１〜Ｎ３、Ｎ５、Ｎ７のグループとノードＮ４、Ｎ６のグループとにネットワークを分割するとともに、極大木のエッジＥ６を１本だけ含むため、基底の要素となる。カットセットｂ３は、エッジＥ３〜Ｅ５にまたがることにより、ノードＮ１〜Ｎ３のグループとノードＮ４〜Ｎ７のグループとにネットワークを分割するとともに、極大木のエッジＥ５を１本だけ含むため、基底の要素となる。カットセットｂ４は、エッジＥ３、Ｅ４、Ｅ６、Ｅ９にまたがることにより、ノードＮ１〜Ｎ５、Ｎ７のグループとノードＮ６のグループとにネットワークを分割するとともに、極大木のエッジＥ７を１本だけ含むため、基底の要素となる。カットセットｂ５は、エッジＥ１にまたがることにより、ノードＮ１、Ｎ３〜Ｎ７のグループとノードＮ２のグループとにネットワークを分割するとともに、極大木のエッジＥ１を１本だけ含むため、基底の要素となる。カットセットｂ６は、エッジＥ８、Ｅ９にまたがることにより、ノードＮ１〜Ｎ６のグループとノードＮ７のグループとにネットワークを分割するとともに、極大木のエッジＥ８を１本だけ含むため、基底の要素となる。
【００４４】
そして、図４（ａ）の極大木には、６本のエッジＥ１、Ｅ２、Ｅ５、Ｅ６、Ｅ７、Ｅ８が含まれているので、これらの６個のカットセットｂ１〜ｂ６にて、図３のネットワークに属するコサイクル空間の基底を構成することができる。
そして、基底となるカットセットｂ１〜ｂ６が抽出されると、基底となるカットセットｂ１〜ｂ６を組み合わせることにより、図３のネットワークを２つに分割するすべてのカットセットを求めることができる。ここで、図１のカットセット算出手段１４は、分割されたネットワーク間を流れるトラヒック量が閾値を超えないように、基底となるカットセットｂ１〜ｂ６を組み合わせることができる。そして、基底となるカットセットｂ１〜ｂ６を組み合わせ回数がより少ない段階で、トラヒック量が閾値を超えるようなネットワークの分割が求まるように、基底となるカットセットｂ１〜ｂ６を組み合わせる順序を設定することができる。
【００４５】
例えば、図１の組み合わせ順序設定手段１４ａは、図４（ａ）の極大木のエッジＥ１、Ｅ２、Ｅ５、Ｅ６、Ｅ７、Ｅ８のトラヒック量の大きさ及び基底となるカットセットｂ１〜ｂ６の持つエッジの数のいずれか少なくとも一方に基づいて、基底を組み合わせる順序を設定することができる。
図６は、図４（ａ）の極大木に含まれるエッジのトラヒック量の大きさでソートされた基底の例を示す図である。
【００４６】
図５のカットセットｂ１〜ｂ６において、カットセットｂ１〜ｂ６にそれぞれ含まれる極大木のエッジＥ２、Ｅ６、Ｅ５、Ｅ７、Ｅ１、Ｅ８のトラヒック量はそれぞれ、３、６、６、３、１、１である。このため、極大木のエッジＥ２、Ｅ６、Ｅ５、Ｅ７、Ｅ１、Ｅ８のトラヒック量でカットセットｂ１〜ｂ６の順序を並べ替えると、図５の基底となるカットセットｂ１〜ｂ６を組み合わせる順序は、図６に示すように、ｂ１_ｍ→ｂ２_ｍ→ｂ３_ｍ→ｂ４_ｍ→ｂ５_ｍ→ｂ６_ｍとなる。
そして、カットセットｂ１_ｍ〜ｂ６_ｍを組み合わせる順序が求まると、ｂ１_ｍ→ｂ２_ｍ→ｂ３_ｍ→ｂ４_ｍ→ｂ５_ｍ→ｂ６_ｍの順序でカットセットｂ１_ｍ〜ｂ６_ｍを組み合わせることにより、トラヒック量が閾値を超えないようにネットワークを分割するカットセットをすべて求める。
【００４７】
ここで、極大木のエッジＥ１、Ｅ２、Ｅ５、Ｅ６、Ｅ７、Ｅ８のトラヒック量の大きさに基づいてカットセットｂ１_ｍ〜ｂ６_ｍを組み合わせる順序を設定することにより、トラヒック量の大きな極大木のエッジＥ１、Ｅ２、Ｅ５、Ｅ６、Ｅ７、Ｅ８をより早い段階でカットセットに組み込ませることが可能となる。このため、基底の組み合わせ回数がより少ない段階で、トラヒック量が閾値を越えるとともに、それ以降の基底の対称差よりトラヒック量が閾値以下となることのないカットセットを求めることができる。従って、トラヒック量が閾値を越えないようなカットセットを求める際に、トラヒック量が閾値を越えないようなカットセットを漏らすことなく、無駄な基底の組み合わせを不要とすることができ、トラヒック量が閾値を超えないようにネットワークを分割するカットセットを効率よく求めることができる。
【００４８】
図７は、図６の基底を組み合わせることで生成されたカットセットの例を示す図である。
図７（ａ）において、例えば、分割されたネットワーク間を流れるトラヒック量の閾値が１０に設定されているものとする。そして、カットセットｂ１_ｍとカットセットｂ２_ｍとを最初に組み合わせると、エッジＥ３、Ｅ４はカットセットｂ１_ｍ、ｂ２_ｍに共通に含まれているため、エッジＥ３、Ｅ４は消去され、エッジＥ５、Ｅ６、Ｅ９のみを含むカットセットｂ１ｂ２_ｍが生成される。
【００４９】
ここで、エッジＥ５、Ｅ６は極大木に含まれており、これらのエッジＥ５、Ｅ６のトラヒック量の合計は１２となるため、カットセットｂ１ｂ２_ｍのトラヒック量は閾値＝１０を超えている。また、基底となるカットセットｂ１_ｍ〜ｂ６_ｍには、極大木のエッジＥ６、Ｅ５、Ｅ２、Ｅ７、Ｅ１、Ｅ８がそれぞれ１本だけしか含まれていないため、カットセットｂ１ｂ２_ｍにどのようなカットセットｂ３_ｍ〜ｂ６_ｍをさらに組み合わせても、カットセットｂ１ｂ２_ｍに含まれる極大木のエッジＥ５、Ｅ６が消去されることはない。従って、カットセットｂ１ｂ２_ｍにさらにカットセットｂ３_ｍ〜ｂ６_ｍを組み合わせて新たなカットセットを生成しても、そのカットセットのトラヒック量の合計が閾値＝１０以下となることはなく、カットセットｂ１ｂ２_ｍにさらにカットセットｂ３_ｍ〜ｂ６_ｍを組み合わせる操作を省略することができる。
【００５０】
一方、図７（ｂ）に示すように、カットセットｂ１_ｍとカットセットｂ３_ｍとを最初に組み合わせると、エッジＥ３はカットセットｂ１_ｍ、ｂ３_ｍに共通に含まれているため、エッジＥ３は消去され、エッジＥ２、Ｅ４、Ｅ６、Ｅ９のみを含むカットセットｂ１ｂ３_ｍが生成される。ここで、エッジＥ２、Ｅ６は極大木に含まれており、これらのエッジＥ２、Ｅ６のトラヒック量の合計は９となるため、カットセットｂ１ｂ３_ｍのトラヒック量は閾値＝１０以下である。このため、カットセットｂ１_ｍとカットセットｂ３_ｍとを組み合わせた段階では、カットセットｂ１ｂ３_ｍにさらにカットセットｂ２_ｍ、ｂ４_ｍ〜ｂ６_ｍを組み合わせて新たなカットセットを生成すると、そのカットセットのトラヒック量の合計が閾値＝１０以下となる可能性があるので、カットセットｂ１ｂ３_ｍにさらにカットセットｂ２_ｍ、ｂ４_ｍ〜ｂ６_ｍを組み合わせる操作を行う必要がある。
【００５１】
従って、カットセットｂ１ｂ３_ｍにさらにカットセットｂ２_ｍを組み合わせて新たなカットセットを生成しても、そのカットセットのトラヒック量の合計が閾値＝１０以下となることはないにもかかわらず、カットセットｂ１_ｍとカットセットｂ３_ｍとを最初に組み合わせると、カットセットｂ１ｂ３_ｍにさらにカットセットｂ２_ｍを組み合わせる操作を行う必要があり、無駄な組み合わせ操作が発生する。
【００５２】
一方、カットセットｂ１_ｍとカットセットｂ２_ｍとを最初に組み合わせると、カットセットｂ１_ｍとカットセットｂ２_ｍとを組み合わせた段階で、それ以上カットセットｂ３_ｍ〜ｂ６_ｍをカットセットｂ１ｂ２_ｍに組み合わせても、トラヒック量の合計が閾値＝１０以下となる場合がないと判るので、それ以上カットセットｂ３_ｍ〜ｂ６_ｍをカットセットｂ１ｂ２_ｍに組み合わせる操作を行う必要がないと判断することができる。
【００５３】
このため、極大木のエッジＥ１、Ｅ２、Ｅ５、Ｅ６、Ｅ７、Ｅ８のトラヒック量の大きさに基づいてカットセットｂ１_ｍ〜ｂ６_ｍを組み合わせる順序を設定することにより、トラヒック量が閾値を超えないようなカットセットｂ１_ｍ〜ｂ６_ｍの組み合わせを漏らすことなく、カットセットｂ１_ｍ〜ｂ６_ｍの組み合わせ回数を減らすことができ、トラヒック量が閾値を超えないようなネットワークの分割を効率よく行うことができる。
【００５４】
図８は、図５の基底が持つエッジ数でソートされた基底の例を示す図である。
図５のカットセットｂ１〜ｂ６において、カットセットｂ１にはエッジＥ２、Ｅ３が含まれ、カットセットｂ２にはエッジＥ３、Ｅ４、Ｅ６、Ｅ９が含まれ、カットセットｂ３にはエッジＥ３〜Ｅ５が含まれ、カットセットｂ４にはエッジＥ３、Ｅ４、Ｅ６、Ｅ９が含まれ、カットセットｂ５にはエッジＥ１が含まれ、カットセットｂ６にはエッジＥ８、Ｅ９が含まれている。このため、基底となるカットセットｂ１〜ｂ６が持つエッジ数はそれぞれ２、４、３、４、１、２である。従って、カットセットｂ１〜ｂ６がそれぞれ持つエッジ数でカットセットｂ１〜ｂ６の順序を並べ替えると、図５の基底となるカットセットｂ１〜ｂ６を組み合わせる順序は、図８に示すように、ｂ１_ｓ→ｂ２_ｓ→ｂ３_ｓ→ｂ４_ｓ→ｂ５_ｓ→ｂ６_ｓとなる。
【００５５】
そして、カットセットｂ１_ｓ〜ｂ６_ｓを組み合わせる順序が求まると、ｂ１_ｓ→ｂ２_ｓ→ｂ３_ｓ→ｂ４_ｓ→ｂ５_ｓ→ｂ６_ｓの順序でカットセットｂ１_ｓ〜ｂ６_ｓを組み合わせることにより、トラヒック量が閾値を超えないようなネットワークの分割をすべて求める。
ここで、基底となるカットセットｂ１〜ｂ６の持つエッジの数に基づいてカットセットｂ１_ｓ〜ｂ６_ｓを組み合わせる順序を設定することにより、より多くのサブエッジをより早い段階でカットセットｂ１_ｓ〜ｂ６_ｓに組み込ませることが可能となり、基底の組み合わせ回数がより少ない段階で、基底の対称差により消去される可能性のあるサブエッジの数を減らすことができる。このため、トラヒック量が閾値を越えるカットセットが得られた時に、それ以降のどのような基底を組み合わせてもトラヒック量が閾値以下となることのないカットセットを、基底の組み合わせ回数がより少ない段階で特定することが可能となり、カットセットを求める際のそれ以降の基底の組み合わせを不要として、トラヒック量が閾値を超えないようなネットワークの分割を効率よく行うことができる。
【００５６】
図９は、図８の基底を組み合わせることで生成されたカットセットの例を示す図である。
図９（ａ）において、例えば、分割されたネットワーク間を流れるトラヒック量の閾値が１０に設定されているものとする。そして、カットセットｂ１_ｓとカットセットｂ２_ｓとを最初に組み合わせると、エッジＥ５、Ｅ６、Ｅ９を含むカットセットｂ１ｂ２_ｓが生成される。
【００５７】
ここで、エッジＥ５、Ｅ６、Ｅ９のトラヒック量はそれぞれ６、６、１であり、これらのエッジＥ５、Ｅ６、Ｅ９のトラヒック量の合計は１３となるため、カットセットｂ１ｂ２_ｓのトラヒック量は閾値＝１０を超えている。ここで、カットセットｂ１ｂ２_ｓには、サブエッジＥ９が含まれているため、カットセットｂ１ｂ２_ｓにさらにカットセットｂ３_ｓ〜ｂ６_ｓを組み合わせた時に、対称差の演算により消去される可能性のあるエッジはＥ９である。しかし、エッジＥ９のトラヒック量はそれぞれ１であり、カットセットｂ１ｂ２_ｓのサブエッジＥ９が消去されても、カットセットｂ１ｂ２_ｓ全体のトラヒック量が閾値＝１０以下となることはない。従って、カットセットｂ１ｂ２_ｓにさらにカットセットｂ３_ｓ〜ｂ６_ｓを組み合わせて新たなカットセットを生成しても、そのカットセットのトラヒック量の合計が閾値＝１０以下となることはなく、カットセットｂ１ｂ２_ｓにさらにカットセットｂ３_ｓ〜ｂ６_ｓを組み合わせる操作を省略することができる。
【００５８】
一方、図９（ｂ）に示すように、カットセットｂ１_ｓとカットセットｂ３_ｓとを最初に組み合わせると、エッジＥ２、Ｅ４、Ｅ６、Ｅ９を含むカットセットｂ１ｂ３_ｓが生成される。ここで、エッジＥ２、Ｅ４、Ｅ６、Ｅ９のトラヒック量はそれぞれ３、５、６、１であり、これらのエッジＥ２、Ｅ４、Ｅ６、Ｅ９のトラヒック量の合計は１５となるため、カットセットｂ１ｂ３_ｓのトラヒック量は閾値＝１０を超えている。ここで、カットセットｂ１ｂ３_ｓにはサブエッジＥ４、Ｅ９が含まれているため、カットセットｂ１ｂ３_ｓにさらにカットセットｂ２、ｂ４〜ｂ６を組み合わせた時に、対称差の演算により消去される可能性のあるエッジはＥ４、Ｅ９であるが、エッジＥ４、Ｅ９のトラヒック量はそれぞれ５、１である。このため、カットセットｂ１_ｓとカットセットｂ３_ｓとを組み合わせた段階では、カットセットｂ１ｂ３_ｓにさらにカットセットｂ２_ｓ、ｂ４_ｓ〜ｂ６_ｓを組み合わせて新たなカットセットを生成すると、そのカットセットのトラヒック量の合計が閾値＝１０以下となる可能性があるので、カットセットｂｂ３_ｓにさらにカットセットｂ２_ｓ、ｂ４_ｓ〜ｂ６_ｓを組み合わせる操作を行う必要がある。
【００５９】
従って、カットセットｂ１ｂ３_ｓにさらにカットセットｂ２_ｓを組み合わせて新たなカットセットを生成しても、そのカットセットのトラヒック量の合計が閾値＝１０以下となることはないにもかかわらず、カットセットｂ１_ｓとカットセットｂ３_ｓとを最初に組み合わせると、カットセットｂ１ｂ３_ｓにさらにカットセットｂ２_ｓを組み合わせる操作を行う必要があり、無駄な組み合わせ操作が発生する。
【００６０】
一方、カットセットｂ１_ｓとカットセットｂ２_ｓとを最初に組み合わせると、カットセットｂ１_ｓとカットセットｂ２_ｓとを組み合わせた段階で、それ以上カットセットｂ３_ｓ〜ｂ６_ｓをカットセットｂ１ｂ２_ｓに組み合わせても、トラヒック量の合計が閾値＝１０以下となる場合がないと判るので、それ以上カットセットｂ３_ｓ〜ｂ６_ｓをカットセットｂ１ｂ２_ｓに組み合わせる操作を行う必要がないと判断することができる。このため、基底となるカットセットｂ１〜ｂ６の持つエッジの数に基づいてカットセットｂ１_ｓ〜ｂ６_ｓを組み合わせる順序を設定することにより、トラヒック量が閾値を超えないようなカットセットｂ１_ｓ〜ｂ６_ｓの組み合わせを漏らすことなく、カットセットｂ１_ｓ〜ｂ６_ｓの組み合わせ回数を減らすことができ、トラヒック量が閾値を超えないようなネットワークの分割を効率よく行うことができる。
【００６１】
図１０は、図８の基底が持つエッジ数が同じものに関して、図４の極大木に含まれるエッジのトラヒック量の大きさでソートされた基底の例を示す図である。
図５のカットセットｂ１_ｓ〜ｂ６_ｓにおいて、基底となるカットセットｂ１_ｓ〜ｂ６_ｓが持つエッジ数はそれぞれ４、４、３、２、２、１である。このため、カットセットｂ１_ｓ、ｂ２_ｓが持つエッジ数はそれぞれ４で互いに等しい。また、カットセットｂ４_ｓ、ｂ５_ｓが持つエッジ数はそれぞれ２で互いに等しい。このため、エッジ数が互いに等しいカットセットｂ１_ｓ、ｂ２_ｓについて、各カットセットｂ１_ｓ、ｂ２_ｓに含まれる極大木に含まれるエッジＥ６、Ｅ５のトラヒック量の大きさでカットセットｂ１_ｓ、ｂ２_ｓを並べ替えるとともに、各カットセットｂ４_ｓ、ｂ５_ｓに含まれる極大木に含まれるエッジＥ７、Ｅ８のトラヒック量の大きさでカットセットｂ４_ｓ、ｂ５_ｓを並べ替える。この結果、図５の基底となるカットセットｂ１〜ｂ６を組み合わせる順序は、図１０に示すように、ｂ１_ｍｓ→ｂ２_ｍｓ→ｂ３_ｍｓ→ｂ４_ｍｓ→ｂ５_ｍｓ→ｂ６_ｍｓとなる。
【００６２】
図１１は、本発明の一実施形態に係る基底を組み合わせる順序の一例を示す図である。
図１１において、図１の木生成手段１４ｂは、例えば、図５のカットセットｂ１〜ｂ６をｂ１→ｂ２→ｂ３→ｂ４→ｂ５→ｂ６の順序で組み合わせるものとすると、ｂ１→ｂ２→ｂ３→ｂ４→ｂ５→ｂ６の順序で枝分かれした木を生成する。そして、左から順に深さ優先探索にてカットセットｂ１〜ｂ６を組み合わせることにより、ｂ１→ｂ２→ｂ３→ｂ４→ｂ５→ｂ６の順序で組み合わされたすべてのカットセットを生成することができる。例えば、□で示した箇所は、カットセットｂ１、ｂ３、ｂ４が組み合わされたカットセットｂ１ｂ３ｂ４、○で示した箇所は、カットセットｂ２、ｂ４、ｂ５、ｂ６が組み合わされたカットセットｂ２ｂ４ｂ５ｂ６、△で示した箇所は、カットセットｂ４のみからなるカットセットｂ４を示している。
【００６３】
図１２は、本発明の一実施形態に係る基底の組み合わせの実行結果と枝刈りの一例を示す図である。
図１２において、分割されたネットワーク間を流れるトラヒック量の閾値が１０に設定され、図５のカットセットｂ１〜ｂ６をｂ１→ｂ２→ｂ３→ｂ４→ｂ５→ｂ６の順序で組み合わせるものとする。
【００６４】
ここで、カットセットｂ２、ｂ３には極大木のエッジＥ６、Ｅ５がそれぞれ含まれ、これらのエッジＥ６、Ｅ５のトラヒック量はそれぞれ６、６である。このため、カットセットｂ２、ｂ３を組み合わせてカットセットｂ２ｂ３を生成すると、カットセットｂ２ｂ３の極大木のエッジＥ６、Ｅ５のトラヒック量の合計は１２となる。従って、カットセットｂ２ｂ３の極大木のエッジＥ６、Ｅ５のトラヒック量の合計は閾値＝１０を超え、カットセットｂ２ｂ３にカットセットｂ４、ｂ５、ｂ６をさらに組み合わせたカットセットを生成しても、そのカットセットのトラヒック量が閾値＝１０以下となることはないと判断することができる。このため、カットセットｂ２、ｂ３より下位にあるカットセットｂ４、ｂ５、ｂ６（範囲Ｒ１、Ｒ４）の枝刈りＫ１、Ｋ４を行うことができ、カットセットｂ２ｂ３にカットセットｂ４、ｂ５、ｂ６をさらに組み合わせる操作を省略することができる。
【００６５】
また、カットセットｂ１にはエッジＥ２、Ｅ３が含まれ、カットセットｂ２にはエッジＥ３、Ｅ４、Ｅ６、Ｅ９が含まれるため、カットセットｂ１、ｂ２を組み合わせると、エッジＥ２、Ｅ４、Ｅ６、Ｅ９が含まれるカットセットｂ１ｂ２が生成される。そして、エッジＥ２、Ｅ４、Ｅ６、Ｅ９のトラヒック量はそれぞれ３、５、６、１であるため、カットセットｂ１ｂ２全体のトラヒック量は１５となり、カットセットｂ１ｂ２全体のトラヒック量は閾値＝１０を超える。ここで、カットセットｂ１ｂ２にはサブエッジＥ４、Ｅ９が含まれているため、カットセットｂ１ｂ２にさらにカットセットｂ４、ｂ５、ｂ６を組み合わせた時に、対称差の演算により消去される可能性のあるエッジはＥ４、Ｅ９である。しかし、エッジＥ４はカットセットｂ４、ｂ５、ｂ６には含まれておらず、カットセットｂ１ｂ２にさらにカットセットｂ４、ｂ５、ｂ６を組み合わせても、カットセットｂ１ｂ２のサブエッジＥ４が消去されることはない。また、エッジＥ９のトラヒック量は１であり、カットセットｂ１ｂ２のサブエッジＥ９が消去されても、カットセットｂ１ｂ２全体のトラヒック量が閾値＝１０以下となることはない。
【００６６】
従って、カットセットｂ１ｂ２にカットセットｂ４、ｂ５、ｂ６をさらに組み合わせたカットセットを生成しても、そのカットセットのトラヒック量が閾値＝１０以下となることはないと判断することができる。このため、カットセットｂ１、ｂ２より下位にあるカットセットｂ４、ｂ５、ｂ６（範囲Ｒ２）の枝刈りＫ２を行うことができ、カットセットｂ１ｂ２にカットセットｂ４、ｂ５、ｂ６をさらに組み合わせる操作を省略することができる。
【００６７】
また、カットセットｂ１にはエッジＥ２、Ｅ３が含まれ、カットセットｂ３にはエッジＥ３、Ｅ４、Ｅ５が含まれるため、カットセットｂ１、ｂ３を組み合わせると、エッジＥ２、Ｅ４、Ｅ５が含まれるカットセットｂ１ｂ３が生成される。そして、エッジＥ２、Ｅ４、Ｅ５のトラヒック量はそれぞれ３、５、６であるため、カットセットｂ１ｂ３全体のトラヒック量は１４となり、カットセットｂ１ｂ３全体のトラヒック量は閾値＝１０を超える。ここで、カットセットｂ１ｂ３にはサブエッジＥ４が含まれているため、カットセットｂ１ｂ３にさらにカットセットｂ４、ｂ５、ｂ６を組み合わせた時に、対称差の演算により消去される可能性のあるエッジはＥ４である。しかし、エッジＥ４はカットセットｂ４、ｂ５、ｂ６には含まれておらず、カットセットｂ１ｂ３にさらにカットセットｂ４、ｂ５、ｂ６を組み合わせても、カットセットｂ１ｂ３のサブエッジＥ４が消去されることはない。
【００６８】
従って、カットセットｂ１ｂ３にカットセットｂ４、ｂ５、ｂ６をさらに組み合わせたカットセットを生成しても、そのカットセットのトラヒック量が閾値＝１０以下となることはないと判断することができる。このため、カットセットｂ１、ｂ３より下位にあるカットセットｂ４、ｂ５、ｂ６（範囲Ｒ３）の枝刈りＫ３を行うことができ、カットセットｂ１ｂ３にカットセットｂ４、ｂ５、ｂ６をさらに組み合わせる操作を省略することができる。
【００６９】
また、カットセットｂ２にはエッジＥ３、Ｅ４、Ｅ６、Ｅ９が含まれている。そして、エッジＥ３、Ｅ４、Ｅ６、Ｅ９のトラヒック量はそれぞれ２、５、６、１であるため、カットセットｂ２全体のトラヒック量は１４となり、カットセットｂ２全体のトラヒック量は閾値＝１０を超える。ここで、カットセットｂ２にはサブエッジＥ３、Ｅ４、Ｅ９が含まれているため、カットセットｂ２にさらにカットセットｂ４、ｂ５、ｂ６を組み合わせた時に、対称差の演算により消去される可能性のあるエッジはＥ３、Ｅ４、Ｅ９である。しかし、エッジＥ４はカットセットｂ４、ｂ５、ｂ６には含まれておらず、カットセットｂ１ｂ２にさらにカットセットｂ４、ｂ５、ｂ６を組み合わせても、カットセットｂ１ｂ２のサブエッジＥ４が消去されることはない。また、エッジＥ３、Ｅ９のトラヒック量はそれぞれ２、１であり、カットセットｂ２のサブエッジＥ３、Ｅ９が消去されても、カットセットｂ２全体のトラヒック量が閾値＝１０以下となることはない。
【００７０】
従って、カットセットｂ２にカットセットｂ４、ｂ５、ｂ６をさらに組み合わせたカットセットを生成しても、そのカットセットのトラヒック量が閾値＝１０以下となることはないと判断することができる。このため、カットセットｂ２より下位にあるカットセットｂ４、ｂ５、ｂ６（範囲Ｒ５）の枝刈りＫ５を行うことができ、カットセットｂ２にカットセットｂ４、ｂ５、ｂ６をさらに組み合わせる操作を省略することができる。
【００７１】
また、カットセットｂ３にはエッジＥ３、Ｅ４、Ｅ５が含まれている。そして、エッジＥ３、Ｅ４、Ｅ５のトラヒック量はそれぞれ２、５、６であるため、カットセットｂ３全体のトラヒック量は１３となり、カットセットｂ３全体のトラヒック量は閾値＝１０を超える。ここで、カットセットｂ３にはサブエッジＥ３、Ｅ４が含まれているため、カットセットｂ３にさらにカットセットｂ４、ｂ５、ｂ６を組み合わせた時に、対称差の演算により消去される可能性のあるエッジはＥ３、Ｅ４である。しかし、エッジＥ４はカットセットｂ４、ｂ５、ｂ６には含まれておらず、カットセットｂ３にさらにカットセットｂ４、ｂ５、ｂ６を組み合わせても、カットセットｂ３のサブエッジＥ４が消去されることはない。また、エッジＥ３のトラヒック量は２であり、カットセットｂ３のサブエッジＥ３が消去されても、カットセットｂ３全体のトラヒック量が閾値＝１０以下となることはない。
【００７２】
従って、カットセットｂ３にカットセットｂ４、ｂ５、ｂ６をさらに組み合わせたカットセットを生成しても、そのカットセットのトラヒック量が閾値＝１０以下となることはないと判断することができる。このため、カットセットｂ３より下位にあるカットセットｂ４、ｂ５、ｂ６（範囲Ｒ６）の枝刈りＫ６を行うことができ、カットセットｂ３にカットセットｂ４、ｂ５、ｂ６をさらに組み合わせる操作を省略することができる。
【００７３】
図１３は、本発明の一実施形態に係る基底を組み合わせる順序を変更した時の枝刈りの一例を示す図である。
図１３において、分割されたネットワーク間を流れるトラヒック量の閾値が１０に設定され、図５のカットセットｂ１〜ｂ６をｂ５→ｂ６→ｂ１→ｂ２→ｂ３→ｂ４の順序で組み合わせるものとする。この場合、枝刈りＫ１１を引き起こす基底の要素が木の末端の方に組み合わされる。このため、枝刈りＫ１１によりカットセットの組み合わせ操作を省略できる回数が減少することが判る。
【００７４】
例えば、カットセットｂ５にはエッジＥ１が含まれ、カットセットｂ６にはエッジＥ８、Ｅ９が含まれるため、カットセットｂ５、ｂ６を組み合わせると、エッジＥ１、Ｅ８、Ｅ９が含まれるカットセットｂ５ｂ６が生成される。そして、エッジＥ１、Ｅ８、Ｅ９のトラヒック量はそれぞれ１、１、１であるため、カットセットｂ５ｂ６全体のトラヒック量は３となり、カットセットｂ５ｂ６全体のトラヒック量は閾値＝１０以下となる。このため、カットセットｂ５ｂ６にさらにカットセットｂ１、ｂ２、ｂ３、ｂ４を組み合わせたカットセットを生成すると、そのカットセットのトラヒック量が閾値＝１０以下となる可能性があるので、カットセットｂ５ｂ６にさらにカットセットｂ１を組み合わせたカットセットｂ５ｂ６ｂ１を生成する。
【００７５】
ここで、カットセットｂ１にはエッジＥ２、Ｅ３が含まれているため、カットセットｂ５ｂ６にさらにカットセットｂ１を組み合わせると、エッジＥ１、Ｅ２、Ｅ３、Ｅ８、Ｅ９が含まれるカットセットｂ５ｂ６ｂ１が生成され、そのカットセットｂ５ｂ６ｂｂ１のトラヒック量は８となる。このため、カットセットｂ５ｂ６ｂｂ１のトラヒック量は閾値＝１０以下となり、カットセットｂ５ｂ６ｂ１にさらにカットセットｂ２、ｂ３、ｂ４を組み合わせたカットセットを生成すると、そのカットセットのトラヒック量が閾値＝１０以下となる可能性があるので、カットセットｂ５ｂ６ｂ１にさらにカットセットｂ２を組み合わせたカットセットｂ５ｂ６ｂ１ｂ２を生成する。
【００７６】
ここで、カットセットｂ２にはエッジＥ３、Ｅ４、Ｅ６、Ｅ９が含まれているため、カットセットｂ５ｂ６ｂ１にさらにカットセットｂ２を組み合わせると、エッジＥ１、Ｅ２、Ｅ４、Ｅ６、Ｅ８が含まれるカットセットｂ５ｂ６ｂ１ｂ２が生成され、そのカットセットｂ５ｂ６ｂ１ｂ２のトラヒック量は１６となる。ここで、カットセットｂ５ｂ６ｂｂ１に含まれるエッジＥ１、Ｅ２、Ｅ４、Ｅ６、Ｅ８のうち、エッジＥ１、Ｅ２、Ｅ６、Ｅ８は極大木に含まれ、カットセットｂ５ｂ６ｂ１ｂ２の極大木のエッジＥ１、Ｅ２、Ｅ６、Ｅ８のトラヒック量の合計は１１となる。
【００７７】
従って、カットセットｂ５ｂ６ｂｂ１ｂ２ｂの極大木のエッジＥ１、Ｅ２、Ｅ６、Ｅ８のトラヒック量の合計は閾値＝１０を超え、カットセットｂ５ｂ６ｂ１ｂ２にカットセットｂ３、ｂ４をさらに組み合わせたカットセットを生成しても、そのカットセットのトラヒック量が閾値＝１０以下となることはないと判断することができる。このため、カットセットｂ５、ｂ６、ｂ１、ｂ２より下位にあるカットセットｂ３、ｂ４（範囲Ｒ１１）の枝刈りＫ１１を行うことができ、カットセットｂ５、ｂ６、ｂ１、ｂ２にカットセットｂ３、ｂ４をさらに組み合わせる操作を省略することができる。
【００７８】
このように、カットセットｂ１〜ｂ６を組み合わせる順序によって、枝刈りを行うことが可能なカットセットｂ１〜ｂ６の組み合わせ回数が異なることが判る。そして、カットセットｂ１〜ｂ６の組み合わせ回数が少ない段階で枝刈りが行なえるようにするためには、極大木のエッジのトラヒック量の大きさ及び基底の持つエッジの数のいずれか少なくとも一方に基づいて、基底を組み合わせる順序を設定することが好ましい。
そして、トラヒック量が閾値を超えないようなカットセットが算出されると、そのカットセットから作られるノードの部分集合の評価関数となる凸関数を計算する。ここで、凸関数としては、例えば、以下の式に示すように、クラス間分散を用いることができるなお、クラス間分散の値が大きいほど、大きく分かれたグループとみなすことができる。
【００７９】
【数１】
2006180126.tif 000003
【００８０】
ただし、Ｖはすべてのノードの集合、Ｘはノードの部分集合、Ｘのバーはノードの部分集合の補集合、ｃ（Ｘ）はＸの重心、ｄ（ｘ、ｙ）はｘとｙをノードの座標とした時のｘとｙの間の距離を表す。
なお、分割により得られたネットワークのノードのグループが大きく分かれているかを評価する場合、ノードの部分集合の評価関数としてノードの数を用いるようにしてもよい。
【実施例】
【００８１】
本発明の効果を評価するために、ランダムに作成したネットワークを用いてシミュレーションを行った。ここで、ネットワークの作成は以下のように行った。
まず、ノードとエッジの数およびトラヒック量の最大値を設定した。エッジの数は、ノードの数以上かつノードの数の１０倍以下とした。次に、６００×６００の２次元空間にノードをランダムに配置し、続いてエッジを配置した。ここで、実際のネットワークに近くなるようにするために、まずエッジの距離の合計が最小となるような極大木を作った。そして、ランダムに選んだノードが近くのノードに結ばれるように残りのエッジを配置した。最後に、トラヒック量の最大値以下になるように、各エッジのトラヒック量をランダムに設定した。
【００８２】
図１４は、本発明の評価に用いたネットワークの一例を示す図である。
図１４の例では、ノードの数を１００、エッジの数を１５０、トラヒック量の最大値を１０とした。なお、図１４のエッジ上に付されている番号はトラヒック量である。
図１５は、図１４のネットワークの分割例を示す図である。
図１５において、トラヒック量が閾値を１５とし、分割されたネットワーク間を流れるトラヒック量が閾値を超えないようにして、ネットワークを構成するノードのクラス間分散の値が最も大きくなるようなカットセットＫＳを求めた。ここで、このカットセットＫＳには、極大木のエッジＥ１１、Ｅ１２とサブエッジＥ１３、Ｅ１４が含まれている。なお、図１５の例では、分割されたネットワーク間を流れるトラヒック量が閾値＝１５を超えないカットセットを持つノードの部分集合は１０６７６通り得られた。この図１５の例では、ネットワークの分割により得られたノードのグループが空間的にまとまりを保ちながら分かれて配置されていることが判る。
【００８３】
図１６は、極大木の違いによるトラヒック量が閾値以下のカットセットの作成にかかる時間の比較例を示す図である。なお、図１６の列は、ネットワークの作成条件を示す。また、図１６の行は、ネットワークをランダムに１０回だけ作成した時に、トラヒック量が閾値以下となるカットセットを持つノードを分割するのにかかった時間をｍｓで示す。
図１６において、ノードの数を１００、エッジの数を１５０、トラヒック量の閾値を１０とした場合、エッジのトラヒック量の合計が最大となる極大木を選別した場合には、そうでない場合に比べて、トラヒック量が閾値以下となるカットセットを持つノードを分割するのにかかった時間が概ね減少することが判る。また、ノードの数を３００、エッジの数を６００、トラヒック量の閾値を１０とした場合には、エッジのトラヒック量の合計が最大となる極大木を選別した場合とそうでない場合とで、トラヒック量が閾値以下となるカットセットを持つノードを分割するのにかかった時間を一桁程度減少させることができ、ノードの数が多いと効果が大きくなることが判る。
【００８４】
また、また、ノードの数を１００、エッジの数を４００、トラヒック量の閾値を４０とした場合にも、エッジのトラヒック量の合計が最大となる極大木を選別すると、トラヒック量が閾値以下となるカットセットを持つノードを分割するのにかかった時間が減少することが判り、エッジの数が多い場合にもそれなりの効果あることが判る。
【００８５】
図１７は、極大木の違いによる基底の作成にかかる時間の比較例を示す図である。なお、図１７の例では、ネットワークの作成条件は図１６の例と同一にし、基底の作成にかかる時間をｍｓで示した。
図１７において、エッジのトラヒック量の合計が最大となる極大木を選別した場合には、そうでない場合に比べて、基底の作成にかかる時間が増大し、ノードの数が多くなると、その差は大きくなることが判る。しかし、エッジのトラヒック量の合計が最大となる極大木を選別すると、基底の作成にかかる時間が増大するが、基底の組み合わせにかかる時間がそれ以上に削減され、ネットワークの分割にかかる時間を全体として減少させることができる。
【００８６】
図１８は、基底の順序の違いによるトラヒック量が閾値以下のカットセットの作成にかかる時間の比較例を示す図である。なお、図１７の例では、ネットワークの作成条件は図１６の例と同一にし、ネットワークをランダムに１０回だけ作成した時に、トラヒック量が閾値以下となるカットセットを持つノードを分割するのにかかった時間をｍｓで示した。また、実施例１、４、７では、極大木のエッジのトラヒック量の大きさに基づいて基底を組み合わせる順序を設定し、実施例２、５、８では、基底の持つエッジの数に基づいて基底を組み合わせる順序を設定し、実施例３、６、９では、極大木のエッジのトラヒック量の大きさに基づいて基底を組み合わせる順序を設定するとともに、極大木のエッジのトラヒック量の大きさが同じものについては、基底の持つエッジの数に基づいて基底を組み合わせる順序を設定した。
【００８７】
図１８において、極大木のエッジのトラヒック量の大きさまたは基底の持つエッジの数に基づいて基底を組み合わせる順序を設定することにより、トラヒック量が閾値以下のカットセットの作成にかかる時間を削減できることが判る。また、極大木のエッジのトラヒック量の大きさおよび基底の持つエッジの数の両方に基づいて基底を組み合わせる順序を設定すると、その効果が大きいことが判る。
【産業上の利用可能性】
【００８８】
本発明は、インターネットなどのネットワークを分割して管理する方法の他、無線インターフェースを有したモバイルホスト群がローカルに一時的なネットワークを形成するアドホックネットワークの分割方法などにも利用することができる。
【図面の簡単な説明】
【００８９】
【図１】本発明の一実施形態に係るネットワーク分割装置の概略構成を示す機能ブロック図である。
【図２】本発明の一実施形態に係るネットワーク分割方法の一例を示すフローチャートである。
【図３】本発明の一実施形態に係るネットワークの構成例を示す図である。
【図４】図３のネットワークにおける極大木の例を示す図である。
【図５】図４（ａ）の極大木を設定した時の基底の例を示す図である。
【図６】図４（ａ）の極大木に含まれるエッジのトラヒック量の大きさでソートされた基底の例を示す図である。
【図７】図６の基底を組み合わせることで生成されたカットセットの例を示す図である。
【図８】図５の基底が持つエッジ数でソートされた基底の例を示す図である。
【図９】図８の基底を組み合わせることで生成されたカットセットの例を示す図である。
【図１０】図８の基底が持つエッジ数が同じものに関して、図４の極大木に含まれるエッジのトラヒック量の大きさでソートされた基底の例を示す図である。
【図１１】本発明の一実施形態に係る基底を組み合わせる順序の一例を示す図である。
【図１２】本発明の一実施形態に係る基底の組み合わせの実行結果と枝刈りの一例を示す図である。
【図１３】本発明の一実施形態に係る基底を組み合わせる順序を変更した時の枝刈りの一例を示す図である。
【図１４】本発明の評価に用いたネットワークの一例を示す図である。
【図１５】図１４のネットワークの分割例を示す図である。
【図１６】極大木の違いによるトラヒック量が閾値以下のカットセットの作成にかかる時間の比較例を示す図である。
【図１７】極大木の違いによる基底の作成にかかる時間の比較例を示す図である。
【図１８】基底の順序の違いによるトラヒック量が閾値以下のカットセットの作成にかかる時間の比較例を示す図である。
【符号の説明】
【００９０】
１０  ネットワーク分割装置
１１  ネットワーク情報入力手段
１２  極大木抽出手段
１２ａ  極大木選別手段
１３  基底算出手段
１４  カットセット算出手段
１４ａ  組み合わせ順序設定手段
１４ｂ  木生成手段
１４ｃ  枝刈り手段
１５  凸関数計算手段
Ｎ１〜Ｎ７  ノード
Ｅ１〜Ｅ９  エッジ
ｂ１〜ｂ６、ｂ１_ｍ〜ｂ６_ｍ、ｂ１ｂ３ｂ５_ｍ、ｂ２ｂ６_ｍ、ｂ１_ｓ〜ｂ６_ｓ、ｂ１_ｍｓ〜ｂ６_ｍｓ  カットセット
【図１】
2006180126.tif 000004
【図２】
2006180126.tif 000005
【図３】
2006180126.tif 000006
【図４】
2006180126.tif 000007
【図５】
2006180126.tif 000008
【図６】
2006180126.tif 000009
【図７】
2006180126.tif 000010
【図８】
2006180126.tif 000011
【図９】
2006180126.tif 000012
【図１０】
2006180126.tif 000013
【図１１】
2006180126.tif 000014
【図１２】
2006180126.tif 000015
【図１３】
2006180126.tif 000016
【図１４】
2006180126.tif 000017
【図１５】
2006180126.tif 000018
【図１６】
2006180126.tif 000019
【図１７】
2006180126.tif 000020
【図１８】
2006180126.tif 000021