(57)【要約】      （修正有）【課題】現実的な経路や、通信容量を考慮した上で、通信網の信頼性を簡略した手順で効率的に計算する。【解決手段】各通信網構成要素とその故障確率、経路、通信容量を予め記憶（１１）し、任意の経路集合の内、安全条件１（当該経路集合により所定の通信容量が確保），２（当該経路集合の各経路が正常な場合に、当該経路集合に含まれない経路が正常に機能するという現象が発生しない），３（当該経路集合が完全条件１，２を満足する部分集合を含まない）を満足する経路集合を求め、拡張タイセット条件１（全ての通信網構成要素が正常であれば、しきい値以上の通信容量を確保できる）と２（通信網構成要素が一つでも故障すればしきい値以上の通信容量が確保できない）を満足する通信網構成要素の集合（拡張タイセット）を生成し、少なくとも一つの拡張タイセットに含まれる全通信網構成要素が正常に機能する確率を、所定以上の通信容量が確保される確率とする。【選択図】図１１
2008124875.tif 000002
【特許請求の範囲】
【請求項１】
プログラムされたコンピュータにより通信網の信頼性評価を行う通信網信頼性計算装置であって、
通信網を構成する各通信網構成要素に予め付与された識別情報と各通信網構成要素に予め設定された故障確率、および、予め定められた各通信網構成要素の組み合わせからなる通信経路の識別情報と当該通信経路に含まれる各通信網構成要素の識別情報とを対応付けた集合情報、ならびに、予め、正常に機能している通信網構成要素からなる通信経路で送信される情報の量（通信容量）を記憶する第１の記憶手段と、
全ての通信経路からなる集合の部分集合（経路集合）の一つ一つについて、
上記第１の記憶手段に記憶した上記通信容量を参照して、当該経路集合に含まれる通信経路によって所定の通信容量が確保されること（完全条件１）の確認と、
当該経路集合を構成する通信経路が正常であった場合に、当該経路集合に含まれない通信経路が正常に機能するという現象が発生しないこと（完全条件２）の確認、および、
当該経路集合が、完全条件１および完全条件２を満足する真の部分集合を含まないこと（完全条件３）の確認を行い、
上記完全条件１，２，３を満足する経路集合を特定して第２の記憶手段に記憶し、
該第２の記憶手段に記憶した経路集合に含まれる通信経路を構成する通信網構成要素を上記第１の記憶手段を参照して特定し、特定した通信網構成要素から、下記の第１，第２の条件を満足する通信網構成要素の集合（拡張タイセット）を全て生成して
第３の記憶手段に格納する拡張タイセット生成手段と、
上記第１の記憶手段から上記第３の記憶手段に格納した拡張タイセットに含まれる通信網構成要素に対して予め設定された故障確率を読み出し、読み出した故障確率を用いて、少なくとも一つの拡張タイセットに含まれる全ての通信網構成要素が正常に機能する確率を求める信頼性計算実行手段と、
該信頼性計算実行手段が求めた確率を、当該通信網において上記しきい値以上の通信容量が確保される確率として出力する出力手段と
を有することを特徴とする通信網信頼性計算装置。
第１の条件：当該拡張タイセットに含まれる全ての通信網構成要素が正常であれば、通信網において、しきい値以上の通信容量を確保することができる。
第２の条件：当該拡張タイセットに含まれる通信網構成要素が一つでも故障すれば、通信網において、しきい値以上の通信容量を確保することができない。
【請求項２】
請求項１に記載の通信網信頼性計算装置であって、
上記拡張タイセット生成手段は、
各経路集合について上記完全条件１，２，３を確認する際、当該経路集合に含まれる通信経路の数の少ない経路集合から確認を開始し、完全条件１，２，３の条件を満足しなかったとしても、完全条件３を満足する経路集合については、当該経路集合が含む通信経路の識別情報を記憶しておき、当該経路集合が含む通信経路の数を逐次増やして上記完全条件１，２，３を確認することを特徴とする通信網信頼性計算装置。
【請求項３】
プログラムされたコンピュータにより通信網の信頼性評価を行う通信網信頼性計算方法であって、
通信網を構成する各通信網構成要素に予め付与された識別情報と各通信網構成要素に予め設定された故障確率、および、予め定められた各通信網構成要素の組み合わせからなる通信経路の識別情報と当該通信経路に含まれる各通信網構成要素の識別情報とを対応付けた集合情報、ならびに、予め、正常に機能している通信網構成要素からなる通信経路で送信される情報の量（通信容量）を第１の記憶手段に記憶する第１の手順と、
全ての通信経路からなる集合の部分集合（経路集合）の一つ一つについて、
上記第１の記憶手段に記憶した上記通信容量を参照して、当該経路集合に含まれる通信経路によって所定の通信容量が確保されること（完全条件１）の確認と、
当該経路集合を構成する通信経路が正常であった場合に、当該経路集合に含まれない通信経路が正常に機能するという現象が発生しないこと（完全条件２）の確認、および、
当該経路集合が、完全条件１および完全条件２を満足する真の部分集合を含まないこと（完全条件３）の確認を行い、
上記完全条件１，２，３を満足する経路集合を特定して第２の記憶手段に記憶し、
該第２の記憶手段に記憶した経路集合に含まれる通信経路を構成する通信網構成要素を上記第１の記憶手段を参照して特定し、特定した通信網構成要素から、下記の第１，第２の条件を満足する通信網構成要素の集合（拡張タイセット）を全て生成して
第３の記憶手段に格納する第２の手順と、
上記第１の記憶手段から上記第３の記憶手段に格納した拡張タイセットに含まれる通信網構成要素に対して予め設定された故障確率を読み出し、読み出した故障確率を用いて、少なくとも一つの拡張タイセットに含まれる全ての通信網構成要素が正常に機能する確率を求める第３の手順と、
該第３の手順で求めた確率を、当該通信網において上記しきい値以上の通信容量が確保される確率として出力する第４の手順と
を有することを特徴とする通信網信頼性計算方法。
第１の条件：当該拡張タイセットに含まれる全ての通信網構成要素が正常であれば、通信網において、しきい値以上の通信容量を確保することができる。
第２の条件：当該拡張タイセットに含まれる通信網構成要素が一つでも故障すれば、通信網において、しきい値以上の通信容量を確保することができない。
【請求項４】
請求項３に記載の通信網信頼性計算方法であって、
上記第２の手順は、
各経路集合について上記完全条件１，２，３を確認する際、当該経路集合に含まれる通信経路の数の少ない経路集合から確認を開始し、完全条件１，２，３の条件を満足しなかったとしても、完全条件３を満足する経路集合については、当該経路集合が含む通信経路の識別情報を記憶しておき、当該経路集合が含む通信経路の数を逐次増やして上記完全条件１，２，３を確認する手順を有することを特徴とする通信網信頼性計算方法。
【請求項５】
コンピュータに、請求項３もしくは請求項４のいずれかに記載の通信網信頼性計算方法における各手順を実行させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、通信網の信頼性を高速計算する技術に関するものである。更に具体的に述べれば、通信網を構成する通信網構成要素（交換装置、伝送装置、ケーブル等）と、通信網構成要素からなる通信経路（以下、単に「経路」とも記載）、正常に機能する経路によって確保される通信容量、各構成要素の故障確率が知られているときに、当該通信網の通信網構成要素間に通信網が正常に機能しているとみなすしきい値以上の通信容量を伝送することができる確率を高速に計算する技術に関するものである。
【背景技術】
【０００２】
通信網の信頼性とは、通信が安定して行われる度合いまたは性質を表す。通信網をどう構成するかによって、通信網の信頼性は大きく異なったものになる。以下、図１〜図７に示す通信網構成例を用いて説明する。
【０００３】
例えば、二つの交換装置の間を一つの経路で結ぶ場合（図１参照）と二つの経路で結ぶ場合（図２参照）では、二つの経路のうち一つの経路が利用できなくなっても、もう一方の経路が利用できることから、後者（図２）の通信網構成の方が高い信頼性を実現できる。
【０００４】
また、経路が二つ設定されている場合でも、その経路の関係が、通信を両方に振り分けて、片方の経路が利用できないときは、半分（５０％）の通信量のみが利用可能であるのか、経路の一方が現用の経路（通常使用されている経路）であり、他方の予備の経路（現用の経路が利用不可能となった際にのみ利用する）で、現用の経路が運ぶことのできる通信容量を全て（１００％）予備の経路で代替できるのかでは、さらに信頼性は異なってくる（図３参照）。
【０００５】
さらに、通信網の構成が複雑である場合、例えば図４に示すように、経路数がより多くなった場合、信頼性の観点から、適切な網構成であるのかどうかを判断することは簡単ではない。
【０００６】
このような通信網構成の信頼性に対する適切な判断を行うためには、信頼性を数値で表すことが合理的である。すなわち、信頼性を表す数値が、通信網構成を変えることで、どのように変化するかを検証することで、想定される通信網構成の中で最も高信頼な通信網を明らかにすることができる。
【０００７】
この検証のために、図５に示すように、通信網を構成する交換装置、多重化装置などを点（ノード）で表し、ケーブル、伝送装置を線（リンク）で表して「グラフ表現」し、各ノードとリンクの故障確率が与えられたとして、指定されたノード間が連結していれば、通信網において通信可能と考え、その連結確率を計算する技術が、例えば、非特許文献１，２において提示されている。
【０００８】
しかし、このようなグラフ表現は、必ずしも実際の通信網を適切に表していない。すなわち、実際の通信網では、伝送装置、交換装置（ノード）とケーブル（リンク）の物理的な関係としては連結していても、通信できる経路をソフト的に割り当てていないと、通信できないこともある。
【０００９】
例えば、図６の通信網を図７のようにグラフ表現した場合、図７では、図中の故障が発生していても、グラフ上は連結しているが、実際には、図６に示したように通信に利用できる経路が存在しないので、２ノード間で通信を行うことができず、通信途絶が発生する。
【００１０】
また、通信網の信頼性を適切に判断するためには、当該通信網を流れる通信容量を考慮する必要があるが、従来の技術では、このような通信網を流れる通信容量を考慮していない。すなわち、通信網の故障は、故障により通信できる情報の量（通信容量）が段階的に減少するが、従来の技術では、このような故障による通信網の信頼性の劣化を評価できない。
【００１１】
【非特許文献１】Ｓ．Ｄ．Ｗａｎｇ，Ｃ．Ｈ．Ｓｕｎ，“Ｔｒａｎｓｆｏｒｍａｔｉｏｎ  ｏｆ  ｓｔａｒ−ｄｅ１ｔａ  ＆  ｄｅ１ｔａ−ｓｔａｒ  ｃｏｎｖｅｒｓｉｏｎ  ｒｅ１ｉａｂｉ１ｉｔｙ  ｎｅｔｗｏｒｋｓ”，ＩＥＥＥ  Ｔｒａｎｓ．  Ｒｅ１ｉａｂｉｌｉｔｙ，  Ｒ−４５，１９９６，ｐｐ．１２０−１２６．
【００１２】
【非特許文献２】Ｗｅｉ−Ｊｅｎｎ  Ｋｅ，  “Ｒｅ１ｉａｂｉ１ｉｔｙ  ｅｖａ１ｕａｔｉｏｎ  ｆｏｒ  ｄｉｓｔｒｉｂｕｔｅｄ  ｃｏｍｐｕｔｉｎｇ  ｎｅｔｗｏｒｋｓ  ｗｉｔｈ  ｉｍｐｅｒｆｅｃｔ  ｎｏｄｅｓ”，  ＩＥＥＥ  Ｔｒａｎｓ．Ｒｅ１ｉａｂｉｌｉｔｙ  Ｒ−４６，１９９７，ｐｐ．３４２−３４９．
【発明の開示】
【発明が解決しようとする課題】
【００１３】
解決しようとする問題点は、従来の技術では、現実的な経路や、通信容量を考慮した上で、通信網の信頼性を計算することができない点である。
【００１４】
本発明の目的は、通信網が送信できる情報量が、故障により段階的に劣化しても、あるしきい値以上の通信容量が確保される確率を導出することで、上記従来技術の課題を解決すると共に、これらの課題を、簡略した手順で効率的に解決することである。
【課題を解決するための手段】
【００１５】
上記目的を達成するため、本発明は、（１）通信網を構成する通信網構成要素（交換装置、伝送装置、ケーブル等）と、通信網構成要素からなる経路、正常に機能する経路によって確保される通信容量、各構成要素の故障確率のそれぞれが予め知られているときに、これらの情報を用いて、当該通信網の通信網構成要素間に通信網が正常に機能しているとみなすしきい値以上の通信容量を伝送することができる確率を高速に計算することにより、当該通信網の信頼性を高速計算することを特徴としている。より詳細には、通信網を構成する通信装置やケーブル等の各通信網構成要素を番号付けして記憶装置に記憶し、情報を送信する際にどの通信網構成要素を経由するかを示す通信のための１以上の経路を番号付けして記憶装置に記憶し、さらに、正常に機能している通信網構成要素から成る経路によって送信される情報の量（通信容量）および通信網構成要素の故障確率を予め記憶装置に記憶しておき、以下のようにして、通信網が故障により段階的に送信できる情報量が劣化しても、あるしきい値α以上の通信容量が確保される確率を導出する。すなわち、経路を、各経路が経由する通信網構成要素を要素とする集合とし、正常に機能する経路によって確保される通信容量、各通信網構成の故障確率に関するデータを、故障データとして記憶装置から読み出し、この故障データから、全ての経路からなる集合の部分集合（経路集合）の一つ一つについて、（イ）当該経路集合に含まれる経路によって所定の通信容量が確保されること（完全条件１）、（ロ）当該経路集合を構成する経路が正常であった場合に、当該経路集合に含まれない経路が正常に機能するという現象が発生しないこと（完全条件２）、（ハ）当該経路集合が、完全条件１および完全条件２を満足する真の部分集合を含まないこと（完全条件３）、を確認し、さらに、これらの完全条件１〜３を満足する経路集合に初等的な集合演算を施すことで、以下の（ニ）、（ホ）の条件を満足する通信網構成要素の集合（拡張タイセット）を全て生成する。（ニ）当該拡張タイセットに含まれる全ての通信網構成要素が正常であれば、通信網において、しきい値α以上の通信容量を確保することができる。（ホ）当該拡張タイセットに含まれる通信網構成要素が一つでも故障すれば、通信網において、しきい値α以上の通信容量を確保することができない。そして、少なくとも一つの拡張タイセットに含まれる全ての通信網構成要素が正常に機能する確率を、通信網において所定以上の通信容量が確保される確率として出力することを特徴とする。また、（２）上記各経路集合について（イ）（ロ）（ハ）の条件（完全条件１，２，３）を確認する際、当該経路集合に含まれる経路の数の少ない経路集合から確認を開始し、（イ）（ロ）（ハ）の条件を満足しなかったとしても、（ハ）を満足する経路集合については、当該経路集合が含む経路番号を物理媒体に保存しておき、経路集合が含む経路の数を逐次増やして（イ）（ロ）（ハ）を確認することで、確認作業の効率化を図ることを特徴とする。
【発明の効果】
【００１６】
本発明によれば、通信網の信頼性を、完全な経路集合を列挙して、そこから拡張タイセットを生成し、拡張タイセットが少なくとも一つ存在する確率として求めることができる。拡張タイセットは通信網構成要素の集まりであるが、通信網構成要素に比べて、より数の少ない経路の集まりについて完全条件１，２，３を満足するかどうかを確認することで、手順の簡略化を実現することができる。また、完全条件１，２，３を満足する経路集合を列挙するに当たり、小さな経路数の経路集合から順次経路を付加し、完全性を確認するが、それ以上経路を付加しても完全とならない経路集合を除いておくことで、手順の効率化を図っている。また、経路を付加することで完全となり得る経路集合が存在しなければ、手順を停止することで、無駄な手順実行を避けることができ、高速に完全な経路集合を列挙することができる。
【発明を実施するための最良の形態】
【００１７】
以下、図を用いて本発明を実施するための最良の形態例を説明するが、まず、上述の本発明が解決しようとする課題と、その課題を解決するための本発明の基本的な技術について詳細を説明する。
【００１８】
図８を用いて、その説明のめに必要な概念と前提を整理する。
【００１９】
通信網は、通信網構成要素（交換装置、伝送装置、ケーブル等）と経路から構成されるものとする。経路は、通信網構成要素の集まった集合と考える。
【００２０】
通信網構成要素全体の集合をＥと書き、経路全体の集合をＷと書く。この集合Ｗに属する部分集合である経路ｗ、すなわち、経路ｗ∈Ｗに対し、経路ｗに含まれる通信網構成要素の集合をν（ｗ）で表す。
【００２１】
例えば、図８の通信網構成例の場合、通信網構成要素はＥ＝｛１，２，３，４，５，６，７，８｝で、経路は経路１〜５まで割り当てられている。尚、本図８では、説明を簡単にするため、リンクのみが故障するとし、通信網構成要素をリンクのみとしている。これは、あくまで説明を容易にするためであり、本発明は、リンク以外を考慮に入れても問題なく適用できる。
【００２２】
図８の通信網において、経路は経路１〜５まで割り当てられており、それらの経路に含まれる通信網構成要素は以下の通りである。
【００２３】
ν（経路１）＝｛１，８｝、ν（経路２）＝｛１，６，７｝、ν（経路３）＝｛２，３，８｝、ν（経路４）＝｛５｝、ν（経路５）＝｛３，４，７｝
【００２４】
また、経路２〜４は現用の経路であり、経路１および経路５は予備の経路である。
【００２５】
通常、通信は現用の経路のみを用いて情報が伝送されるが、現用の経路が機能しない場合には、予備の経路が代替機能を果たす。代替機能の詳細（例えば、現用の通信容量を１００％代替するのか、半分だけ代替するのか等）は、予備の経路導入の実装に依存する。この点に関する本発明における扱いは、以下の「前提１〜７」の説明の後の「注意事項２」において説明する。
【００２６】
上述のようにＥ（通信網構成要素全体の集合），Ｗ（経路全体の集合），ν（経路ｗに含まれる通信網構成要素の集合）が定められたとき、通信網をＥ，Ｗ，νの組と考え、通信網ＮをＮ＝（Ｅ，Ｗ、ν）と書き、この通信網Ｎについて以下の「前提１〜７」を置く。
【００２７】
「前提１」：各通信網構成要素ｉ∈Ｅは、正常または故障の２つのいずれかの状態にある。
【００２８】
「前提２」：各通信網構成要素ｉ∈Ｅは、故障状態にある確率（故障確率）ｑｉが分かっている。正常である確率は「１−ｑｉ」で求められ、これをｐｉと書く。
【００２９】
「前提３」：任意の経路ｗにおいて、ν（ｗ）に含まれる通信網構成要素は、ν（ｗ）に含まれない通信網構成要素の故障発生とは確率的に独立に故障する。
【００３０】
「前提４」：経路ｗ∈Ｗが正常であるとは、経路ｗに含まれる通信網構成要素、すなわち、集合ν（ｗ）に含まれる全ての通信網構成要素が正常であることであり、集合ν（ｗ）の通信網構成要素の１つでも故障すると経路ｗは正常に機能しない。
【００３１】
「前提５」：経路全体集合Ｗの任意部分の集合ε（経路集合ε）に対し、この経路集合εに含まれる全ての経路が正常に機能したとき、経路集合εに含まれる通信網構成要素から構成される経路が決定され、この経路を利用して確保される通信容量が決まる。これをＣ０（ε）と書く。経路集合εの通信容量Ｃ０（ε）は０（ゼロ）または正の実数値である。尚、ε≠φ（空集合）とする。ε＝φのときは、通信容量Ｃ０（ε）は定義されない。
【００３２】
「前提６」：通信容量Ｃ０（ε）は以下の条件を満足する。
【００３３】
ε１とε２を経路全体集合Ｗの部分集合とするとき、ε１⊆ε２が成立するならば、Ｃ０（ε１）≦Ｃ０（ε２）が成立する。
【００３４】
この「前提６」は、正常な経路が増えたにも関わらず確保される通信容量が減るという非現実的な現象がないことを保障している。
【００３５】
「前提７」：通信網構成要素の全体集合Ｅに含まれる通信網構成要素のうち、正常である通信網構成要素の全体をＥｇ（正常集合と呼ぶ）で表し、このとき通信網Ｎが確保する通信容量をＣ（Ｎ）と書くとき、通信容量Ｃ（Ｎ）を、下記の式で定める。
【００３６】
Ｃ（Ｎ）＝Ｃ０（｛ｗ｜ｗ∈Ｗ，ν（ｗ）⊆Ｅｇ｝）
【００３７】
以下、通信網の故障に関しての「注意事項１」と「注意事項２」について説明する。
【００３８】
「注意事項１」：複数の通信装置が同一の電源から電気を供給されていたり、同一のソフトが複数の通信網装置で使用されている場合などには、同時に複数の通信網構成要素が故障することがある。
【００３９】
こうした場合、経路の定義を工夫する必要がある。例えば、図８の場合で、通信網構成要素５が故障すると、通信網構成要素７も同時に故障することが分かっているならば、通信網構成要素の集合ννの定義を以下のように書き換えることで、同時故障の評価に対応することができる。
【００４０】
ν（経路１）＝｛１，８｝、ν（経路２）＝｛１，５，６，７｝、ν（経路３）＝｛２，３，８｝、ν（経路４＝｛５｝、ν（経路５）＝｛３，４，５，７｝
【００４１】
上の定義では、経路２と経路５に含まれる通信網構成装置に、通信網構成装置５が含まれるように書き換えている。これによって、通信網構成装置５が故障すると通信網構成装置７を含む経路が同時に使用できなくなることを表現するができる。
【００４２】
「注意事項２」：「前提６」において、経路集合εの通信容量Ｃ０（ε）の値を実際に算出する手続きは、各経路の通信容量の割り当て方式や経路間の切り替え（現用の経路から予備の経路への切り替え）方式等に依存するが、ここでは、説明を簡潔にするため、これらの方式の詳細については述べず、後述の本発明の内容を具体的に説明する箇所で、簡単な例を述べるに止める。基本的に、通信容量Ｃ０（ε）が算出できるという前提で、かつ通信容量Ｃ０（ε）が「前提６」を満足すれば、本発明は利用可能である。
【００４３】
上述の「前提１」〜「前提７」の理解を容易にするために、以下、正常である通信網構成要素の全体、すなわち、正常集合Ｅｇが与えられたときの通信網Ｎの通信容量Ｃ（Ｎ）の値を算出する例を以下に示す。
【００４４】
図８に対応した以下の通信網（「通信網構成例１」）を想定する。
【００４５】
『Ｅ（構成要素全体集合）＝｛１，２，３，４，５，６，７，８｝』
【００４６】
『Ｗ（経路全体集合）＝｛経路１，経路２，経路３，経路４，経路５｝』
【００４７】
『ν（経路１）＝｛１，８｝、ν（経路２）＝｛１，６，７｝、ν（経路３）＝｛２，３，８｝、ν（経路４）＝｛５｝、ν（経路５）＝｛３，４，７｝』
【００４８】
『現用の経路である経路２，経路３，経路４の各通信容量Ｃ０：Ｃ０（経路２）＝Ｃ０（経路３）＝Ｃ０（経路４）＝１００』
【００４９】
『予備の経路である経路１，経路５の各通信容量Ｃ０：Ｃ０（経路１）＝Ｃ０（経路５）＝１００』
【００５０】
ただし、この例ではＣ０（ε）（経路集合εの通信容量）の算出は、以下の手順（「手順００〜０４」）で行う。
【００５１】
「手順００」：まず通信容量Ｃ０（ε）＝０とする。
【００５２】
「手順０１」：経路集合εが経路２または経路１を含めばＣ０（ε）＝Ｃ０（ε）＋１００とする。・・・ここでの「＝」は、コンピュータプログラミング技術に基づくものであり、「εが経路２または経路１を含めばＣ０（ε）の値に「１００」を加える」の意味である。
【００５３】
「手順０２」：経路集合εが経路３または経路５を含めばＣ０（ε）＝Ｃ０（ε）＋１００とする。
【００５４】
「手順０３」：経路集合εが経路４を含めばＣ０（ε）＝Ｃ０（ε）＋１００とする。
【００５５】
「手順０４」：終了。
【００５６】
この例における経路集合εの通信容量Ｃ０（ε）の算出は、経路集合εに含まれるそれぞれの経路が「１００」の通信容量を持ち、現用のみで「３００」の通信容量が確保されるが、経路２が利用できない場合は経路１を予備の経路として利用し、経路３が利用できない場合は経路５を予備として利用できる状況に対応している。
【００５７】
ここで、Ｅｇ（構成要素の正常集合）＝｛１，４，５，７，８｝の場合についてＣ（Ｎ）（通信網Ｎの通信容量）を求めてみる。
【００５８】
まず、通信網の想定により、「ν（経路１）＝｛１，８｝⊆Ｅｇ」、「ν（経路２）＝¬（｛１，６，７｝⊆Ｅｇ）」、「ν（経路３）＝¬（｛２，３，８｝⊆Ｅｇ）」、「ν（経路４）＝｛５｝⊆Ｅｇ」、「ν（経路５）＝¬（｛３，４，７｝⊆Ｅｇ）」となり、従って、「｛ｗ｜ｗ∈Ｗ，ν（ｗ）⊆Ｅｇ｝＝｛経路１，経路４｝」が得られる。尚、「¬」は否定を表す論理記号であり、例えば、「¬（｛１，６，７｝⊆Ｅｇ）」は｛１，６，７｝がＥｇの部分集合ではないことを表す。
【００５９】
この例における経路集合εの通信容量Ｃ０（ε）の定義により、「ε＝｛経路１，経路４｝」で、「Ｃ０（｛経路１，経路４｝）＝２００」であり、よって、「前提７」より、「Ｃ（Ｎ）＝Ｃ０（｛ｗ｜ｗ∈Ｗ，ν（ｗ）⊆Ｅｇ｝）＝Ｃ０（｛経路１，経路４｝）＝２００」となる。
【００６０】
通信網において、それぞれの通信網構成要素がそれぞれの確率に従って故障すると、Ｅｇ（正常集合）は変化し、従って、通信網が確保する通信容量Ｃ（Ｎ）＝Ｃ０（｛ｗ｜ｗ∈Ｗ，ν（ｗ）⊆Ｅｇ｝）の値は確率的に変化する。
【００６１】
当然、Ｃ（Ｎ）の値が小さくなると、確保できる通信容量が小さくなり、通信網の性能が劣化する。このような通信網の機能の劣化が発生する確率が大きくなると、信頼性が高いとは言えない。つまり、信頼性が高い通信網とは、Ｃ（Ｎ）がある一定の値以上である確率が十分に「１」に近い通信網であると言える。
【００６２】
このような観点から、通信網の信頼性を以下のように表すこととする。尚、「Ｐｒ（  ）」は「（  ）」内の事象が発生する確率を意味する。
【００６３】
通信網の信頼性＝Ｐｒ（Ｃ（Ｎ）≧α）。      ・・・ここで「α」はしきい値と呼ばれる正の実数定数である。
【００６４】
本例のシステムは、通信網構成要素の故障確率から「Ｐｒ（Ｃ（Ｎ）≧α）」、すなわち、「通信網において所定以上の通信容量が確保される確率」を効率的に求めるものであり、以下、その説明を行う。
【００６５】
通信網構成要素の全体Ｅの部分集合Ｅ０が以下の条件（「拡張タイセット条件１，２」）の両方の性質を満足するとき、Ｅ０を「拡張タイセット」と呼ぶ（注意：拡張タイセットは経路の集合ではなく、通信網構成要素の集合である）。
【００６６】
「拡張タイセット条件１」：Ｅ０＝ＥｇならばＣ（Ｎ）≧αである。すなわち、部分集合Ｅ０に含まれる全ての通信網構成要素が正常であれば、通信網において、しきい値α以上の通信容量を確保することができる。
【００６７】
「拡張タイセット条件２」：任意のｉ∈Ｅ０に対し、Ｅｇ＝Ｅ０−｛ｉ｝ならばＣ（Ｎ）＜αである（ここで、二つの集合Ｓ１とＳ２において、Ｓ１の要素のうち、Ｓ２の要素であるものを除いた集合をＳ１−Ｓ２で表す。また、｛ｉ｝は要素ｉからだけなる集合を表す）。すなわち、部分集合Ｅ０に含まれる通信網構成要素が一つでも故障すれば、通信網において、しきい値α以上の通信容量を確保することができない。
【００６８】
この「拡張タイセット」と通信網の信頼性Ｐｒ（Ｃ（Ｎ）≧α）の間には下記の式１が成り立つ。尚、この式１が成立する正当性は、後述の「正当性の説明」における「＜１＞」の箇所で説明する。
【００６９】
Ｐｒ（Ｃ（Ｎ）≧α）＝Ｐｒ（少なくとも一つの拡張タイセットに含まれる全ての要素が正常である）・・・式１
【００７０】
もし、全ての拡張タイセットが列挙できれば、それらから、上述の式１の右辺の計算を実行することは、例えば、公知文献（Ｗ．Ｇ．Ｓｃｈｎｅｅｗｅｉｓｓ，ＢＯＯＬＥＡＮ  ＦＵＮＣＴＩＯＮＳ，Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ  Ｂｅｒｌｉｎｅ  １９８９．）に記載の技術によって可能である。
【００７１】
従って、全ての拡張タイセットを列挙する技術が問題となる。以下では、全ての拡張タイセットを列挙するための技術を説明する。
【００７２】
まず、以下のように、必要な各定義を導入する。
【００７３】
定義１（「経路集合」）：通信網に定義されている経路の全経路の集合をＷとし、集合Ｗの部分集合を経路集合と呼ぶ（経路集合の要素は通信網構成要素ではなく経路である）。
【００７４】
定義２（「経路数ｊの経路集合」）：経路集合がｊ個の経路を含むとき、経路数ｊの経路集合と呼ぶ。
【００７５】
定義３（「写像ｆとｆ−１」）：「ｆ」は、通信網構成要素全体の集合Ｅの部分集合Ｘを、以下の経路集合ｆ（Ｘ）に変換する写像である。
【００７６】
ｆ（Ｘ）＝｛ｗ｜ｗ∈Ｗ，ν（ｗ）⊆Ｘ｝
【００７７】
「ｆ−１」は、集合Ｗの任意の部分集合Ａｊ＝｛ｗ１，ｗ２，・・・，ｗｊ｝（すなわち経路数がｊの経路集合）を、集合Ｅの部分集合ｆ−１（Ａｊ）に変換する写像で、以下の通りとする。
【００７８】
ｆ−１（Ａ）＝ν（ｗ１）∪ν（ｗ２）∪・・・∪ν（ｗｊ）
【００７９】
以下、図９におけるブロック図で示す以下の通信網構成例２を想定して、上述の定義１〜３の例を説明する。
【００８０】
『Ｅ（構成要素全体集合）＝｛１，２，３，４，５，６｝』
【００８１】
『Ｗ（経路全体集合）＝｛経路１，経路２，経路３，経路４｝』
【００８２】
『ν（経路１）＝｛１，３，５｝、ν（経路２）＝｛２，３，４｝、ν（経路３）＝｛１，４｝、ν（経路４）＝｛６｝』
【００８３】
『現用の経路：経路１，経路２』、『予備の経路：経路３，経路４』
【００８４】
ただし、経路集合εの通信容量Ｃ０（ε）に関しては、経路集合εが経路４を含むときは、『Ｃ０（ε）＝２００』と算出し、また、経路集合εが経路４を含まないときは、『Ｃ０（ε）＝Ｍｉｎ（経路集合εに含まれる経路数，２）×１００』と算出する（ここで、Ｍｉｎ（  ）は、（  ）内における最も小さい値を表す）。
【００８５】
このような通信網構成において、経路集合を経路数別に列挙すると以下のとおりである。
【００８６】
「経路数１」の経路集合：｛経路１｝，｛経路２｝，｛経路３｝，｛経路４｝
【００８７】
「経路数２」の経路集合：｛経路１，経路２｝，｛経路１，経路３｝，｛経路１，経路４｝，｛経路２，経路３｝，｛経路２，経路４｝，｛経路３，経路４｝
【００８８】
「経路数３」の経路集合：｛経路１，経路２，経路３｝，｛経路１，経路２，経路４｝，｛経路１，経路３，経路４｝，｛経路２，経路３，経路４｝
【００８９】
「経路数４」の経路集合：｛経路１，経路２，経路３，経路４｝
【００９０】
写像ｆと写像ｆ−１の例は以下の通りとなる。
【００９１】
通信網構成要素全体の集合Ｅの部分集合Ｘを、Ｘ＝｛１，３，４，５｝とすれば、ｆ（｛１，３，４，５｝）＝｛ｗ｜ｗ∈Ｗ，ν（ｗ）⊆｛１，３，４，５｝｝＝｛｛１，３，５｝，｛１，４｝｝＝｛経路１，経路３｝となる。
【００９２】
また、部分集合Ｘ＝｛１，２，３，４，５｝とすれば、ｆ（｛１，２，３，４，５｝＝｛ｗ｜ｗ∈Ｗ，ν（ｗ）⊆｛１，２，３，４，５｝｝＝｛｛１，３，５｝，｛２，３，４｝，｛１，４｝｝＝｛経路１，経路２，経路３｝となる。
【００９３】
また、ｆ−１（｛経路１，経路３｝）＝ν（経路１）∪ν（経路３）＝｛１，３，５｝∪｛１，４｝＝｛１，３，４，５｝」、「ｆ−１（｛経路１，経路２｝）＝ν（経路１）｝∪ν（経路２）＝｛１，３，５｝｝∪｛２，３，４｝＝｛１，２，３，４，５｝となる。
【００９４】
さらに、以下の「定義４」を導入する。
【００９５】
「定義４」（経路数ｊの完全な経路集合）：経路数ｊの経路集合Ａｊが以下の条件（「安全条件１〜３」）を満足するとき、経路集合Ａｊは完全であると言う。
【００９６】
「完全条件１」：経路集合Ａｊの通信容量Ｃ０（Ａｊ）≧α。この「完全条件１」は、経路集合Ａｊに含まれる経路によって、所定のα以上の通信容量が確保できることを意味する条件である。
【００９７】
「完全条件２」：ｆ（ｆ−１（Ａｊ））＝Ａｊ。この「完全条件２」は、経路集合Ａｊに含まれる経路をｗ１，ｗ２，・・・，ｗｊとしたとき、各経路に含まれる通信網構成要素の和集合、つまり、ν（ｗ１）∪ν（ｗ２）∪・・・∪ν（ｗｊ）が、ｗ１，ｗ２，・・・，ｗｊ以外の経路の少なくとも一つ（ｗ'と書く）についてν（ｗ'）を含む、すなわち、「ν（ｗ’）⊆ν（ｗ１）∪ν（ｗ２）∪・・・∪ν（ｗｊ）」となるような事態が起きないことを意味している（ｆとｆ−１の定義どおりの集合操作から、このことは言える。煩雑さを避けるため証明の詳細は略する）。
【００９８】
例えば、図１０のブロック図における通信網で示すように、ν（経路１）＝｛１，３，５｝，ν（経路２）＝｛２，３，４｝，ν（経路３）＝｛１，４｝のとき、ν（経路３）＝｛１，４｝⊆｛１，２，３，４，５｝＝ν（経路１）∪ν（経路２）であり、｛経路１，経路２｝は「完全条件２」を満足しない。
【００９９】
尚、この例では、経路１と経路２が正常に機能すれば、経路３も正常に機能することとなる。このように、「完全条件２」が満続されないと、経路が正常に機能する、しないについて複数の経路間で互いに影響を与える事態が発生することから、扱いが複雑になる。
【０１００】
「完全条件３」：経路集合Ａｊは、経路数がｊよりも小さい経路集合で「完全条件１」と「安全条件２」を満足する経路集合を部分集合として含まない。この「完全条件３」は、経路集合Ａｊの真の部分集合には、「完全条件１」および「安全条件２」を満足する経路集合は無いことを意味している。
【０１０１】
「α＝２００」としたときの、図１０に示す「通信網構成例２」においての、「完全条件１」、「完全条件２」、「完全条件３」に関する「例１〜３」を説明する。
【０１０２】
「例１」：経路集合Ａ２＝｛経路１，経路２｝の場合、まず、「完全条件１」に関しては、経路集合εの通信容量Ｃ０（ε）の定義より、Ｃ０（Ａ２）＝２００≧αであり、経路集合Ａ２は「完全条件１」を満たす。
【０１０３】
次に、「完全条件２」に関しては、ｆ−１（Ａ２）＝ν（経路１）∪ν（経路２）＝｛１，３，５｝∪｛２，３，４｝＝｛１，２，３，４，５｝であるので、ｆ（ｆ−１（Ａ２））＝ｆ（｛１，２，３，４，５｝）＝｛ｗ｜ｗ∈Ｗ，ν（ｗ）⊆｛１，２，３，４，５｝｝＝｛経路１，経路２，経路３｝より、ｆ（ｆ−１（Ａ２））＝｛経路１，経路２，経路３｝≠｛経路１，経路２｝＝Ａ２であるので、「完全条件２」は満足しない。
【０１０４】
そして、「完全条件３」に関しては、経路集合εの通信容量Ｃ０（ε）の定義より、Ｃ０（｛経路１｝）＜２００，Ｃ０（｛経路２｝）＜２００なので、｛経路１｝，｛経路２｝は完全ではない。すなわち、「完全条件１」を満足しない。その結果、経路集合Ａ２は、「完全条件１」と「完全条件２」を満足する経路数「１」の経路集合を含まないので、「完全条件３」を満足する。
【０１０５】
以上の「完全条件１，２，３」の３つの判定結果より、経路集合Ａ２は完全ではない。
【０１０６】
また、「例２」：経路集合Ａ２＝｛経路１，経路３｝の場合、まず、「完全条件１」に関しては、経路集合εの通信容量Ｃ０（ε）の定義より、Ｃ０（Ａ２）＝２００≧αであり、経路集合Ａ２は「完全条件１」を満たす。
【０１０７】
次に、「完全条件２」に関しては、ｆ−１（Ａ２）＝ν（経路１）∪ν（経路３）＝｛１，３，５｝∪｛１，４｝＝｛１，３，４，５｝であるので、ｆ（ｆ−１（Ａ２））＝ｆ（｛１，３，４，５｝）＝｛ｗ｜ｗ∈Ｗ，ν（ｗ）⊆｛１，３，４，５｝｝＝｛経路１，経路３｝より、ｆ（ｆ−１（Ａ２））＝｛経路１，経路３｝＝｛経路１，経路３｝＝Ａ２であるので、「完全条件２」を満足する。
【０１０８】
そして、「完全条件３」に関しては、経路集合εの通信容量Ｃ０（ε）の定義より、Ｃ０（｛経路１｝）＜２００，Ｃ０（｛経路３｝）＜２００なので、｛経路１｝，｛経路３｝は完全ではない。すなわち、「完全条件１」を満足しない。その結果、経路集合Ａ２は、「完全条件１」と「完全条件２」を満足する経路数「１」の経路集合を含まないので、「完全条件３」を満足する。
【０１０９】
以上の「完全条件１，２，３」の３つの判定結果より、経路集合Ａ２は完全である。
【０１１０】
また、「例３」：経路集合Ａ３＝｛経路１，経路２，経路３｝の場合、まず、「完全条件１」に関しては、経路集合εの通信容量Ｃ０（ε）の定義より、Ｃ０（Ａ３）＝２００≧αであり、経路集合Ａ３は「完全条件１」を満たす。
【０１１１】
次に、「完全条件２」に関しては、ｆ−１（Ａ３）＝ν（経路１）∪ν（経路２）∪ν（経路３）＝｛１，３，５｝∪｛２，３，４｝∪｛１，４｝＝｛１，２，３，４，５｝であるので、ｆ（ｆ−１（Ａ３））＝ｆ（｛１，２，３，４，５｝）＝｛ｗ｜ｗ∈Ｗ，ν（ｗ）⊆｛１，２，３，４，５｝｝＝｛経路１，経路２，経路３｝より、ｆ（ｆ−１（Ａ３））＝｛経路１，経路２，経路３｝＝｛経路１，経路２，経路３｝＝Ａ３であるので、「完全条件２」を満足する。
【０１１２】
そして、「完全条件３」に関しては、「例２」により、｛経路１，経路３｝は完全であり、従って、｛経路１，経路３｝⊆｛経路１，経路２，経路３｝＝Ａ３より、経路集合Ａ３は、経路数が「２」の完全な経路集合を含むので、「完全条件３」を満足しない。
【０１１３】
以上の「完全条件１，２，３」の３つの判定結果より、経路集合Ａ３は完全ではない。
【０１１４】
次に、以下の「性質１」が成り立つものとする。尚、この「性質１」が成立する根拠は、後述の「正当性の説明」における＜２＞の箇所で説明する。
【０１１５】
「性質１」：経路数がｊの経路集合Ａｊが完全であるとき、ｆ−１（Ａｊ）は拡張タイセットである。しかも、任意の拡張タイセットＥ０⊆Ｅに対し、必ずＥ０＝ｆ−１（Ａｊ）となる完全な経路集合Ａｊが存在する。
【０１１６】
この「性質１」の前半は、完全な経路集合ｆ−１を用いて変換すれば、それは拡張タイセットであることを意味し、後半は、全ての完全な経路集合を列挙すれば、それらをｆ−１で変換することで、全ての拡張タイセットが得られることを意味している。
【０１１７】
この「性質１」を用いれば、経路集合の一つ一つについて上述の完全条件を満足するかを確認することで、全ての拡張タイセットを列挙することができる。
【０１１８】
これは、通信網構成要素の集合Ｅの部分集合を一つ一つ吟味するのではなく、経路の全体の集合Ｗの部分集合について吟味すればよいことを意味している。
【０１１９】
通常、経路全体集合Ｗの元の個数の方が、通信網構成要素の全体集合Ｅの元の個数より少ないことから、「性質１」を用いることによって、通信網構成要素の全体集合Ｅの部分集合を一つ一つ吟味する場合に比べると、拡張タイセットの列挙に要する手間は削減される。
【０１２０】
以下では、各経路数毎の完全な経路集合の具体的な列挙技術を説明する。
【０１２１】
まず、説明のために、新たな記号（「ＥＴ（ｍ）（ｍ＝１，２，・・・）」、「ＮＥＴ（ｍ）（ｍ＝１，２，・・・）」、「ｇ（ＮＥＴ（ｍ））（ｍ＝１，２，・・・）」）を定義する。
【０１２２】
ＥＴ（ｍ）（ｍ＝１，２，・・・）：完全条件１，２，３を全て満足する経路数ｍの経路集合。
【０１２３】
ＮＥＴ（ｍ）（ｍ＝１，２，・・・）：完全条件３を満足するが、完全条件１または２を満足しない経路数ｍの経路集合。
【０１２４】
ｇ（ＮＥＴ（ｍ））（ｍ＝１，２，・・・）：以下の「式２」で定義される経路数ｍ＋１の経路集合。
【０１２５】
ｇ（ＮＥＴ（ｍ））＝｛ｘ｜ｘ⊆Ｗ，適当なｚ∈ＮＥＴ（１），ｙ∈ＮＥＴ（ｍ）が存在して、ｘ＝ｚ∪ｙ，ｘの経路数＝ｍ＋１｝      ・・・式２
【０１２６】
尚、ここで、「ｘ」，「ｙ」，「ｚ」は全て経路集合であり、また、「∈」，「⊆」，「∪」は全て、通常の集合論で用いられる記号である。
【０１２７】
図９で示した「通信網構成例２」において、ＮＥＴ（ｍ），ＮＥＴ（ｍ），ｇ（ＮＥＴ（ｍ））の要素の例を以下に示す。
【０１２８】
｛経路３｝は「完全条件１」と「完全条件３」の定義より、「完全条件３」を満足するが、「完全条件１」を満足しない。また、｛経路１，経路２｝は、「完全条件３」を満足するが、「完全条件２」を満足しない。従って、下記の通りとなる。
【０１２９】
｛経路３｝∈ＮＥＴ（１）、および、｛経路１，経路２｝∈ＮＥＴ（２）。
【０１３０】
ここで、ｚ＝｛経路３｝，ｙ＝｛経路１，経路２｝とすると、以下が成立する。    
【０１３１】
｛経路１，経路２，経路３｝＝ｚ∪ｙ
【０１３２】
｛経路１，経路２，経路３｝の経路数＝３であることから、｛経路１，経路２，経路３｝は、前述の「式２」で、ｍ＝２としたときの右辺の集合の要素が満たすべき条件を満足しており、以下の通りとなる。
【０１３３】
｛経路１，経路２，経路３｝∈ｇ（ＮＥＴ（２））
【０１３４】
次に、ＮＥＴ（ｍ），ｇ（ＮＥＴ（ｍ））を用いて、「完全条件１，２，３」を満足する全ての経路集合を全て列挙する手順を示す。
【０１３５】
「各経路数毎の完全な経路集合列挙手順」について説明する。
【０１３６】
「手順１１」：Ｗ（経路の全体集合）＝｛ｗ１，ｗ２，・・・，ｗｎ｝に関して、｛ｗ１｝，｛ｗ２｝，・・・，｛ｗｎ｝の一つ一つについて、完全条件１，２，３を満足するかどうかを確認し、完全ならばＥＴ（１）に格納する。また、完全条件３を満足するが、完全条件１または２を満足しないならば、ＮＥＴ（１）に格納する。そして「ｍ＝１」とする。
【０１３７】
「手順１２」：ＮＥＴ（ｍ）＝φならば終了。
【０１３８】
「手順１３」：ｇ（ＮＥＴ（ｍ））を生成する。尚、具体的なｇ（ＮＥＴ（ｍ））の生成手順の詳細は、後述する。
【０１３９】
「手順１４」：生成したｇ（ＮＥＴ（ｍ））に含まれる各経路集合について、完全条件１，２，３を満足するものをＥＴ（ｍ＋１）に格納する。
【０１４０】
「手順１５」：生成したｇ（ＮＥＴ（ｍ））に含まれる各経路集合について、完全条件３を満足するが完全条件１または完全条件２を満足しないものをＮＥＴ（ｍ＋１）に格納する。
【０１４１】
「手順１６」：ｍ＝ｍ＋１として手順１２に進む。
【０１４２】
上の「手順１１」〜「手順１６」によって、ＥＴ（ｍ）に、経路数ｍの全ての完全な経路集合が格納されることとなる。尚、本手順の正当性は、後述の「正当性の説明」における（ＣＣＣ）で説明する。
【０１４３】
上述の手順１１〜１６は、完全条件の確認を経路数の小さい経路集合から開始し、完全条件を全て満足するものをＥＴ（ｍ）に格納し、満足しないが、手順の後の段階で経路を加えれば、完全条件を全て満足する可能性のある経路集合をＮＥＴ（ｍ）に残しておくという考え方に基づいている。
【０１４４】
完全条件を確認した結果、手順の以後の段階で、経路を加えても、全ての完全条件を満足する可能性がない（完全条件３を満足しなければ、経路を加えても、もはや完全にならない）経路集合はそれ以降の手順において無視することで、効率化を図っている。
【０１４５】
以下、図９に示す「通信網構成２」においてα＝２００とした場合の、「手順１１」〜「手順１６」を適用した例を示す。
【０１４６】
図９における通信網構成例２では、構成要素全集合Ｅ＝｛１，２，３，４，５，６｝、経路全集号Ｗ＝｛経路１，経路２，経路３，経路４｝となり、ν（経路１）＝｛１，３，５｝，ν（経路２）＝｛２，３，４｝，ν（経路３）＝｛１，４｝，ν（経路４）＝｛４｝となり、現用の経路が経路１，経路２で、予備の経路：経路３，経路４である。
【０１４７】
また、通信網を正常と判断する通信容量のしきい値α＝２００とし、通信容量Ｃ０（ε）は、任意の経路部分集合εが経路４を含むとき、Ｃ０（ε）＝２００、集合εが経路４を含まないときＣ０（ε）＝Ｍｉｎ（εに含まれる経路数，２）×１００である。
【０１４８】
この図９に示す通信網構成例２における手順（１１〜１６）適用は以下のとおり進行する。
【０１４９】
「手順１１」：Ｃ０（｛経路１｝）＝Ｃ０（｛経路２｝）＝Ｃ０（｛経路３｝）＝１００＜αであるから、｛経路１｝，｛経路２｝，｛経路３｝は全て完全ではない。
【０１５０】
しかし、Ｃ０（｛経路４｝）＝２００≧αより、｛経路４｝は完全条件１を満足する。また、｛経路４｝が完全条件２を満足することは、ｆ（ｆ−１（｛経路４｝）＝ｆ（｛６｝）＝｛経路４｝より、確認でき、完全条件３が成立することは｛経路４｝の経路数が「１」であることから明らかである。
【０１５１】
従って、ＥＴとＮＥＴは下記の通りとなる。
【０１５２】
ＥＴ（１）＝｛｛経路４｝｝
【０１５３】
ＮＥＴ（１）＝｛｛経路１｝，｛経路２｝，｛経路３｝｝
【０１５４】
「手順１２」：ＮＥＴ（１）はφでないので手順１３に移る。
【０１５５】
「手順１３」：ｇ（ＮＥＴ（１））＝｛｛経路１，経路２｝，｛経路１，経路３｝，｛経路２、経路３｝｝となる。
【０１５６】
「手順１４」：ｇ（ＮＥＴ（１））に含まれる経路集合は、Ｃ０（｛経路１，経路２｝）＝Ｃ０（｛｛経路１，経路３｝）＝Ｃ０（｛経路２，経路３｝）＝２００≧αであることから、全て完全条件１を満足する。
【０１５７】
また、ｆ（ｆ−１（｛経路１，経路２｝））＝｛経路１，経路２，経路３｝、ｆ（ｆ−１（｛経路１，経路３｝））＝｛経路１，経路３｝、ｆ（ｆ−１（｛経路２，経路３｝））＝｛経路２，経路３｝より、｛経路１，経路３｝，｛経路２，経路３｝が完全条件２を満足する。
【０１５８】
さらに、｛経路１，経路３｝，｛経路２，経路３｝は、経路数１の完全な経路集合｛経路４｝を含まないので、完全条件３を満足する。
【０１５９】
従って、ＥＴ（２）＝｛｛経路１，経路３｝，｛経路２，経路３｝｝となる。
【０１６０】
「手順１５」：手順１４で述べたように、｛経路１，経路２｝は完全条件２を満足しないが経路集合｛経路４｝を含まず、かつ、完全条件３を満足するので、ＮＥＴ（２）＝｛｛経路１，経路２｝｝となる。
【０１６１】
「手順１６」：手順１２（手順１２’）に進む。
【０１６２】
「手順１２’」：ＮＥＴ（２）はφでないので手順１３（手順１３’）に移る。
【０１６３】
「手順１３’」：ｇ（ＮＥＴ（２））＝｛｛経路１，経路２，経路３｝｝となる。
【０１６４】
「手順１４'」：ｇ（ＮＥＴ（２））に含まれる経路集合は、｛経路１，経路２，経路３｝のみであり、これは経路数２の完全な経路集合｛経路２，経路３｝を含むので、完全条件３を満足せず、完全でない。従って、ＥＴ（３）＝φとなる。
【０１６５】
「手順１５'」：｛経路１，経路２，経路３｝は完全条件３を満足しないので、ＮＥＴ（３）＝φとなる。
【０１６６】
「手順１６'」：手順１２（手順１２’’）に進む。
【０１６７】
「手順１２’’」：ＮＥＴ（３）＝φなので、終了する。
【０１６８】
上の例では、完全な拡張タイセットは、以下のとおりに得られる。
【０１６９】
｛経路４｝，｛経路１，経路３｝，｛経路２，経路３｝
【０１７０】
次に、上述の「式（１）」の正当性の説明を「＜１＞」において、「性質１」が成立する根拠の説明を「＜２＞」において、「手順１１〜１６：各経路数毎の完全な経路集合の列挙手順」の正当性の説明を「＜３＞」において行う。
【０１７１】
尚、以下、条件１が成り立つとき条件２が成り立つならば「条件１⇒条件２」と表し、また、「条件１⇒条件２」かつ「条件２⇒条件１」が成立するとき、「条件１⇔条件２」と表す。
【０１７２】
まず、各説明に必要となる「基本的性質０〜１２」について整理する。尚、「基本的性質０」は、ｆとｆ−１の定義から導かれる性質であり、「基本的性質１」以降は、集合論に関する初等的性質である。この「基本的性質１」以降については、公知文献（『梅垣壽春、大矢雅則、垣原祐一郎：「集合・位相・距離」、共立出版（１９８７）』）に詳しいので、本稿では、基本的性質１以降の正当性の根拠は割愛する。
【０１７３】
「基本的性質０」：任意の経路集合｛ｗ１，ｗ２，・・・，ｗｓ｝について以下が成立する。
【０１７４】
ｆ（ｆ−１（｛ｗ１，ｗ２，・・・，ｗｓ｝））＝｛ｗ｜ｗ∈Ｗ，ν（ｗ）⊆ν（ｗ１）∪ν（ｗ２）∪・・・∪ν（ｗｓ）｝
【０１７５】
以下、「基本的性質０」の根拠を説明する。
【０１７６】
前述の「定義３」で示された「写像ｆ−１」の定義より、「ｆ−１（｛ｗ１，ｗ２，・・・，ｗｓ｝）＝ν（ｗ１）∪ν（ｗ２）∪・・・∪ν（ｗｓ）」である。
【０１７７】
これと、前述の「定義３」で示された「写像ｆ」の定義より、「ｆ（ｆ−１（｛ｗ１，ｗ２，・・・，ｗｓ｝））＝｛ｗ｜ｗ∈Ｗ，ν（ｗ）⊆ｆ−１（｛ｗ１，ｗ２，・・・，ｗｓ｝）｝＝｛ｗ｜ｗ∈Ｗ，ν（ｗ）⊆ν（ｗ１）∪ν（ｗ２）∪・・・∪ν（ｗｓ）｝」となる。
【０１７８】
「基本的性質１」：Ｓ，Ｄ１，Ｄ２，Ｄを集合とし、Ｄ１⊆Ｄ２⊆Ｄであるとする。さらに、ψをＳからＤの部分集合全体への写像とする。このとき、以下が成立する。
【０１７９】
｛ｘ｜ｘ∈Ｓ，ψ（ｘ）⊆Ｄ１｝⊆｛ｘ｜ｘ∈Ｓ，ψ（ｘ）⊆Ｄ２｝
【０１８０】
「基本的性質２」：任意の集合Ｓ１，Ｓ２と一つの要素からなる集合｛ｘ｝について、以下が成立する。尚、上述したように、下記の式における「¬」は否定を表す論理記号であり、例えば、「¬（ｘ∈Ｓ１）」はｘがＳ１に属さないことを表す。
【０１８１】
Ｓ１⊆Ｓ２−｛ｘ｝⇔Ｓ１⊆Ｓ２，¬（ｘ∈Ｓ１）
【０１８２】
「基本的性質３」：Ｄを任意の集合とすると、以下が成立する。
【０１８３】
｛ｘ｜ｘ∈Ｄ，条件１，条件２｝＝｛ｘ｜ｘ∈Ｄ，条件１｝∩｛ｘ｜ｘ∈Ｄ，条件２｝
【０１８４】
「基本的性質４」：ｄ個の集合Ｓ１，Ｓ２，・・・，Ｓｄと、一つの要素からなる集合｛ｘ｝があったとき、以下が成立する。
【０１８５】
¬（ｘ∈Ｓ１），¬（ｘ∈Ｓ２，）・・・，¬（ｘ∈Ｓｄ）⇔¬（ｘ∈Ｓ１∪Ｓ２∪・・・∪Ｓｄ）
【０１８６】
「基本的性質５」：任意の集合Ｓと一つの要素からなる集合｛ｘ｝について、以下が成立する。
【０１８７】
¬（ｘ∈Ｓ）⇔Ｓ＝Ｓ−｛ｘ｝
【０１８８】
「基本的性質６」：任意の集合Ｓ１，Ｓ２と一つの要素からなる集合｛ｘ｝について、以下が成立する。
【０１８９】
Ｓ１−｛ｘ｝⊆Ｓ１∪Ｓ２−｛ｘ｝
【０１９０】
「基本的性質７」：ｄ個の集合Ｓ１，Ｓ２，・・・，Ｓｄがあったとき、任意のｔ∈｛１，２，・・・ｄ｝に対し、以下が成立する。
【０１９１】
Ｓｔ⊆Ｓ１∪Ｓ２∪・・・∪Ｓｄ
【０１９２】
「基本的性質８」：ｄ個の集合Ｓ１，Ｓ２，・・・，Ｓｄと、一つの要素からなる集合｛ｘ｝があったとき、以下が成立する。
【０１９３】
ｘ∈Ｓ１∪Ｓ２∪・・・∪Ｓｄ⇔適当なＳｔ⊆｛Ｓ１，Ｓ２，・・・，Ｓｄ｝が存在しｘ∈Ｓｔとなる。
【０１９４】
「基本的性質９」：ｄ個の集合Ｓ１，Ｓ２，・・・，Ｓｄと集合Ｓがあったとき、以下が成立する。
【０１９５】
Ｓ１⊆Ｓ，Ｓ２⊆Ｓ，・・・，Ｓｄ⊆Ｓ  ⇔  Ｓ１∪Ｓ２∪・・・∪Ｓ⊆Ｓ
【０１９６】
「基本的性質１０」：ｄ個の集合Ｓ１，Ｓ２，・・・，Ｓｄについて、以下が成立する。
【０１９７】
Ｓ１⊆Ｓ１∪Ｓ２∪・・・∪Ｓｄ、
Ｓ２⊆Ｓ１∪Ｓ２∪・・・∪Ｓｄ、
・・・、
Ｓｄ⊆Ｓ１∪Ｓ２∪・・・∪Ｓｄ
【０１９８】
つまり、任意のδ∈｛１，２，・・・，ｄ｝について、Ｓδ⊆Ｓ１∪Ｓ２∪・・・∪Ｓｄが成り立つ。
【０１９９】
「基本的性質１１」：集合Ｓ１，Ｓ２について、以下が成立する。
【０２００】
Ｓ１⊆Ｓ２⇔任意のｘ∈Ｓ１についてｘ∈Ｓ２
【０２０１】
「基本的性質１２」：集合Ｓ，Ｓ１，Ｓ２について、Ｓ１⊆Ｓ２⊆Ｓが分かっているとき、以下が成立する。
【０２０２】
Ｓ１＝Ｓ２⇔ｉ０∈Ｓ２，¬（ｉ０∈Ｓ１）となるｉ０∈Ｓが存在しない。
【０２０３】
＜１＞  ：以下、前述の式１、すなわち、「Ｐｒ（Ｃ（Ｎ）≧α）＝Ｐｒ（少なくとも一つの拡張タイセットに含まれる全ての要素が正常である）」の正当性について説明する。
【０２０４】
式１の正当性を言うには、「Ｃ（Ｎ）≧α⇔少なくとも一つの拡張タイセットに含まれる全ての要素が正常である」を言えばよい。
【０２０５】
＜１−１＞  ：そこで、以下、この「Ｃ（Ｎ）≧α⇒少なくとも一つの拡張タイセットに含まれる全ての要素が正常である」の正当性を説明する。
【０２０６】
Ｃ（Ｎ）≧αが成立すれば、前述の「前提７」における定義、すなわち、Ｃ（Ｎ）＝Ｃ０（｛ｗ｜ｗ∈Ｗ，ν（ｗ）⊆Ｅｇ｝）より、Ｃ０（｛ｗ｜ｗ∈Ｗ，ν（ｗ）⊆Ｅｇ｝）≧αとなる正常集合Ｅｇ⊆Ｅが存在する（存在しなければ、Ｃ（Ｎ）＜αとなって矛盾する）。
【０２０７】
従って、集合θを、下記のように定義すると、集合θは空ではない。
【０２０８】
θ＝｛Ｅ’｜Ｅ’⊆Ｅｇ，Ｃ０（｛ｗ｜ｗ∈Ｗ，ν（ｗ）⊆Ｅ’｝）≧α｝
【０２０９】
これと、集合θが高々有限個の元しか持たないことから、集合θの元Ｅ’の中で最も要素数の少ないものがとれる。その一つをＥＭとする。
【０２１０】
このＥＭは集合θの元であるので以下の「条件１，２」が成立する。
【０２１１】
「条件１」：ＥＭ⊆Ｅｇ
【０２１２】
「条件２」：Ｃ０（｛ｗ｜ｗ∈Ｗ，ν（ｗ）⊆ＥＭ｝）≧α
【０２１３】
「条件１」と上述の「基本的性質１」より、以下が成り立つ。
【０２１４】
｛ｗ｜ｗ∈Ｗ，ν（ｗ）⊆ＥＭ｝⊆｛ｗ｜ｗ∈Ｗ，ν（ｗ）⊆Ｅｇ｝
【０２１５】
これに、前述の「前提６」を適用すると、下記の通りとなる。
【０２１６】
Ｃ０｛ｗ｜ｗ∈Ｗ，ν（ｗ）⊆ＥＭ｝≦Ｃ０｛ｗ｜ｗ∈Ｗ，ν（ｗ）⊆Ｅｇ｝
【０２１７】
この式の右辺は、前述の「前提７」（Ｃ（Ｎ）の定義）より、「Ｃ（Ｎ）」であり、このことと「条件２」より、下記の式が成り立つ。
【０２１８】
α≦Ｃ０｛ｗ｜ｗ∈Ｗ，ν（ｗ）⊆ＥＭ≦Ｃ０｛ｗ｜ｗ∈Ｗ，ν（ｗ）⊆Ｅｇ｝＝Ｃ（Ｎ）
【０２１９】
つまり、Ｃ（Ｎ）≧αとなり、『ＥＭは「拡張タイセット条件１」を満足する。』      ・・・（「事実１」）
【０２２０】
また、任意のｉ∈ＥＭに対し、Ｃ０（｛ｗ｜ｗ∈Ｗ，ν（ｗ）⊆ＥＭ−｛ｉ｝｝）＜ａとなる。
【０２２１】
なぜなら、適当なｉ０∈ＥＭが存在して、「Ｃ０（｛ｗ｜ｗ∈Ｗ，ν（ｗ）⊆ＥＭ−｛ｉ０｝｝）≧α」とすると、「ＥＭ−｛ｉ０｝⊂ＥＭ⊆Ｅｇ」より（上の二つの式が集合θの定義の｛  ｝内の条件に該当するので）、下記の通りとなり、ＥＭがθの元の中で、最も要素数が少ないことに矛盾する。
【０２２２】
ＥＭ−｛ｉ０｝∈θ＝｛Ｅ’｜Ｅ’⊆Ｅｇ，Ｃ０（｛ｗ｜ｗ∈Ｗ，ν（ｗ）⊆Ｅ'｝）≧α｝
【０２２３】
従って、この場合、Ｅｇ＝Ｅ０−｛ｉ｝ならば、下記の通りとなり、『ＥＭは「拡張タイセット条件２」を満足する』。      ・・・（「事実２」）
【０２２４】
Ｃ（Ｎ）＝Ｃ０（｛ｗ｜ｗ∈Ｗ，ν（ｗ）⊆ＥＭ−｛ｉ｝＜α
【０２２５】
前述の「事実１」および「事実２」より、ＥＭは拡張タイセットであることが言えた。
【０２２６】
ＥＭが集合θの元であることから、ＥＭ⊆Ｅｇが言えるので、拡張タイセットＥＭについて、その要素は全て、正常集合Ｅｇに含まれる。つまり、少なくとも一つの拡張タイセットＥＭの要素が、全て正常である。
【０２２７】
＜１−２＞  ：次に、「少なくとも一つの拡張タイセットに含まれる全ての要素が正常である⇒Ｃ（Ｎ）≧α」の正当性について説明する。
【０２２８】
少なくとも一つの拡張タイセットに含まれる全ての要素が正常であるならば、ある拡張タイセットＥＭ’が存在して、ＥＭ’⊆Ｅｇとなる。
【０２２９】
従って、経路ｗ∈Ｗについてν（ｗ）⊆ＥＭ’であれば、ν（ｗ）⊆ＥＭ’⊆Ｅｇとなる。
【０２３０】
従って、「基本的性質１」より、｛ｗ｜ｗ∈Ｗ，ν（ｗ）⊆ＥＭ’｝⊆｛ｗ｜ｗ∈Ｗ，ν（ｗ）⊆Ｅｇ｝が成立する。
【０２３１】
これと、前述の「前提６」から、「Ｃ０（｛ｗ｜ｗ∈Ｗ，ν（ｗ）⊆ＥＭ’｝）≦Ｃ０（｛ｗ｜ｗ∈Ｗ，ν（ｗ）⊆Ｅｇ｝）」が成立し、ＥＭ’は拡張タイセットであるから、「拡張タイセット条件１」より、下記が言える。
【０２３２】
α≦Ｃ０（｛ｗ｜ｗ∈Ｗ，ν（ｗ）⊆ＥＭ’｝）
【０２３３】
従って、α≦Ｃ０（｛ｗ｜ｗ∈Ｗ，ν（ｗ）⊆ＥＭ’｝）≦Ｃ０（｛ｗ｜ｗ∈Ｗ，ν（ｗ）⊆Ｅｇ｝）＝Ｃ（Ｎ）が示せた。
【０２３４】
＜２＞  ：次に、前述の『「性質１」の正当性』について説明する。
【０２３５】
「性質１」は以下の二つに分けられる。
【０２３６】
「性質１−１」：経路数ｊの経路集合Ａｊが、「完全条件１，２，３」を満足する⇒ｆ−１（Ａｊ）は拡張タイセットである。
【０２３７】
「性質１−２」：任意の拡張タイセットＥ０⊆Ｅについて、完全な経路集合Ａｊが存在し、Ｅ０＝ｆ−１（Ａｊ）となる。
【０２３８】
＜２−１＞まず、「性質１−１」の正当性について説明する。
【０２３９】
経路集合Ａｊが「完全条件１，２，３」を満足するのだから、以下が成立する。
【０２４０】
「完全条件１」：Ｃ０（Ａｊ）≧α
【０２４１】
「完全条件２」：ｆ（ｆ−１（Ａｊ））＝Ａｊ
【０２４２】
「完全条件３」：Ａｊは経路数がｊよりも小さい経路集合で完全条件１と２を満足するものを集合として含まない。
【０２４３】
これから、ｆ−１（Ａｊ）が以下の条件を満足することを示す
【０２４４】
「拡張タイセット条件１」：Ｃ０（｛ｗ｜ｗ∈Ｗ，ν（ｗ）⊆ｆ−１（Ａｊ）｝）≧α
【０２４５】
「拡張タイセット条件２」：任意のｉ∈ｆ−１（Ａｊ）に対し、Ｃ０（｛ｗ｜ｗ∈Ｗ，ν（ｗ）⊆ｆ−１（Ａｊ）−｛ｉ｝＜α
【０２４６】
＜２−１−１＞  まず、『Ａｊが「完全条件１，２，３」を満足する⇒ｆ−１（Ａｊ）が「拡張タイセット条件１」を満足する』について説明する。
【０２４７】
ｆの定義（前述の「定義３」参照）より、ｆ（ｆ−１（Ａｊ））＝｛ｗ｜ｗ∈Ｗ，ν（ｗ）⊆ｆ−１（Ａｊ）｝であることと、「完全条件２」を用いて、下記の式が成り立つ。
【０２４８】
Ｃ０（｛ｗ｜ｗ∈Ｗ，ν（ｗ）⊆ｆ−１（Ａｊ）＝  Ｃ０（ｆ（ｆ−１（Ａｊ）））＝Ｃ０（Ａｊ）
【０２４９】
そして、「完全条件１」より、Ｃ０（Ａｊ）≧αであるから、「拡張タイセット条件１」を満足することが示される。      ・・・（「事実３」）
【０２５０】
＜２−１−２＞  次に、『Ａｊが「完全条件１，２，３」を満足する⇒ｆ−１（Ａｊ）が「拡張タイセット条件２」を満足する』について説明する。
【０２５１】
背理法を用いて示す。つまり、以下の「仮定１」を正しいとして矛盾（Ａｊが完全条件の一つである「完全条件３」を満足しない）を導く。
【０２５２】
「仮定１」：ある適当なｉ０∈ｆ−１（Ａｊ）がありＣ０（｛ｗ｜ｗ∈Ｗ，ν（ｗ）⊆ｆ−１（Ａｊ）−｛ｉ０｝｝）≧αとなる。
【０２５３】
背理法の流れは、以下のとおりである。
【０２５４】
段階１：ｆ（ｆ−１（Ａｊ）−｛ｉ０｝）が「完全条件１」を満足することを示す。
【０２５５】
段階２：ｆ（ｆ−１（Ａｊ）−｛ｉ０｝）がＡｊの真の部分集合であることを示す。
【０２５６】
段階３：ｆ（ｆ−１（Ａｊ）−｛ｉ０｝）が「完全条件２」を満足することを示す。
【０２５７】
段階４：段階１〜３が示されれば、Ａｊが「完全条件３」を満たさないことが示されたことになり、矛盾が導かれた。
【０２５８】
まず、段階１：ｆ（ｆ−１（Ａｊ）−｛ｉ０｝）が「完全条件１」を満足することを示す。
【０２５９】
ｆの定義（前述の「定義３」を参照）より、ｆ（ｆ−１（Ａｊ）−｛ｉ０｝）＝｛ｗ｜ｗ∈Ｗ，ν（ｗ）⊆ｆ−１（Ａｊ）−｛ｉ０｝｝が成り立つ。
【０２６０】
従って、前述の「仮定１」より、「Ｃ０（ｆ（ｆ−１（Ａｊ）−｛ｉ０｝））＝Ｃ０（｛ｗ｜ｗ∈Ｗ，ν（ｗ）⊆ｆ−１（Ａｊ）−｛ｉ０｝｝）≧α」なので、「ｆ（ｆ−１（Ａｊ）−｛ｉ０｝｝）」は完全条件１を満足する．      ・・・（「事実４」）
【０２６１】
次に、段階２：ｆ（ｆ−１（Ａｊ）−｛ｉ０｝｝）がＡｊの真の部分集合であることを、段落（２−１）と（２−１）に分けて示す。
【０２６２】
まず、段階（２−１）で、「ｆ（ｆ−１（Ａｊ）−｛ｉ０｝）⊆Ａｊ」を示し、次に、段階（２−２）で「ｆ（ｆ−１（Ａｊ）−｛ｉ０｝）≠Ａｊ」を示す。
【０２６３】
段階（２−１）：「ｆ（ｆ−１（Ａｊ）−｛ｉ０｝）⊆Ａｊ」を示す．
【０２６４】
ｆの定義（前述の「定義３」）より、下記の式が成り立つ。
【０２６５】
ｆ（ｆ−１（Ａｊ）−｛ｉ０｝｝）＝｛ｗ｜ｗ∈Ｗ，ν（ｗ）⊆ｆ−１（Ａｊ）−｛ｉ０｝｝
【０２６６】
また、前述の「基本的性質１」より、下記の式が成り立つ。
【０２６７】
｛ｗ｜ｗ∈Ｗ，ν（ｗ）⊆ｆ−１（Ａｊ）−｛ｉ０｝｝⊆｛ｗ｜ｗ∈Ｗ，ν（ｗ）⊆ｆ−１（Ａｊ）｝
【０２６８】
ｆの定義（前述の「定義３」）より、「｛ｗ｜ｗ∈Ｗ，ν（ｗ）⊆ｆ−１（Ａｊ）｝＝ｆ（ｆ−１（Ａｊ））」となり、Ａｊが「完全条件２」を満足していることを前提としていたから、下記の式が成り立つ。
【０２６９】
ｆ（ｆ−１（Ａｊ））＝Ａｊ
【０２７０】
従って、下記の式が成り立ち、これにより、段階（２−１）の正当性は示された。
【０２７１】
ｆ（ｆ−１（Ａｊ）−｛ｉ０｝）⊆Ａｊ
【０２７２】
次に、段階（２−２）：ｆ（ｆ−１（Ａｊ）−｛ｉ０｝）≠Ａｊを示す。
【０２７３】
前述の「仮定１」より、以下が言える。
【０２７４】
ある適当なｉ０∈ｆ−１（Ａｊ）がありＣ０（｛ｗ｜ｗ∈Ｗ，ν（ｗ）⊆ｆ−１（Ａｊ）−｛ｉ０｝｝）≧αとなる。
【０２７５】
今、Ａｊ＝｛ｗ１，ｗ２，・・・，ｗｊ｝と書くと、ｆ−１の定義（「定義３」）より、「ｉ０∈ｆ−１（Ａｊ）＝ν（ｗ１）∪ν（ｗ２）∪・・・∪ν（ｗｊ）」となり、上のｉ０は当然、以下を満足する。
【０２７６】
ｉ０∈ν（ｗ１）∪ν（ｗ２）∪・・・∪ν（ｗｊ）
【０２７７】
これに前述の「基本的性質８」を適用すると、下記の通りとなる。
【０２７８】
適当なｗｔ∈｛ｗ１，ｗ２，・・・，ｗｊ｝＝Ａｊが存在し、ｉ０∈ν（ｗｔ）となる。      ・・・（「事実５」）
【０２７９】
ところが、このｗｔについて、ｉ０∈ν（ｗｔ）なのだから、下記の通りである。
【０２８０】
¬（ｗｔ∈｛ｗ｜ｗ∈Ｗ，ν（ｗ）⊆ｆ−１（Ａｊ），¬（ｉ０∈ν（ｗ）｝）
【０２８１】
上式における右辺は以下の式変形により、「ｆ（ｆ−１（Ａｊ）−｛ｉ０｝）」に等しい。（ただし、ここで、「基本的性質２」とｆの定義（「定義３」）を用いた。）
【０２８２】
¬（ｗ∈｛ｗ｜ｗ∈Ｗ，ν（ｗ）⊆ｆ−１（Ａｊ），¬（ｉ０∈ν（ｗ））｝）
＝｛ｗ｜ｗ∈Ｗ，ν（ｗ）⊆ｆ−１（Ａｊ）−｛ｉ０｝｝
＝ｆ（ｆ−１（Ａｊ）−｛ｉ０｝）      ・・・（「事実６」）
【０２８３】
前述の「事実５」と「事実６」より、「ｗｔ∈Ａｉ」と「¬（ｗ∈ｆ（ｆ−１（Ａｊ）−｛ｉ０｝））」は共に正しい。これは、下記のことを意味し、これにより、段落（２−２）が示される。
【０２８４】
ｆ（ｆ−１（Ａｉ）−｛ｉ０｝≠Ａｊ
【０２８５】
次に、段階３の『ｆ（ｆ−１（Ａｊ）−｛ｉ０｝）が「完全条件２」を満足する』ことを示す。
【０２８６】
すなわち、ｆ（ｆ−１（Ａｊ）−｛ｉ０｝）＝ｆ（ｆ−１（ｆ（ｆ−１（Ａｊ）−｛ｉ０｝）））を示す。
【０２８７】
まず、段階（３−１）で左辺が右辺に含まれることを述べ、次に、段階（３−２）で、右辺が左辺に含まれることを言う。
【０２８８】
まず、段階（３−１）のｆ−１（Ａｊ）−｛ｉ０｝⊆ｆ（ｆ−１（ｆ（ｆ−１（Ａｊ）−｛ｉ０｝）））を説明する。
【０２８９】
段階２の結果より、下記の通り書くことができる。
【０２９０】
ｆ（ｆ−１（Ａｊ）−｛ｉ０｝）＝｛ｗ１，ｗ２，・・・，ｗｓ｝，    Ａｊ＝｛ｗ１，ｗ２，・・・，ｗｓ，ｗｓ＋１，・・・，ｗｊ｝      ・・・（「事実７」）
【０２９１】
この表記の下で、ｗ１∈｛ｗ｜ｗ∈Ｗ，ν（ｗ１）⊆ν（ｗ１）∪ν（ｗ２）∪・・・∪ν（ｗｓ）｝が成立する。      ・・・（「事実８」）
【０２９２】
この「事実８」の理由を下記する。
【０２９３】
一般に、Δ∈｛ｘ｜条件１，条件２｝を言うためには、Δが条件１と条件２を満足することを言えばよい。
【０２９４】
すなわち、ｗ１∈Ｗは、Ａｊ＝｛ｗ１，ｗ２，・・・，ｗｓ，ｗｓ＋１，・・・，ｗｊ｝が経路集合であったことから明らかであり、「ν（ｗ１）⊆ν（ｗ１）∪ν（ｗ２）∪・・・∪ν（ｗｓ）」は「基本的性質７」より言える。よって上式（「事実８」）は成り立つ。
【０２９５】
同様の考察を繰り返して、以下が成立する。
【０２９６】
ｗ１∈｛ｗ｜ｗ∈Ｗ，ν（ｗ１）⊆ν（ｗ１）∪ν（ｗ２）∪・・・∪ν（ｗｓ）｝、  
ｗ２∈｛ｗ｜ｗ∈Ｗ，ν（ｗ１）⊆ν（ｗ１）∪ν（ｗ２）∪・・・∪ν（ｗｓ）｝、  
・・・  
ｗｓ∈｛ｗ｜ｗ∈Ｗ，ν（ｗ１）⊆ν（ｗ１）∪ν（ｗ２）∪・・・∪ν（ｗｓ）｝
【０２９７】
従って、下記が成立する。
【０２９８】
｛ｗ１，ｗ２，・・・，ｗｓ｝⊆｛ｗ｜ｗ∈Ｗ，ν（ｗ）⊆ν（ｗ１）∪ν（ｗ２）∪・・・∪ν（ｗｓ）｝＝ｆ（ｆ−１（｛ｗ１，ｗ２，・・・，ｗｓ｝））
【０２９９】
上式の最後の等式は「基本的性質０」による。
【０３００】
前述の「事実７」より、「ｆ（ｆ−１（Ａｊ）−｛ｉ０｝）＝｛ｗ１，ｗ２，・・・，ｗｓ｝」であり、上の関係は、下記の通りに書くことができ、段階（３−１）が示される。
【０３０１】
ｆ（ｆ−１（Ａｊ）−｛ｉ０｝）⊆ｆ（ｆ−１（ｆ（ｆ−１（Ａｊ）−｛ｉ０｝）））
【０３０２】
次に、段階（３−２）の「ｆ（ｆ−１（ｆ（ｆ−１（Ａｊ）−｛ｉ０｝）））⊆ｆ（ｆ−１（Ａｊ）−｛ｉ０｝）」について説明する。
【０３０３】
前述の「事実７」における前半と、ｆの定義（「定義３」）と「基本的性質２，３」により、下記の通りとなる。
【０３０４】
｛ｗ１，ｗ２，・・・，ｗｓ｝＝ｆ（ｆ−１（Ａｊ）−｛ｉ０｝）
＝｛ｗ｜ｗ∈Ｗ，ν（ｗ）⊆ｆ−１（Ａｊ）−｛ｉ０｝｝
＝｛ｗ｜ｗ∈Ｗ，ν（ｗ）⊆ｆ−１（Ａｊ），¬（ｉ０∈ν（ｗ））｝
＝｛ｗ｜ｗ∈Ｗ，ν（ｗ）⊆ｆ−１（Ａｊ）｝∩｛ｗ｜ｗ∈Ｗ，¬（ｉ０∈ν（ｗ））｝
⊆｛ｗ｜ｗ∈Ｗ，¬（ｉ０∈ν（ｗ））｝
【０３０５】
上式右辺の｛ｗ｜ｗ∈Ｗ，¬（ｉ０∈ν（ｗ））｝に含まれる任意の要素ｗは、｛  ｝内の条件を見ると、¬（ｉ０∈ν（ｗ））を満足することが分かる。
【０３０６】
従って、上式から、｛ｗ１，ｗ２，・・・，ｗｓ｝についても、「¬（ｉ０∈ν（ｗ１）），¬（ｉ０∈ν（ｗ２）），・・・，¬（ｉ０∈ν（ｗｓ））」が成立する。
【０３０７】
これに、「基本的性質４」を適用すると、「¬（ｉ０∈ν（ｗ１）∪ν（ｗ２）∪，・・・∪ν（ｗｓ））」となり、さらに、「基本的性質５」より、下記の通りとなる。
【０３０８】
ν（ｗ１）∪ν（ｗ２）∪・・・∪ν（ｗｓ）＝ν（ｗ１）∪ν（ｗ２）∪・・・∪ν（ｗｓ）−｛ｉ０｝
【０３０９】
さらに、これに、「基本的性質０」とあわせると、以下のようになる。
【０３１０】
ｆ（ｆ−１（｛ｗ１，ｗ２，・・・，ｗｓ｝））
＝｛ｗ｜ｗ∈Ｗ，ν（ｗ）⊆ν（ｗ１）∪ν（ｗ２）∪・・・∪ν（ｗｓ）｝
＝｛ｗ｜ｗ∈Ｗ，ν（ｗ）⊆ν（ｗ１）∪ν（ｗ２）∪・・・∪ν（ｗｓ）−｛ｉ０｝｝      ・・・（「事実９」）
【０３１１】
「基本的性質１」とｆの定義（「定義３」）より、下記の通りとなる。
【０３１２】
｛ｗ｜ｗ∈Ｗ，ν（ｗ）⊆ν（ｗ１）∪ν（ｗ２）∪・・・∪ν（ｗｓ）−｛ｉ０｝｝
⊆｛ｗ｜ｗ∈Ｗ，ν（ｗ）⊆ν（ｗ１）∪ν（ｗ２）∪・・・∪ν（ｗｓ）∪ν（ｗｓ＋１）∪・・・∪ν（ｗｓ）−｛ｉ０｝｝
＝ｆ（ｆ−１（｛ｗ１，ｗ２，・・・，ｗｊ｝）−｛ｉ０｝）      ・・・（「事実１０」）
【０３１３】
上の等式右辺に、「事実７」、すなわち、Ａｊ＝｛ｗ１，ｗ２，・・・，ｗｊ｝，ｆ（ｆ−１（Ａｊ）−｛ｉ０｝）＝｛ｗ１，ｗ２，・・・，ｗｓ｝を用いると、下記の通りとなる。
【０３１４】
ｆ（ｆ−１（｛ｗ１，ｗ２，・・・，ｗｊ｝）−｛ｉ０｝）＝ｆ（ｆ−１（Ａｊ）−｛ｉ０｝）＝｛ｗ１，ｗ２，・・・，ｗｓ｝      ・・・（「事実１１」）
【０３１５】
結局、「事実９〜１１」により、下記の通りとなる。
【０３１６】
ｆ（ｆ−１（｛ｗ１，ｗ２，・・・，ｗｓ｝⊆｛ｗ１，ｗ２，・・・，ｗｓ｝
【０３１７】
そして、「事実７」より、ｆ（ｆ−１（Ａｊ）−｛ｉ０｝）＝｛ｗ１，ｗ２，・・・，ｗｓ｝であり、下記の通りとなり、段階（３−２）が言えた。
【０３１８】
ｆ（ｆ−１（ｆ（ｆ−１（Ａｊ）−｛ｉ０｝））⊆ｆ（ｆ−１（Ａｊ）−｛ｉ０｝）
【０３１９】
次に、段階（３−３）として、ｆ（ｆ−１（Ａｉ）−｛ｉ０｝）＝ｆ（ｆ−１（ｆ（ｆ−１（Ａｊ）−｛ｉ０｝）））の正当性について説明する。
【０３２０】
段階（３−１）より、ｆ（ｆ−１（Ａｉ）−｛ｉ０｝）⊆ｆ（ｆ−１（ｆ（ｆ−１（Ａｊ）−｛ｉ０｝））が成立し、段階（３−２）より、ｆ（ｆ−１（ｆ（ｆ−１（Ａｊ）−｛ｉ０｝））⊆ｆ（ｆ−１（Ａｉ）−｛ｉ０｝）が成立するので、下記の式が成立する。
【０３２１】
ｆ（ｆ−１（Ａｉ）−｛ｉ０｝）＝ｆ（ｆ−１（ｆ（ｆ−１（Ａｊ）−｛ｉ０｝）））
【０３２２】
従って、ｆ（ｆ−１（Ａｊ）−｛ｉ０｝）は「完全条件２」を満足する。
【０３２３】
次に、段階４における、段階１，２，３の結果が「Ａｊが完全である」ことに矛盾することを説明する。
【０３２４】
具体的には、経路集合Ａｊが「完全条件３」を満足しないことを説明する。
【０３２５】
まず、段階１と段階３の結果から、ｆ（ｆ−１（Ａｊ）−｛ｉ０｝）は「完全条件１」と「完全条件２」を満足する。
【０３２６】
しかし、段階２の結果からｆ（ｆ−１（Ａｊ）−｛ｉ０｝）は経路集合Ａｊの真の部分集合である。
【０３２７】
ここで、Ａｊが「完全条件３」を満足するとは、「完全条件１，２を満足するＡｊの真の部分集合が存在しない。」ことであったから、上の結果は、Ａｊが「完全条件３」を満足しないことを示しており矛盾である。
【０３２８】
＜２−２＞  次に、「性質１−２」、すなわち、「任意の拡張タイセットＥ０⊆Ｅについて、完全な経路集合Ａｊが存在し、  Ｅ０＝ｆ−１（Ａｊ）となる。」の正当性を説明する。
【０３２９】
具体的には、Ｅ０⊆Ｅが以下の「拡張タイセット条件１，２」を満足するとき、Ｅ０＝ｆ−１（Ａｊ）となる経路集合Ａｊで、さらに下記の（「完全条件１〜３」）を満足するものが存在することを示す。
【０３３０】
「拡張タイセット条件１」：Ｃ０（｛ｗ｜ｗ∈Ｗ，ν（ｗ）⊆Ｅ０｝）≧αである。
【０３３１】
「拡張タイセット条件２」：任意のｉ∈Ｅ０に対し、Ｅｇ＝Ｅ０−｛ｉ｝ならばＣ（Ｎ）＜α  （すなわち、任意のｉ∈Ｅ０に対し、Ｃ０（｛ｗ｜ｗ∈Ｗ，ν（ｗ）⊆Ｅ０−｛ｉ｝｝＜α）
【０３３２】
「完全条件１」：Ｃ０（Ａｊ）≧α
【０３３３】
「完全条件２」：ｆ（ｆ−１（Ａｊ））＝Ａｊ
【０３３４】
「完全条件３」：Ａｉは経路数がｊよりも小さい経路集合で完全条件１と２を満足するものを集合として含まない。
【０３３５】
正当性の説明は以下のとおりである。
【０３３６】
一般に、条件を満足するＸが存在することを示すには、実際にＸを構成し、構成したＸが条件を満足することを言えばよい。
【０３３７】
そこで、以下では、Ｂｊ＝｛ｗ｜ｗ∈Ｗ，ν（ｗ）⊆Ｅ０｝としたとき、ＢｊがＥ０＝ｆ−１（Ｂｊ）を満足し、かつ、前述の（「完全条件１，２，３」）を満足することを言う。
【０３３８】
尚、Ｂｉ≠φである。なぜならば、Ｃ０（Ｂｊ）＝Ｃ０（｛ｗ｜ｗ∈Ｗ，ν（ｗ）⊆Ｅ０｝）であるが、上述の拡張タイセット条件１より、Ｃ０（｛ｗ｜ｗ∈Ｗ、ν（ｗ）⊆Ｅ０｝）≧αなので、Ｃ０（Ｂｊ）≧αとなる値を持つ。Ｂｊ＝φとするならば、これは、「前提５」において、Ｃ０（ε）が値を持つのはε≠φのときであることに反する。
【０３３９】
まず、ＢｊがＥ０＝ｆ−１（Ｂｊ）を満足することを示し、続いて、Ｂｊが「完全条件１，２，３」を満足することを示す。
【０３４０】
＜２−２−１＞Ｅ０＝ｆ−１（Ｂｊ）の正当性を、以下の段階で示す。
【０３４１】
まず、段階２１：ｆ−１（Ｂｊ）⊆Ｅ０を示し、次に、段階２２：Ｅ０⊆ｆ−１（Ｂｊ）を示す。
【０３４２】
以下、段階２１のｆ−１（Ｂｊ）⊆Ｅ０を示す。
【０３４３】
Ｂｊ＝｛ｂ１，ｂ２，・・・，ｂｊ｝とする。
【０３４４】
Ｂｊの定義より、Ｂｊ＝｛ｗ｜ｗ∈Ｗ，ν（ｗ）⊆Ｅ０｝であるから、以下が成り立つ。
【０３４５】
ν（ｂ１）⊆Ｅ０，ν（ｂ２）⊆Ｅ０，・・・，ν（ｂｊ）⊆Ｅ０      ・・・（「事実１２」）
【０３４６】
従って、ｆ−１の定義（「定義３」）と「基本的性質９」より、下記が成り立つ。
【０３４７】
ｆ−１（Ｂｊ）＝ν（ｂ１）∪ν（ｂ２）∪・・・∪ν（ｂｊ）⊆Ｅ０
【０３４８】
これは、段階２１で示したかったことであった。
【０３４９】
次に、段階２２のＥ０⊆ｆ−１（Ｂｊ）を示す。
【０３５０】
これを示すには、ｆの定義（「定義３」）より、「ｆ−１（Ｂｊ）＝ν（ｂ１）∪ν（ｂ２）∪・・・∪ν（ｂｊ）」であることと、「基本的性質１１」より、以下を示せばよい。
【０３５１】
「任意のｉ∈Ｅ０について、ｉ∈ν（ｂ１）∪ν（ｂ２）∪・・・∪ν（ｂｊ）である。」
【０３５２】
以下、これを背理法で示す。つまり上の否定を以下のように仮定（「仮定２」）する。
【０３５３】
「仮定２」：¬（ｉ∈ν（ｂ１）∪ν（ｂ２）∪・・・∪ν（ｂｊ））となるｉ∈Ｅ０が存在する。
【０３５４】
この「仮定２」に、「基本的性質４」を適用すると、下記が成立する。
【０３５５】
¬（ｉ∈ν（ｂ１）），¬（ｉ∈ν（ｂ２）），・・・，¬（ｉ∈ν（ｂｊ））
【０３５６】
従って、「事実１２」と「基本的性質２」より、下記が成立する。
【０３５７】
ν（ｂ１）⊆Ｅ０−｛ｉ｝，ν（ｂ２）⊆Ｅ０−｛ｉ｝，・・・，ν（ｂｊ）⊆Ｅ０−｛ｉ｝
【０３５８】
このことから、下記が成立する。
【０３５９】
Ｂｊ＝｛ｂ１，ｂ２，・・・，ｂｊ｝⊆｛ｗ｜ｗ∈Ｗ，ν（ｗ）⊆Ｅ０−｛ｉ｝｝
【０３６０】
Ｂｊの定義、すなわち、Ｂｊ＝｛ｗ｜ｗ∈Ｗ，ν（ｗ）⊆Ｅ０｝と「前提６」と、前述の＜２−２＞において「性質１−２」（すなわち、「任意の拡張タイセットＥ０⊆Ｅについて、完全な経路集合Ａｊが存在し、  Ｅ０＝ｆ−１（Ａｊ）となる。」）の正当性を説明する際に、成り立つとした「拡張タイセット条件２：任意のｉ∈Ｅ０に対し、Ｅｇ＝Ｅ０−｛ｉ｝ならばＣ（Ｎ）＜α  （すなわち、任意のｉ∈Ｅ０に対し、Ｃ０（｛ｗ｜ｗ∈Ｗ，ν（ｗ）⊆Ｅ０−｛ｉ｝｝＜α））」より、下記の通りとなる。
【０３６１】
Ｃ０（｛ｗ｜ｗ∈Ｗ，ν（ｗ）⊆Ｅ０｝）＝Ｃ０（Ｂｊ）＝Ｃ０（｛ｂ１，ｂ２，・・・，ｂｊ｝）
≦Ｃ０（｛ｗ｜ｗ∈Ｗ，ν（ｗ）⊆Ｅ０−｛ｉ｝｝）＜α
【０３６２】
しかし、これは、同じく、前述の＜２−２＞において「性質１−２」の正当性を説明する際に、成り立つとした「拡張タイセット条件１」、すなわち、「Ｃ０（｛ｗ｜ｗ∈Ｗ，ν（ｗ）⊆Ｅ０｝）≧α」に矛盾する。
【０３６３】
以上で、＜２−２−１＞におけるＥ０＝ｆ−１（Ｂｊ）の正当性の説明を終わり、以下、＜２−２−２＞〜＜２−２−４＞において、Ｂｊが「完全条件１，２，３」を満足することを説明する。
【０３６４】
＜２−２−２＞まず、Ｂｊが「完全条件１」を満足することについて説明する。
【０３６５】
「拡張タイセット条件１」とＢｊの定義より、Ｃ０（Ｂｊ）＝Ｃ０（｛ｗ｜ｗ∈Ｗ，ν（ｗ）⊆Ｅ０｝）≧αが成立し、従って、Ｂｊは「完全条件１」を満足する。
【０３６６】
＜２−２−３＞次に、「完全条件２」を満足することについて、以下の段階で説明する。
【０３６７】
段階３１でＢｊ⊆ｆ（ｆ−１（Ｂｊ））を示し、段階３２でｆ（ｆ−１（Ｂｊ））⊆Ｂｊを示す。
【０３６８】
まず、段階３１：Ｂｉ⊆ｆ（ｆ−１（Ｂｊ））を示す。
【０３６９】
＜２−２−１＞でのＥ０＝ｆ−１（Ｂｊ）の正当性の説明と同様に、Ｂｊ＝｛ｂ１，ｂ２，・・・，ｂｊ｝とする。
【０３７０】
任意のｂｒ∈｛ｂ１，ｂ２，・・・，ｂｊ｝について、下記のことが、「基本的性質１０」より言える。
【０３７１】
ν（ｂｒ）⊆ν（ｂ１）∪ν（ｂ２）∪・・・∪ν（ｂｊ）      ・・・（「事実１３」）
【０３７２】
従って、任意のｂｒ∈｛ｂ１，ｂ２，・・・，ｂｊ｝について、「事実８」の理由と同じ考察に基づき、下記のことが言える。
【０３７３】
ｂｒ∈｛ｗ｜ｗ∈Ｗ，ν（ｗ）⊆ν（ｂ１）∪ν（ｂ２）∪・・・∪ν（ｂｊ）｝
【０３７４】
そして、「基本的性質０」より、「｛ｗ｜ｗ∈Ｗ，ν（ｗ）⊆ν（ｂ１）∪ν（ｂ２）∪，・・・∪ν（ｂｊ）｝＝  ｆ（ｆ−１（Ｂｊ））」が成り立つので、結局、任意のｂｒ∈｛ｂ１，ｂ２，・・・，ｂｊ｝＝Ｂｊについて、「ｂｒ∈ｆ（ｆ−１（Ｂｊ））」が言えた。
【０３７５】
これと「基本的性質１１」より、以下が言える。
【０３７６】
Ｂｊ⊆ｆ（ｆ−１（Ｂｊ））
【０３７７】
つまり、段階３１の正当性が言え、以上で、段階３１の説明を終了する。
【０３７８】
次に、段階３２のｆ（ｆ−１（Ｂｊ））⊆Ｂｊについて説明する。
【０３７９】
Ｂｊの定義：Ｂｊ＝｛ｂ１，ｂ２，・・・，ｂｊ｝＝｛ｗ｜ｗ∈Ｗ，ν（ｗ）⊆Ｅ０｝より、下記が成立する。
【０３８０】
ν（ｂ１）⊆Ｅ０，ν（ｂ２）⊆Ｅ０，・・・，ν（ｂｊ）⊆Ｅ０
【０３８１】
さらに、「基本的性質９」より、下記が成立する。
【０３８２】
ν（ｂ１）∪ν（ｂ２）∪・・・∪ν（ｂｊ）⊆Ｅ０
【０３８３】
一方、「基本的性質０」より、下記の通りとなる。
【０３８４】
ｆ（ｆ−１（Ｂｊ））＝｛ｗ｜ｗ∈Ｗ，ν（ｗ）⊆ν（ｂ１）∪ν（ｂ２）∪・・・∪ν（ｂｊ）｝
【０３８５】
これと「事実１４」に「基本的性質１」を適用すると、下記の式の通りとなる。尚、最後の等式はＢｉの定義による。
【０３８６】
ｆ（ｆ−１（Ｂｊ））＝｛ｗ｜ｗ∈Ｗ，ν（ｗ）⊆ν（ｂ１）∪ν（ｂ２）∪・・・∪ν（ｂｊ）｝
⊆｛ｗ｜ｗ∈Ｗ，ν（ｗ）⊆Ｅ０｝＝Ｂｊ
【０３８７】
これは段階３２が示せたことを意味する。以上で、段階３２の説明を終了する。
【０３８８】
以上の段階３１と段階３２の結果より、Ｂｊは「完全条件２」を満足することが言えた。
【０３８９】
＜２−２−４＞次に、「完全条件３」について説明する。ここでは、背理法を用いる。つまり、以下の仮定（「仮定３」）から矛盾を導く。
【０３９０】
「仮定３」：Ｂｊが「完全条件３」を満足しない。
【０３９１】
この「仮定３」が正しいとすると、以下の「仮定３’」が正しい。
【０３９２】
「仮定３’」：ある経路数ｈ＜ｊについて、「完全条件１」と「完全条件２」を満足するＢｈが存在し、Ｂｈ⊂Ｂｊが成立する。
【０３９３】
従って、下記の通り書くことができる。
【０３９４】
Ｂｈ＝｛ｂ１，ｂ２，・・・，ｂｈ｝，  Ｂｊ＝｛ｂ１，ｂ２，・・・，ｂｈ，ｂｈ＋１，・・・，ｂｊ｝      ・・・（「事実１５」）
【０３９５】
以下の段階４１〜４４の流れで、「仮定３'」から矛盾を導く。
【０３９６】
段階４１：ｉ０∈ｆ−１（Ｂｊ），¬（ｉ０∈ｆ−１（Ｂｈ））となるｉ０∈Ｅ０が存在することを示す。
【０３９７】
段階４２：上のｉ０について、Ｃ０（｛ｗ｜ｗ∈Ｗ，ν（ｗ）⊆Ｅ０−｛ｉ０｝｝）≧αを示す。
【０３９８】
段階４３：同じｉ０について、Ｃ０（｛ｗ｜ｗ∈Ｗ，ν（ｗ）⊆Ｅ０−｛ｉ０｝｝）＜αを示す。
【０３９９】
段階４４：段階４２と段階４３の結果は矛盾している。
【０４００】
まず、段階４１のｉ０∈ｆ−１（Ｂｊ），¬（ｉ０∈ｆ−１（Ｂｈ））となるｉ０∈Ｅ０が存在することを示す。
【０４０１】
これが成立しないとすると、「基本的性質１２」より、ｆ−１（Ｂｊ）＝ｆ−１（Ｂｈ）となる。
【０４０２】
両辺にｆを適用すると、ｆ（ｆ−１（Ｂｊ））＝ｆ（ｆ−１（Ｂｈ））が成立するが、＜２−２−３＞の結果と「仮定３'」より、ＢｊもＢｈも「完全条件２」を満足するので、下記のようになる。
【０４０３】
Ｂｊ＝ｆ（ｆ−１（Ｂｊ））＝ｆ（ｆ−１（Ｂｈ））＝Ｂｈ
【０４０４】
しかし、これは、「仮定３'」のＢｈ⊂Ｂｊに矛盾する。これにより、段階４１は終了する。
【０４０５】
次に、段階４２のＣ０（｛ｗ｜ｗ∈Ｗ，ν（ｗ）⊆Ｅ０−｛ｉ０｝｝）≧αを示す。
【０４０６】
説明のための準備として以下の事実を示す
【０４０７】
ｆ−１（Ｂｈ）＝ν（ｂ１）∪ν（ｂ２）∪・・・∪ν（ｂｈ）      ・・・（「事実１６」）
【０４０８】
ν（ｂ１）⊆Ｅ０，ν（ｂ２）⊆Ｅ０，・・・，ν（ｂｊ）⊆Ｅ０      ・・・（「事実１７」）
【０４０９】
「事実１６」はｆ−１の定義（「定義３」）どおりであるので正当である。
【０４１０】
「事実１７」は、前述の＜２−２＞の冒頭において、Ｂｊ＝｛ｗ｜ｗ∈Ｗ，ν（ｗ）⊆Ｅ０｝と定義したことから、Ｂｊの要素ｂ１，ｂ２，・・・，ｂｊが｛  ｝内の条件を満たすので、その正当性は明らかである。
【０４１１】
以下、段階４２−１で、補助的性質を示し、段階４２−２で、Ｃ０（｛ｗ｜ｗ∈Ｗ，ν（ｗ）⊆Ｅ０−｛ｉ０｝｝）≧αを示す。
【０４１２】
まず、段階４２−１で、ν（ｂ１）⊆Ｅ０−｛ｉ０｝，ν（ｂ２）⊆Ｅ０−｛ｉ０｝，・・・，ν（ｂｈ）⊆Ｅ０−｛ｉ０｝を示す。
【０４１３】
段階４１の結果より、ｉ０∈ｆ−１（Ｂｊ），¬（ｉ０∈ｆ−１（Ｂｈ）），ｉ０∈Ｅ０である。
【０４１４】
ここで、¬（ｉ０∈ｆ−１（Ｂｈ））に着目する。
【０４１５】
「事実１６」より、ｆ−１（Ｂｈ）＝ν（ｂ１）∪ν（ｂ２）∪・・・∪ν（ｂｈ）であるから、結局、¬（ｉ０∈ν（ｂ１）∪ν（ｂ２）∪・・・.∪ν（ｂｈ））が成立する。
【０４１６】
これと「基本的性質４」より、¬（ｉ０∈ν（ｂ１）），¬（ｉ０∈ν（ｂ２）），・・・，¬（ｉ０∈ν（ｂｈ））が成立し、さらに、「事実１７」と「基本的性質２」より、ν（ｂ１）⊆Ｅ０−｛ｉ０｝，ν（ｂ２）⊆Ｅ０−｛ｉ０｝，・・・，ν（ｂｈ）⊆Ｅ０−｛ｉ０｝が成立する。これにより、段階４２−１が示された。
【０４１７】
次に、段階４２−２のＣ０（｛ｗ｜ｗ∈Ｗ，ν（ｗ）⊆Ｅ０−｛ｉ０｝｝）≧αについて説明する。
【０４１８】
段階２−１の結果より、以下が成立する。
【０４１９】
ν（ｂ１）⊆Ｅ０−｛ｉ０｝，ν（ｂ２）⊆Ｅ０−｛ｉ０｝，・・・，ν（ｂｈ）⊆Ｅ０−｛ｉ０｝
【０４２０】
従って、「事実８」と同様の考察により、以下のことが言える。
【０４２１】
ｂ１∈｛ｗ｜ｗ∈Ｗ，ν（ｗ）⊆Ｅ０−｛ｉ０｝｝、
ｂ２∈｛ｗ｜ｗ∈Ｗ，ν（ｗ）⊆Ｅ０−｛ｉ０｝｝、
・・・
ｂｈ∈｛ｗ｜ｗ∈Ｗ，ν（ｗ）⊆Ｅ０−｛ｉ０｝｝
【０４２２】
従って、下記の式が成立する。
【０４２３】
Ｂｈ＝｛ｂ１，ｂ２，・・・，ｂｈ｝⊆｛ｗ｜ｗ∈Ｗ，ν（ｗ）⊆Ｅ０−｛ｉ０｝｝
【０４２４】
ここで、「仮定３'」で述べたように、Ｂｈが「完全条件１」を満足することと「前提６」より、下記の通りとなり、段階４２が示される。
【０４２５】
α≦Ｃ０（Ｂｈ）≦Ｃ０（｛ｗ｜ｗ∈Ｗ，ν（ｗ）⊆Ｅ０−｛ｉ０｝｝）
【０４２６】
次に、段階４３におけるＣ０（｛ｗ｜ｗ∈Ｗ，ν（ｗ）⊆Ｅ０−｛ｉ０｝｝）＜αに関しては、Ｅ０が拡張タイセットであることから、「拡張タイセット条件２」より上の不等式が成立することが言える。
【０４２７】
従って背理法より「仮定３」は誤りであり、段階４４における「段階２と３は矛盾する」が言える。
【０４２８】
以上の「＜２−２−１＞〜＜２−２−４＞」により、Ｂｊは、Ｅ０＝ｆ−１（Ｂｊ）となる完全な経路集合であることが言え、Ｂｊの表記をＡｊにすることで、「＜２−２＞」の正当性が示される。
【０４２９】
＜３＞  ：次に、『各経路数毎の完全な経路集合の列挙手順の正当性』について説明する。具体的には以下の「性質２，３」を用いて説明する。
【０４３０】
「性質２」：以下の包含関係が成立する。尚、「ｍ＝１，２，・・・」とする。
【０４３１】
ＥＴ（ｍ＋１）⊆ｇ（ＮＥＴ（ｍ）），ＮＥＴ（ｍ＋１）⊆ｇ（ＮＥＴ（ｍ））
【０４３２】
「性質３」：以下の関係が成立する。
【０４３３】
ＮＥＴ（ｍ０）＝φ  ⇒  ｍ＞ｍ０に対し、ＮＥＴ（ｍ）＝φ，ＮＥＴ（ｍ）＝φ
【０４３４】
「性質２」は、手順中、経路数ｍ＋１の全ての経路集合の完全条件を確認しなくても、ｇ（ＮＥＴ（ｍ））に含まれる経路集合さえ確認すれば、経路数ｍ＋１の完全な経路集合の全て（ＥＴ（ｍ＋１）に対応））と、経路数ｍ＋１で「完全条件３」を満足するが、「完全条件１」または「完全条件２」を満足しない経路集合の全て（ＮＥＴ（ｍ＋１）に対応）を列挙することができることを意味している。
【０４３５】
「性質３」は、ＮＥＴ（ｍ０）＝φが確認された時点で、それ以上手順を実行しても（つまりｍをｍ０より大きくしても）もはや完全な経路集合は発見されないことを意味し、手順の停止条件の正当性を与えている。
【０４３６】
＜３−１＞  ：「性質２」における「ＥＴ（ｍ＋１）⊆ｇ（ＮＥＴ（ｍ））」の正当性について説明する。尚、「性質２」におけるＮＥＴ（ｍ＋１）⊆ｇ（ＮＥＴ（ｍ）も同様に示すことができる。
【０４３７】
この正当性を示すには、以下のようにして、「基本的性質１１」より、「任意のｖ∈ＥＴ（ｍ＋１）についてｖ∈ｇ（ＮＥＴ（ｍ））」を示せばよい。
【０４３８】
これは、前述の「式（２）」より、「ｇ（ＮＥＴ（ｍ））＝｛ｘ｜ｘ⊆Ｗ，適当なｚ∈ＮＥＴ（１），ｙ∈ＮＥＴ（ｍ）が存在して、ｘ＝ｚ∪ｙ，ｘの経路数＝ｍ＋１｝」なので、任意のｖ∈ＥＴ（ｍ＋１）に対し、上式の右の集合の条件、「ｖ⊆Ｗ」と「適当なｚ∈ＮＥＴ（１），ｙ∈ＮＥＴ（ｍ）が存在して、ｘ＝ｚ∪ｙ，ｘの経路数＝ｍ＋１」を示せばよい。
【０４３９】
「ｖ⊆Ｗ」については、ＥＴ（ｍ＋１）は経路数ｍ＋１の完全な経路集合の集まりと定義したのであり、ｖ∈ＥＴ（ｍ＋１）も経路集合である。経路集合はＷの部分集合と定義したものであるから、ｖ⊆Ｗは明らかである。
【０４４０】
従って、以下では、「適当なｚ∈ＮＥＴ（１），ｙ∈ＮＥＴ（ｍ）が存在して、ｖ＝ｚ∪ｙ」かつ「ｖの経路数＝ｍ＋１」となることを示す。
【０４４１】
「ｖの経路数＝ｍ＋１」に関しては、ｖ∈ＥＴ（ｍ＋１）から、ｖの経路数はｍ＋１であることは明らかであり、結局、「適当なｚ∈ＮＥＴ（１），ｙ∈ＮＥＴ（ｍ）が存在して、ｖ＝ｚ∪ｙとなる。」を示せば良く、これは以下のようにして示される。
【０４４２】
ｖ＝｛ξ１，ξ２，・・・，ξｍ＋１｝とする。
【０４４３】
ｖ∈ＥＴ（ｍ＋１）から、ｖは完全なので、「完全条件３」より、ｖに含まれる経路数がｍ＋１未満の経路集合は完全ではない。従って、｛ξ１｝は完全ではない経路数１の経路集合である。しかし｛ξ１｝は明らかに「完全条件３」を満足するので、｛ξ１｝は「完全条件１」または「完全条件２」を満足しない。すなわち、以下が成立する。
【０４４４】
｛ξ１｝∈ＮＥＴ（１）      ・・・（「事実１８」）
【０４４５】
同様に｛ξ２，・・・，ξｍ＋１｝も完全な経路集合ではない。      ・・・（「事実１９」）
【０４４６】
さらに、｛ξ２，・・・，ξｍ＋１｝は経路数がｍより小さい完全な経路集合を含まない。      ・・・（「事実２０」）
【０４４７】
なぜならば、｛ξ２，・・・，ξｍ＋１｝が経路数ｍより小さい完全な経路集合（極小パス）ｖ’を含むならば、下記が成立し、ｖが「完全条件３」を満足することに矛盾する。
【０４４８】
ｖ’⊂｛ξ２，・・・，ξｍ＋１｝⊂｛ξ１，ξ２，・・・，ξｍ＋１｝＝ｖ、
ｖ’の経路数＜ｍ＜ｍ＋１
【０４４９】
「事実１９」により、｛ξ２，・・・，ξｍ＋１｝は「完全条件１，２，３」のうち少なくとも一つを満足しないが、「事実２０」は、｛ξ２，・・・，ξｍ＋１｝が「完全条件３」を満足することを示している。
【０４５０】
従って、｛ξ２，・・・，ξｍ＋１｝は「完全条件１」または「完全条件２」を満足しない。
【０４５１】
ゆえに、ＮＥＴ（ｍ）の定義より、下記のようになる。
【０４５２】
｛ξ２，・・・，ξｍ＋１｝∈ＮＥＴ（ｍ）      ・・・（「事実２１」）
【０４５３】
ここで、「ｖ＝｛ξ１，ξ２，・・・，ξｍ＋１｝＝｛ξ１｝∪｛ξ２，・・・，ξｍ＋１｝」が成り立つことと、「事実１８」と「事実２１」より、「ｚ＝｛ξ１｝，ｙ＝｛ξ２，・・・，ξｍ＋１｝」とすれば、「ｚ∈ＮＥＴ（１），ｙ∈ＮＥＴ（ｍ），ｖ＝ｚ∪ｙ」となるｚ∈，ｙ∈が構成できたので、上述の「適当なｚ∈ＮＥＴ（１），ｙ∈ＮＥＴ（ｍ）が存在して、ｖ＝ｚ∪ｙとなる。」が成立することが示される。
【０４５４】
＜３−２＞  ：次に、「性質３」における「ＮＥＴ（ｍ０）＝φ  ⇒  ｍ＞ｍ０に対し、ＮＥＴ（ｍ）＝φ，ＮＥＴ（ｍ）＝φ」の正当性について、第１〜第３の段階の順で説明する。
【０４５５】
まず、第１段階として、ＮＥＴ（ｍ０）＝φ  ⇒  ｇ（ＮＥＴ（ｍ０））＝φを示す。
【０４５６】
ｇ（ＮＥＴ（ｍ０））≠φと仮定すると、適当なｘ０∈ｇ（ＮＥＴ（ｍ０））が存在するが、ｇ（  ）の定義より、「ｘ０∈ｇ（ＮＥＴ（ｍ０））＝｛ｘ｜ｘ⊆Ｗ，適当なｚ∈ＮＥＴ（１），ｙ∈ＮＥＴ（ｍ）が存在して、ｘ＝ｚ∪ｙ，ｘの経路数＝ｍ＋１｝」となり、適当なｚ∈ＮＥＴ（１），ｙ∈ＮＥＴ（ｍ０）が存在して、ｘ＝ｚ∪ｙとなる。
【０４５７】
しかし、今、ＮＥＴ（ｍ０）＝φであるからｙ∈ＮＥＴ（ｍ０）となるｙは存在しないので、矛盾である。従って、背理法より、第１段階は成立する。
【０４５８】
次に、第２段階として、ｇ（ＮＥＴ（ｍ））＝φ  ⇒  ＥＴ（ｍ＋１）＝ＮＥＴ（ｍ＋１）＝φを示す
【０４５９】
ＥＴ（ｍ＋１）≠φと仮定すると、適当なｘ０∈ＥＴ（ｍ＋１）が存在する。ところが、上述の「性質２」より、ｘ０∈ＥＴ（ｍ＋１）⊆ｇ（ＮＥＴ（ｍ））となり、ｇ（ＮＥＴ（ｍ））＝φに矛盾する。同様にＮＥＴ（ｍ＋１）＝φが言える。
【０４６０】
次に、第３段階として、「ＮＥＴ（ｍ０）＝φ  ⇒  ｍ＞ｍ０に対し、ＮＥＴ（ｍ）＝φ，ＮＥＴ（ｍ）＝φ」を示す。すなわち、第１段階と第２段階を繰り返し用い、帰納的に、ｍ＞ｍ０に対し、「ＮＥＴ（ｍ）＝φ」、「ＮＥＴ（ｍ）＝φ」が言える。
【０４６１】
以下、図１１〜図２０を用いて、本発明の実施例を説明する。
【０４６２】
図１１は、本発明に係る通信網信頼性評価を実施する装置の構成例を示すブロック図であって、本例の装置は、ＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）や主メモリ、表示装置、入力装置、記憶装置からなるコンピュータ構成からなり、光ディスク駆動装置等を介してＣＤ−ＲＯＭ等の記憶媒体に記録されたプログラムやデータを記憶装置内にインストールした後、この記憶装置から主メモリに読み込みＣＰＵで処理することにより、各処理部の機能を実行する。すなわち、本例では、プログラムされたコンピュータによって、以下のようにして、通信網の信頼性を評価する処理を行う。
【０４６３】
通信網を構成する通信装置やケーブル等の各通信網構成要素を番号付けして記憶装置に記憶し、情報を送信する際にどの通信網構成要素を経由するかを示す通信のための１以上の経路を番号付けして記憶装置に記憶し、さらに、正常に機能している通信網構成要素から成る経路によって送信される情報の量（通信容量）および通信網構成要素の故障確率を予め記憶装置に記憶しておき、以下のようにして、通信網が故障により段階的に送信できる情報量が劣化しても、あるしきい値α以上の通信容量が確保される確率を導出する。
【０４６４】
まず、経路を、各経路が経由する通信網構成要素を要素とする集合とし、正常に機能する経路によって確保される通信容量、各通信網構成の故障確率に関するデータを、故障データとして記憶装置から読み出し、この故障データから、全ての経路からなる集合の部分集合（経路集合）の一つ一つについて、（イ）当該経路集合に含まれる経路によって所定の通信容量が確保されること（完全条件１）、（ロ）当該経路集合を構成する経路が正常であった場合に、当該経路集合に含まれない経路が正常に機能するという現象が発生しないこと（完全条件２）、（ハ）当該経路集合が、完全条件１および完全条件２を満足する真の部分集合を含まないこと（完全条件３）、を確認し、さらに、これらの完全条件１〜３を満足する経路集合に初等的な集合演算を施すことで、以下の（ニ）、（ホ）の条件を満足する通信網構成要素の集合（拡張タイセット）を全て生成する。
【０４６５】
（ニ）当該拡張タイセットに含まれる全ての通信網構成要素が正常であれば、通信網において、しきい値α以上の通信容量を確保することができる。
【０４６６】
（ホ）当該拡張タイセットに含まれる通信網構成要素が一つでも故障すれば、通信網において、しきい値α以上の通信容量を確保することができない。
【０４６７】
そして、少なくとも一つの拡張タイセットに含まれる全ての通信網構成要素が正常に機能する確率を、通信網において所定以上の通信容量が確保される確率として出力する。
【０４６８】
また、上述の各経路集合について（イ）（ロ）（ハ）の条件（完全条件１，２，３）を確認する際、当該経路集合に含まれる経路の数の少ない経路集合から確認を開始し、（イ）（ロ）（ハ）の条件を満足しなかったとしても、（ハ）を満足する経路集合については、当該経路集合が含む経路番号を物理媒体に保存しておき、経路集合が含む経路の数を逐次増やして（イ）（ロ）（ハ）を確認することで、確認作業の効率化を図る。
【０４６９】
以下、このような処理動作の詳細を図１１〜図２０に示す具体的な例を用いて説明する。
【０４７０】
図１１に示す、プログラムされたコンピュータにより通信網信頼性評価処理を行う装置は、通信網の構成を示すデータを格納する記憶部１１と、そのデータから経路によって確保される通信容量を計算する通信容量計算部６、上述の拡張タイセットを生成する拡張タイセット生成部７、拡張タイセットから所望の信頼性を計算する信頼性計算実行部８、これらの各処理部を制御する制御部５、補助記憶部１〜４、人力装置としてのキーボード（図中「ＫＥＹ」と記載）１０、出力装置を構成するディスプレイ表示部９と表示メモリ１２およびＣＲＴ（Ｃａｔｈｏｄｅ  Ｒａｙ  Ｔｕｂｅ）１３を有する。
【０４７１】
まず、記憶部１１について説明し、以下、通信容量計算部６、補助記憶部１，補助記憶部２、補助記憶部３、補助記憶部４、拡張タイセット生成部７、信頼性計算実行部８、制御部５の順に各装置の機能を説明する。尚、ここでは、補助記憶部１〜４および記憶部１１のそれぞれは、ＨＤＤ（Ｈａｒｄ  Ｄｉｓｋ  Ｄｒｉｖｅ）や主メモリ等の記憶装置と、当該記憶装置とのデータの入出力処理をプログラムに基づき実行するＣＰＵとで実現される機能として記載する。
【０４７２】
記憶部１１には、予め設定された入力データが格納されており、その入力データの構造を図１２に示す（図１２の数値は、例としての仮想値）。
【０４７３】
図１２のテーブル１２０１において、１行目には、対象とする通信網構成装置に対応する番号が格納されている。ここでは「１〜６」の番号が示されている。
【０４７４】
２行目には、１行目に人力された通信網構成装置（１〜６）のそれぞれの故障確率が格納されている。すなわち、１行目のｉ列目の通信網構成装置の故障確率が２行目のｉ列目に記憶されている。
【０４７５】
３行目には、対象とする通信網に割り当てられた経路に対応する番号（「１，２，３，４」）が格納されている。ここでは、１行目の通信網構成装置の番号と区別するため、経路に対応する番号にはアンダーラインを引いている。
【０４７６】
４行目には、現用の経路を構成する各経路の番号（「１，２」）が格納され、５行目には、予備の経路を構成する各経路の番号（「３，４」）が格納されている。
【０４７７】
６〜９行目には、各行を各経路（「１，２，３，４」）に対応させ、その経路に含まれる各通信網構成要素の番号（「１〜６」）が格納され、最後の１０行目には、通信容量のしきい値（α）の値が格納されている。
【０４７８】
通信容量計算部６は、処理対象の通信網における経路全体集合Ｗの任意部分の集合ε（経路集合ε）に含まれる全ての経路が正常に機能したとき、経路集合εに含まれる通信網構成要素から構成される経路を利用して確保される通信容量Ｃ０（ε）の算出を行うものであり、この算出は、通信容量の割り当てや予備のあり方に依存する。本例では、説明の容易性のため、以下の式で算出を行うものとする。
【０４７９】
Ｃ０（ε）＝Ｍｉｎ（εに含まれる経路の数，現用経路の数）×１００
【０４８０】
これは、各経路が１００の通信容量を確保し、どの現用経路が利用できなくなっても、正常である予備経路に確実に切り替わるという想定での計算である。
【０４８１】
補助記憶部１は、上述の完全条件１，２，３を全て満足する経路数ｍの経路集合ＥＴ（ｍ）のデータ（すなわち、経路数ｍの完全な経路集合の集合に対応）を格納する。
【０４８２】
補助記憶部１で格納するデータの構造は図１３におけるテーブル１３０１に示すとおりである。テーブル１３０１における左側に経路数ｍの値（「１，２」）、右側に経路集合ＥＴ（ｍ）の要素の一つ一つに含まれる経路に対応する番号（「１〜４」）を格納する。
【０４８３】
図１３では、経路数ｍ＝１のときの完全な経路集合がＥＴ（１）＝｛経路４｝であり、経路数ｍ＝２のときの完全な経路集合がＥＴ（２）＝｛経路１，経路３｝，｛経路２，経路３｝である場合を示している。
【０４８４】
補助記憶部２は、上述の完全条件３を満足するが、完全条件１または２を満足しない経路数ｍの経路集合ＮＥＴ（ｍ）のデータ（すなわち、経路数ｍの経路集合で、完全条件３は満足するが完全条件１または２を満足しない経路集合の集合に対応）を格納する。そのデータの構造は、図１３に示す補助記憶部１の場合に準ずる。
【０４８５】
補助記憶部３は、経路数ｍ＋１の経路集合のうち、既に実行した手順より、完全にはならないことが分かっている場合を除いた経路集合の集合ｇ（ＮＥＴ（ｍ））のデータを格納する。そのデータの構造は、補助記憶部２と同様に補助記憶部１の場合に準ずる。
【０４８６】
補助記憶部４は、拡張タイセット生成部７が生成した拡張タイセットを格納する。格納するデータの構造は、図１４におけるテーブル１４０１に示すとおりである。すなわち、各行左欄に、拡張タイセットを区別するための番号（「１〜３」）を格納し、右欄に、各拡張タイセットを構成する通信網構成要素の番号（「１〜６」）を格納している。
【０４８７】
拡張タイセット生成部７は、上述した各経路数毎の完全な経路集合を列挙するための手順１〜６を以下のように各部と連携しながら実現する。
【０４８８】
手順１：記憶部１１のテーブル１２０１を参照して、３行目から経路に対応する番号を確認し、一つ一つの経路について完全条件１，２，３を満足するかどうかを確認する。
【０４８９】
ここで、完全条件１を満足するかの確認については、通信容量計算部６を用いて、各経路が確保する通信容量を計算し、記憶部１１のテーブル１２０１における通信容量定数の欄に登録された値（「２００」）と比較することで確認する。
【０４９０】
完全条件２を満足するかの確認については、記憶部１１のテーブル１２０１における６〜９行目のデータから、ｆとｆ−１の計算を行うことで、確認する。
【０４９１】
このｆとｆ−１の実行手順は以下のとおりである。
【０４９２】
通信網構成要素の集合｛ｉ１，ｉ２，・・・，ｉｅ｝について、「ｆ（｛ｉ１，ｉ２，・・・，ｉｅ｝）＝｛ｗ｜ｗ∈Ｗ，ν（ｗ）⊆｛ｉ１，ｉ２，・・・，ｉｅ｝｝」を以下のように算出する。
【０４９３】
尚、集合Ｗに含まれる経路数をｍとする。また、プログラミング技術（プログラム言語）の形式に基づき表現とする。
【０４９４】
まずＱ＝φとする。
Ｆｏｒ  ｋ＝１  ｔｏ  ｍ
経路ｗｋを記憶部のデータの左欄から探す。
探し当てたｗｋの行の右欄の通信網構成要素が全て｛ｉ１，ｉ２，・・・，ｉｅ｝に含まれるかを確認する。
Ｉｆ  含まれるならば、Ｑ＝Ｑ∪｛ｗｋ｝とする。
Ｅｎｄ
ｆ（｛ｉ１，ｉ２，・・・，ｉｅ｝）＝Ｑとする。
【０４９５】
また、経路集合Ａｊ＝｛ｗ１，ｗ２，・・・，ｗｊ｝ついて、ｆ−１（Ａｊ）＝ν（ｗ１）∪ν（ｗ２）∪・・・∪ν（ｗｓ）は以下のように算出する。
【０４９６】
まず、Ｑ＝φとする。
Ｆｏｒ  ｋ＝１  ｔｏ  ｊ
記憶部１１のテーブル１２０１から経路ｗｋの右欄の通信網構成要素（すなわちν（ｗｋ）に含まれる要素）を列挙し、これをｉ１，ｉ２，・・・ｉｇとする。
Ｑ＝Ｑ∪｛ｉ１，ｉ２，・・・，ｉｇ｝
Ｅｎｄ
ｆ−１（Ａｊ）＝Ｑとする。
【０４９７】
完全条件３を満足するかの確認については、経路数が１であることから、全ての経路について満足する。
【０４９８】
完全であるならば、補助記憶部１に格納し（ＥＴ（ｍ））、そうでなければ、補助記憶部２に格納する（ＮＥＴ（ｍ））。
【０４９９】
ｍ＝１とする。
【０５００】
手順２：補助記憶部２のデータを確認し、ＮＥＴ（ｍ）がφならば終了。
【０５０１】
手順３：以下の手順（プログラム言語表現）によって、ｇ（ＮＥＴ（ｍ））を生成して補助記憶部３に書き込む。
【０５０２】
Ｆｏｒ  ｚ∈ＮＥＴ（１）
Ｆｏｒ  ｙ∈ＮＥＴ（ｍ）
ｉｆ  ｚ∪ｙ経路数＝ｍ＋１  ｔｈｅｎ  ｚ∪ｙを補助記憶部３に格納する。
Ｅｎｄ
Ｅｎｄ
【０５０３】
手順４：補助記憶部３に格納された各経路集合（ｇ（ＮＥＴ（ｍ）））について、完全条件１，２，３を満足するものを補助記憶部１に格納する。
【０５０４】
ここで、完全条件１，２の確認は手順１に準ずる。完全条件３の確認は、補助記憶部１に格納された経路集合を集合として含まないことを確認する。
【０５０５】
手順５：手順４で完全条件３を満足するが完全条件１または２を満足しない経路集合を補助記憶部２に格納する。
【０５０６】
手順６：ｍ＝ｍ＋１として、手順２に進む。
【０５０７】
上の手順によって、各経路数の完全な経路集合が補助記憶部１に格納される。ここから、上述の「性質１」を用いることにより、補助記憶部１に格納された、各経路集合｛ｗ１，ｗ２，・・・，ｗｍ｝に対し、それに対応する拡張タイセットＥ０を以下のように生成することができる。
【０５０８】
まず、Ｅ０＝φとする。
Ｆｏｒ  ｋ＝１ｔｏｍ
記憶部から経路ｗｋの右欄の通信網構成要素を列挙しＥ０に加える。
ｅｎｄ
【０５０９】
得られた拡張タイセットを補助記憶部４に格納する。
【０５１０】
信頼性計算実行部８は、通信網の信頼性＝Ｐｒ（Ｃ（Ｎ）≧α）＝Ｐｒ（少なくとも一つの拡張タイセットに含まれる全ての要素が正常である。上述の公知文献（Ｗ．Ｇ．Ｓｃｈｎｅｅｗｅｉｓｓ，ＢＯＯＬＥＡＮ  ＦＵＮＣＴＩＯＮＳ，Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ  Ｂｅｒｌｉｎｅ  １９８９．）に記載の技術によって計算する。
【０５１１】
制御部５は、これまで説明した各処理部を以下の制御手順で動作させ、記憶部１１に入力されたデータから通信網の信頼性を計算する。
【０５１２】
制御手順１：記憶部１１におけるテーブル１２０１のデータを拡張タイセット生成部７に取り込み、拡張タイセットを全て列挙する。結果を補助記憶部４に格納する
【０５１３】
制御手順２：補助記憶部４におけるデータを信頼性計算実行部８に取り込み、通信網の信頼性を計算する。
【０５１４】
制御手順３：計算結果を、ディスプレイ表示部９、表示メモリ１２を介してＣＲＴ１３に表示する。
【０５１５】
このような、装置の各処理部の連携の具体的な様子を示すため、図１２に示す記憶部１１におけるテーブル１２０１のデータに対する計算実行例を以下に示す。
【０５１６】
図１２に示すテーブル１２０１におけるデータを拡張タイセット生成部７に取り込み、拡張タイセット生成部７を起動すると、以下のように、それぞれ経路数毎の完全な経路集合が生成される。
【０５１７】
手順１：記憶部１１のデータ、すなわち、図１２におけるテーブル１２０１の２行目を参照して、各経路に対応する番号を確認し、一つ一つの経路について完全条件１，２，３を満足するかどうかを確認する。
【０５１８】
ここでは、｛経路４｝が完全であるので、｛経路４｝を補助記憶部１に格納し、完全条件３を満足するが完全条件１または２を満足しない｛経路１｝，｛経路２｝，｛経路３｝を補助記憶部２に格納する。その結果を図１５のテーブル１５０１および図１６のテーブル１６０１に示す。
【０５１９】
経路数ｍ＝１とする。
【０５２０】
手順２：補助記憶部２のデータ（図１６におけるテーブル１６０１）を確認し、ＮＥＴ（ｍ）がφでないので手順３に進む。
【０５２１】
手順３：ｇ（ＮＥＴ（ｍ））を以下のように生成して補助記憶部３に書き込む。その結果を図１７のテーブル１７０１に示す。
【０５２２】
ｇ（ＮＥＴ（ｍ））＝｛｛経路，経路２｝，｛経路１，経路３｝，｛経路２，経路３｝｝
【０５２３】
手順４：補助記憶部３に格納された各経路集合について、完全条件１，２，３を満足するものは以下のとおりであり、これらを補助記憶部１に格納する。その結果を図１８のテーブル１８０１に示す。
【０５２４】
｛｛経路１，経路３｝，｛経路２，経路３｝｝
【０５２５】
手順５：手順４で完全条件３を満足するが完全条件１または２を満足しない拡張タイセット候補は以下のとおりであり、これを補助記憶部２に格納する。その結果を図１９のテーブル１９０１に示す。
【０５２６】
（経路１，経路２）
【０５２７】
手順６：経路数ｍ＝ｍ＋１＝２として、手順２（手順２’）に進む。
【０５２８】
手順２’：補助記憶部２のデータよりＮＥＴ（２）はφでないので、手順３（手順３’）に進む。
【０５２９】
手順３’：ｇ（ＮＥＴ（ｍ））を以下のように生成し補助記憶部３に書き込み、手順４（手順４’）に進む。その書き込み結果を図２０のテーブル２００１に示す。
【０５３０】
ｇ（ＮＥＴ（ｍ））＝｛｛経路１，経路２，経路３｝｝
【０５３１】
手順４’：経路数ｍ＋１の完全な経路集合は存在しないので、補助記憶部１には何も格納しない。そして、手順５（手順５’）に進む。
【０５３２】
手順５’：ＮＥＴ（ｍ＋１）＝ＮＥＴ（３）＝φであり、補助記憶部２には何も格納しない。その後、手順６（手順６’）に進む。
【０５３３】
手順６’：手順２（手順２’’）に進む。
【０５３４】
手順２’’：補助記憶部２のデータ（図１９のテーブル１９０１）より、ＮＥＴ（３）＝φであり、処理を終了する。
【０５３５】
結果として、補助記憶装置１に、図１８のテーブル１８０１に示すデータが残り、経路数１，２の完全な経路集合は以下のとおりとなる。
【０５３６】
｛経路４｝，｛経路１，経路３｝，｛経路２，経路３｝
【０５３７】
これらから、拡張タイセットは、以下のとおりとなる。
【０５３８】
｛６｝，｛１，３，４，５｝，｛１，２，３，４｝
【０５３９】
このデータ（拡張タイセット）を用いて、信頼性計算実行部８では以下の計算をする。
【０５４０】
Ｐｒ（Ｃ（Ｎ）≧２００）＝Ｐｒ（「通信網構成要素６が正常］、
または「通信網構成要素１，３，４，５が正常」、
または「通信網構成要素１，２，３，４が正常」）
【０５４１】
これは、上述の公知文献（Ｗ．Ｇ．Ｓｃｈｎｅｅｗｅｉｓｓ，ＢＯＯＬＥＡＮ  ＦＵＮＣＴＩＯＮＳ，Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ  Ｂｅｒｌｉｎｅ  １９８９．）に記載の技術を用いて下記の通りに求めることができる。尚、下記の式において、ｑｉは通信網構成要素ｉが故障する確率、ｐｉは通信網構成要素ｉが正常である確率である。
【０５４２】
ｐ６＋q６（ｐ１ｐ３ｐ４ｐ５＋q５ｐ１ｐ２ｐ３ｐ４）＝０.９９９＋０.００１（０.９９９４＋０.００１×０.９９９４）＝O．９９９９９７０
【０５４３】
以上、各図を用いて説明したように、本例では、通信網を構成する通信網構成要素（交換装置、伝送装置、ケーブル等）と、通信網構成要素からなる経路、正常に機能する経路によって確保される通信容量、各構成要素の故障確率のそれぞれが予め知られているときに、これらの情報を用いて、当該通信網の通信網構成要素間に通信網が正常に機能しているとみなすしきい値以上の通信容量を伝送することができる確率を高速に計算することにより、当該通信網の信頼性を高速計算する。
【０５４４】
具体的には、通信網を構成する通信装置やケーブル等の各通信網構成要素を番号付けして記憶装置に記憶し、情報を送信する際にどの通信網構成要素を経由するかを示す通信のための１以上の経路を番号付けして記憶装置に記憶し、さらに、正常に機能している通信網構成要素から成る経路によって送信される情報の量（通信容量）および通信網構成要素の故障確率を予め記憶装置に記憶しておき、以下のようにして、通信網が故障により段階的に送信できる情報量が劣化しても、あるしきい値α以上の通信容量が確保される確率を導出する。
【０５４５】
すなわち、プログラムされたコンピュータにより通信網の信頼性評価を行う通信網信頼性評価装置であって、通信網を構成する各通信網構成要素に予め付与された識別情報（番号）と各通信網構成要素に予め設定された故障確率、および、予め定められた各通信網構成要素の組み合わせからなる通信経路（「経路」）の識別情報（番号）と当該経路に含まれる各通信網構成要素の識別情報（番号）とを対応付けた集合情報、ならびに、予め、正常に機能している通信網構成要素からなる経路で送信される情報の量（通信容量）を記憶部１１（第１の記憶手段）に記憶しておき、全ての経路からなる集合の部分集合（経路集合）の一つ一つについて、拡張タイセット生成部７が、まず、記憶部１１に記憶した通信容量を参照して、当該経路集合に含まれる経路によって所定の通信容量が確保されること（完全条件１）の確認と、当該経路集合を構成する経路が正常であった場合に、当該経路集合に含まれない経路が正常に機能するという現象が発生しないこと（完全条件２）の確認、および、当該経路集合が、完全条件１および完全条件２を満足する真の部分集合を含まないこと（完全条件３）の確認を行い、これらの完全条件１，２，３を満足する経路集合を特定して補助記憶部１（第２の記憶手段）に記憶し、この補助記憶部１に記憶した経路集合に含まれる経路を構成する通信網構成要素を記憶部１１を参照して特定し、特定した通信網構成要素から、第１，第２の拡張タイセット条件（第１の拡張タイセット条件：当該拡張タイセットに含まれる全ての通信網構成要素が正常であれば、通信網において、しきい値以上の通信容量を確保することができる。第２の拡張タイセット条件：当該拡張タイセットに含まれる通信網構成要素が一つでも故障すれば、通信網において、しきい値以上の通信容量を確保することができない。）を満足する通信網構成要素の集合（拡張タイセット）を全て生成して補助記憶部４（第３の記憶手段）に格納し、信頼性計算実行部８が、記憶部１１から、補助記憶部４に格納した拡張タイセットに含まれる通信網構成要素に対して予め設定された故障確率を読み出し、読み出した故障確率を用いて、少なくとも一つの拡張タイセットに含まれる全ての通信網構成要素が正常に機能する確率を求め、制御部５とディスプレイ表示部９，表示メモリ１２、ＣＲＴ１３からなる出力手段が、信頼性計算実行部８が求めた確率を、当該通信網において上記しきい値以上の通信容量が確保される確率として出力する。
【０５４６】
また、拡張タイセット生成部７は、各経路集合について完全条件１，２，３を確認する際、当該経路集合に含まれる経路の数の少ない経路集合から確認を開始し、完全条件１，２，３の条件を満足しなかったとしても、完全条件３を満足する経路集合については、当該経路集合が含む経路の識別情報を記憶しておき、当該経路集合が含む経路の数を逐次増やして完全条件１，２，３を確認することで、確認作業の効率化を図る。
【０５４７】
このように、本例によれば、通信網の信頼性を、完全な経路集合を列挙して、そこから拡張タイセットを生成し、拡張タイセットが少なくとも一つ存在する確率として求めることができる。
【０５４８】
拡張タイセットは通信網構成要素の集まりであるが、通信網構成要素に比べて、より数の少ない経路の集まりについて完全条件１，２，３を満足するかどうかを確認することで、手順の簡略化を実現することができる。
【０５４９】
また、完全条件１，２，３を満足する経路集合を列挙するに当たり、小さな経路数の経路集合から順次経路を付加し、完全性を確認するが、それ以上経路を付加しても完全とならない経路集合を除いておくことで、手順の効率化を図っている。
【０５５０】
また、経路を付加することで完全となり得る経路集合が存在しなければ、手順を停止することで、無駄な手順実行を避けることができ、高速に完全な経路集合を列挙することができる。
【０５５１】
このようにして、通信網構成要素の故障確率から、Ｐｒ（Ｃ（Ｎ）≧α）を効率的に求めることができ、現実的な経路、通信容量を考慮した上での、通信網の信頼性の計算を、簡略した手順で効率的に行うことができる。
【０５５２】
尚、本発明は、各図を用いて説明した例に限定されるものではなく、その要旨を逸脱しない範囲において種々変更可能である。例えば、本発明は、図８〜図１０に示される構成の通信網のみに適用されるものではなく、さらに大規模な通信網に対しても適用可能である。
【０５５３】
また、本例では、補助記憶部１〜４および記憶部１１のそれぞれは、ＨＤＤ（Ｈａｒｄ  Ｄｉｓｋ  Ｄｒｉｖｅ）や主メモリ等の記憶装置と、当該記憶装置とのデータの入出力処理をプログラムに基づき実行するＣＰＵとで実現される機能として記載したが、補助記憶部１〜４および記憶部１１のそれぞれを記憶装置そのものとし、データの入力処理は、図示しないＯＳ（Ｏｐｅｒａｔｉｏｎｇ  Ｓｙｓｔｅｍ）を介して実行するアプリケーションプログラムに基づくＣＰＵの処理機能として実現することでも良い。
【０５５４】
また、本例のコンピュータ構成例に関しても、キーボードや光ディスクの駆動装置の無いコンピュータ構成としても良い。また、本例では、光ディスクを記録媒体として用いているが、ＦＤ（Ｆｌｅｘｉｂｌｅ  Ｄｉｓｋ）等を記録媒体として用いることでも良い。また、プログラムのインストールに関しても、通信装置を介してネットワーク経由でプログラムをダウンロードしてインストールすることでも良い。
【図面の簡単な説明】
【０５５５】
【図１】従来の第１の通信網構成例（経路が一つしかない場合）を示すブロック図である。
【図２】従来の第２の通信網構成例（二つの経路が割り当てられている）を示すブロック図である。
【図３】従来の第３の通信網構成例（通信容量を分割して収容した場合と、予備の経路による救済を行った場合）を示すブロック図である。
【図４】従来の第４の通信網構成例（複雑な通信網構成）を示すブロック図である。
【図５】従来の第５の通信網構成例（グラフ表現）を示すブロック図である。
【図６】従来の第６の通信網構成例（故障が発生した場合、グラフ表示では通信可能と見えるが実際には通信不可能となる例）を示すブロック図である。
【図７】従来の第７の通信網構成例（故障が発生した場合、グラフ表示では通信可能と見えるが実際には通信不可能となる例）を示すブロック図である。
【図８】本発明を適用する第１の通信網構成例（通信網の詳細定義）を示すブロック図である。
【図９】本発明を適用する第２の通信網構成例（通信網の詳細定義）を示すブロック図である。
【図１０】本発明を適用する第３の通信網構成例（完全条件２の説明）を示すブロック図である。
【図１１】本発明に係る通信網信頼性評価を実施する装置の構成例を示すブロック図である。
【図１２】図１における記憶部（１１）で記憶される情報例を示す説明図である。
【図１３】図１における補助記憶部（１）で記憶される第１の情報例を示す説明図である。
【図１４】図１における補助記憶部（４）で記憶される情報例を示す説明図である。
【図１５】図１における補助記憶部（１）で記憶される第２の情報例を示す説明図である。
【図１６】図１における補助記憶部（２）で記憶される第１の情報例を示す説明図である。
【図１７】図１における補助記憶部（３）で記憶される第１の情報例を示す説明図である。
【図１８】図１における補助記憶部（１）で記憶される第３の情報例を示す説明図である。
【図１９】図１における補助記憶部（２）で記憶される第２の情報例を示す説明図である。
【図２０】図１における補助記憶部（３）で記憶される第２の情報例を示す説明図である。
【符号の説明】
【０５５６】
１〜４：補助記憶部、５：制御部、６：通信容量計算部、７：拡張タイセット生成部、８：信頼性計算実行部、９：ディスプレイ表示部、１０：キーボード（「ＫＥＹ」）、１１：記憶部、１２：表示メモリ、１３：ＣＲＴ、１２０１〜２００１：テーブル。
【図１】
2008124875.tif 000003
【図２】
2008124875.tif 000004
【図３】
2008124875.tif 000005
【図４】
2008124875.tif 000006
【図５】
2008124875.tif 000007
【図６】
2008124875.tif 000008
【図７】
2008124875.tif 000009
【図８】
2008124875.tif 000010
【図９】
2008124875.tif 000011
【図１０】
2008124875.tif 000012
【図１１】
2008124875.tif 000013
【図１２】
2008124875.tif 000014
【図１３】
2008124875.tif 000015
【図１４】
2008124875.tif 000016
【図１５】
2008124875.tif 000017
【図１６】
2008124875.tif 000018
【図１７】
2008124875.tif 000019
【図１８】
2008124875.tif 000020
【図１９】
2008124875.tif 000021
【図２０】
2008124875.tif 000022