分類の基準

本章では，エッジ数一定のネットワークを分類し，分類されたネットワークの 全点間信頼度の大小比較を行い，最大全点間信頼度を求める．

ここで，本章で分類されるネットワークを図示する際，図中のノードを繋ぐ線 は，複数のエッジが直列で連結されたエッジ集合を表すものとする．図 3-1-1の 右のネットワークにおいて次数が2のノードは，左のネットワークのように省略 し，そのノードが直列に連結しているエッジ集合_E^hは 1 本のエッジとして表記 するものとする．

次に，図3-1-2に示したネットワーク_xとxを考える．この2つのネットワーク

は，エッジ集合E¹とE²の配置のみが異なり，その他の要素は同一なネットワー クである．_xとxのE¹とE²は，それぞれ同じ本数のエッジで構成される．ここ で，_xとxの全ノードが連結する事象をそれぞれY,Y，エッジ集合E¹の全ての エッジが稼働している事象をF¹，i1,2,3,,E(1)に対しE¹のうちi本のエッジが 故障している事象をF_i¹とする．ただし，i₂のときPr{Y|F_i¹}0となることに注

50

意されたい．このとき，_xとxの全点間信頼度は下記で表される．

} Pr{

}

| Pr{

} Pr{

}

| Pr{

)

( Y F¹ F¹ Y F₁¹ F₁¹

R x  

} Pr{

}

| Pr{

} Pr{

}

| Pr{

)

( Y F¹ F¹ Y F₁¹ F₁¹

R x    

上 記 の 2 式 に お い て ， Pr{Y|F¹}Pr{F¹}Pr{Y|F¹}Pr{F¹} ， 0

}

| Pr{

}

|

Pr{Y F₁¹  Y F₁¹  より，R(x)R(x)となる．このことは，ネットワーク のエッジ集合の端点に次数1のノードがある場合，そのネットワーク構成より全 点間信頼度が高くなる構成が存在することを意味する．よって，本論文では，エ ッジ集合E^hの端点に次数 1 のノードが存在するネットワークは信頼度の大小比 較の候補として考えないものとする．

図3-1-1 ネットワーク中のエッジ集合E^h

図3-1-2 エッジ集合E^hの配置

51

図3-2 サイクルの概念

本論文では，ネットワークを分類するための基準をネットワークの分類指標と 呼ぶこととし，ネットワークの分類指標として，隣接サイクル数[61]を提案する．

本章におけるサイクルとは，全て異なるノードが連結された閉歩道となるグラフ

（部分ネットワーク）を意味し，内部に他のサイクルを含まないものとする．ネ ットワーク G に複数のサイクル _Si （_{i1,2,,U}, U はサイクル数）が存在す る場合，あるサイクルS₁に注目したとき，S₁とエッジ集合を共有し，隣り合って いるS₁以外のサイクルを隣接サイクルとする．図3-2に例を示す．図のネットワ ークは，_S1,S2,S3の 3 つのサイクルを持つネットワークである．サイクルの内部 にサイクルを含むものはサイクルとして考えないので，Sのような複数サイクル の外側を囲むサイクルは数えないものとする．

図 3-2 のサイクルS₁がエッジ集合を共有している隣接サイクルは_S2,S3の 2 つ である．次にサイクルS₂と_S3の隣接サイクルは，ともにS₁で1つである．また，

U

i1,2,, に対しサイクル_Siの隣接サイクル数を_siとする．さらに，_siには一 般性を失うことなく次の大小関係があるものとする．

sU

s s

s₁ ₂ ₃

このとき，サイクル_Si は隣接サイクルとして_Si を有することはないので，

1U 1

s が成立する．また，様々な隣接サイクル数の組み合わせを考えた時にs₁ が取り得る最大値を_smaxとし，表3-1に_smaxとUの値をまとめた．

52

表3-1 サイクル数と隣接サイクル数

エッジ数 U s_max

1

n

k 0 -

n

k  1 0

1

n

k 2 1

2

n

k 3 2

3

n

k 4 3

3.3.2 ネットワークの分類

考え得る隣接サイクル数s_iの値の組み合わせにより，kn1,n2,n3にお いて構成可能なネットワークを列挙する．ここで，s_iについて以下の性質を示す．

性質3-1



 U

i

si 1

が奇数であるネットワークは存在しない．

性質3-2



^{i s s i U}



I # | _i _max, 1,2,, とする．このとき，iI,I1,,Uにおいて1つで もs_i I を満たす場合，そのネットワークは存在しない．

性質3-3

エッジ数kのネットワークにおいて，s_i (iU)の組み合わせが，既知のエッジ 数k1のネットワークと同じとき，s_U 0であれば，そのネットワークは存在し ない．s_i (iU)の組み合わせが，エッジ数k1のネットワークと異なる場合，

0

sU であればネットワークは存在しない．

性質3-1，性質3-2，性質3-3を利用し，列挙したs_iの組み合わせにおいて，ネ

ットワークの存在有無を検討する．性質3-1，性質3-2，性質3-3のいずれかによ って存在しないと判定されたs_iの組み合わせには，その根拠を表の判定項目に

(1),(2),(3)で示す．いずれの性質にも該当しない組み合わせについては，T_k^tとして

図3-3から図3-5にその各タイプT_k^tを示す．以下の表3-2から表3-4において，s_i にはs₁ s₂ s₃s_Uの大小関係があるものとする．

53

1) k n1の場合

表3-2 隣接サイクル数によるネットワークパターン(k n1)

パターン s₁ s₂ 判定

1 1 1 T_n²_1

2 1 0 (1)(2)

3 0 0 T_n¹_1

図3-3 k=n+1のネットワーク

1

n

k のとき，図3-3(a)と(b)に示したT_n¹_1とT_n²_1の2種類のネットワークが構 成可能である．表 3-2 における，隣接サイクル数(s₁,s₂)(1,0)の組み合わせを持 つネットワークは，性質3-1と性質3-2から存在しない．

54

2) kn2の場合

表3-3 隣接サイクル数によるネットワークパターン(k n2)

パターン s₁ s₂ s₃ 判定

1 2 2 2 T_n⁴_2

2 2 2 1 (1)(2)

3 2 2 0 (2)

4 2 1 1 T_n³_2

5 2 1 0 (1)(2)

6 2 0 0 (2)

7 1 1 1 (1)(3)

8 1 1 0 T_n²_2

9 1 0 0 (1)(3)

10 0 0 0 T_n¹_2

図3-4 k=n+2のネットワーク

2

n

k のとき，図3-4(a)，(b)，(c)，(d)に示したT_n¹_2，T_n²_2，T_n³_2，T_n⁴_2の4種 類のネットワークが構成可能である．

55

3) kn3の場合

表3-4 隣接サイクル数によるネットワークパターン(k n3)

s₁ s₂

s

₃ s₄ 判定 s₁ s₂

s

₃ s₄ 判定

1 3 3 3 3 T_n⁹_3 19 3 1 0 0 (2)

2 3 3 3 2 (1)(2) 20 3 0 0 0 (1)(2)

3 3 3 3 1 (2) 21 2 2 2 2 (3)

4 3 3 3 0 (1)(2) 22 2 2 2 1 (1)(3)

5 3 3 2 2 T_n⁸_3 23 2 2 2 0 T_n⁵_3

6 3 3 2 1 (1)(2) 24 2 2 1 1 T_n⁶_3

7 3 3 2 0 (2) 25 2 2 1 0 (1)(3)

8 3 3 1 1 (2) 26 2 2 0 0 (3)

9 3 3 1 0 (1)(2) 27 2 1 1 1 (1)(3)

10 3 3 0 0 (2) 28 2 1 1 0 T_n⁴_3

11 3 2 2 2 (1) 29 2 1 0 0 (1)(3)

12 3 2 2 1 T_n⁷_3 30 2 0 0 0 (3)

13 3 2 2 0 (1)(2) 31 1 1 1 1 T_n³_3

14 3 2 1 1 (1) 32 1 1 1 0 (1)(3)

15 3 2 1 0 (2) 33 1 1 0 0 T_n²_3

16 3 2 0 0 (1)(2) 34 1 0 0 0 (1)(3)

17 3 1 1 1 T_n¹⁰_3 35 0 0 0 0 T_n¹_3

18 3 1 1 0 (1)(2)

56

図3-5 k=n+3のネットワーク

3

n

k のとき，図3-5に示したT_n¹_3からT_n¹⁰_3の10種類のネットワークが構成可 能である．次にk n1,n2,n3の分類されたネットワークに対し，全点間信 頼度の大小を検討する．

3.3.3 ファクタリング法

本項では，k n1,n2,n3の分類されたネットワークに対し，全点間信頼度 の大小を検討する． エッジ本数kn2,n3のネットワークに対し，横田他[86]

はkn2のネットワークを4種類に分類，kn3のネットワークは9種類のタ イプに分類した．Kishihata他[32]は横田他[86]の分類をJanのアルゴリズムへ適用

57

し，その効率性について考察を行った．しかしながら，横田他[86]の比較結果は，

n

が小さくエッジ数kが比較的小さいときにしか適用できないという問題があっ た．そこで本章ではChen他[15], Xiao他[60]によるファクタリング法を用いた信 頼度の大小比較を適用する．

ファクタリング法は，全点間信頼度を計算する際に，第1章で述べたように計 算対象のネットワークよりエッジ数の少ないネットワークに変形する方法であ る．この手法は，全点間信頼度が既知であるネットワークに変換することで，計 算を容易にできる特徴がある．ネットワークの変換は，あるエッジの状態に注目 して行う．

ここで，kn3のネットワークにて，ファクタリング法の適用例を示す．図 3-6 のネットワーク

x

_n3は，E⁹の状態によって，ネットワーク

x ˆ

_n2と

x

_n2に変形 することができる．E⁹のエッジがすべて稼働する場合と，E⁹のエッジのうち 1 本のみが故障する場合に分け，E⁹のエッジがすべて稼働する確率をpc(E⁹)，E⁹ のエッジのうち1本のみが故障する確率をpd(E⁹)とすると，

x

_n3の全点間信頼度 は下記で計算できる．

) ( ) ( ˆ )

( ) ( )

( _n3  pc E⁹ R _n2  pd E⁹ R _n2

R x x x

ここで，図 3-6 のネットワーク

x ˆ

_n2の二重線で示したエッジ集合は，エッジ集 合のエッジがすべて稼働の状態，ネットワーク

x

_n2の点線で示したエッジ集合は，

エッジ集合のうち1本のみが故障の状態を表している．

このように，ネットワーク

x

_n3は，エッジ数の少ないネットワーク

x ˆ

_n2，

x

_n2で 表すことが可能である．

図3-6 ファクタリング法の例

58

3.3.4 ファクタリング法を用いた信頼度比較

3.3.2 項で示した各タイプT_k^tのネットワーク x^t_k の全点間信頼度の大小関係を

比較し，全点間信頼度が最大となる構成を検討する．

ここでkn1については，Jan[26]によりR(x¹_n1)R(x²_n1)の関係が成り立つこ とが示されている．

次にkn2の場合について下記の関係を導くことができる．

1) k n2の場合

2

Xn のネットワークは図3-4の4つのタイプに分類できる．ここで，それぞれ のネットワークの

(

tn2

)

R x

を，R(x^t_n1)，及び既知の全点間信頼度に分割し大小比 較を行う．

(1)T_n¹_2とT_n²_2について

図3-7にT_n¹_2とT_n²_2のファクタリング法による変形を示す．x¹_n2T_n¹_2，x²_n2T_n²_2 とする．x¹_n2のエッジ集合E⁶に注目し，E⁶のエッジがすべて稼働する場合と，

E6のエッジのうち 1 本が故障する場合に分ける．E⁶のエッジがすべて稼働す る場合は，E⁶のエッジがすべて稼働する確率がpc(E⁶)，変形したネットワー クの全点間信頼度はR(x¹_n1)pc(E⁵)となる．一方，E⁶のエッジのうち 1 本だけ が 故 障 す る 確 率 は p d(E⁶) ， 変 形 し た ネ ッ ト ワ ー ク の 全 点 間 信 頼 度 は ，

) ( ) ( ¹₁ pc E⁵

R x_n となる．T_n²_2のネットワークx²_n2についても同様に場合分けを行 う．よって2つのネットワークの全点間信頼度は下記で求められる．

)) ( ) ( )(

( )) ( ) ( )(

( )

( ¹ ₂ pc E⁶ R ¹ ₁ pc E⁵ pd E⁶ R ¹ ₁ pc E⁵

R x_n  x_n  x_n

)) ( ) ( )(

( )) ( ) ( )(

( )

( ² ₂ pc E⁶ R ² ₁ pc E⁵ pd E⁶ R ² ₁ pc E⁵

R x_n  x_n  x_n

これよりT_n¹_2とT_n²_2のネットワークについて，以下の関係が成り立つ．

) ( )

( ¹_n1 R ²_n1

R x x より，R(x¹_n2)R(x²_n2)

59

図3-7 x¹_n2とx²_n2の変形過程 (2)T_n²_2とT_n³_2について

図3-8に，T_n²_2とT_n³_2についてファクタリング法によるネットワーク変形を示 す．x²_n2T_n²_2，x³_n2T_n³_2とする．図 3-8 でx²_n2とx³_n2のE⁵の全エッジを稼働状 態としたとき，E⁵が結ぶノードは1つのノードとして考えることができる．E⁵ の両端のノードを1つにまとめてネットワークを変形すると，図3-8の同型の ネットワーク A，B になる．よって，2 つのネットワークの全点間信頼度は，

次式で計算される．

0 ) ( ˆ )

( ) ( )

( ²_2  pc E⁵ R ²_2  pd E⁵ 

R x_n x_n

) ( ) ( ˆ )

( ) ( )

( ³_n2  pc E⁵ R ³_n2 pd E⁵ R ²_n1

R x x x

これより以下の関係が成り立つ．

) ( )

( ²_n2 R ³_n2

R x x

60

図3-8 x²_n2とx³_n2の変形過程

(3) T_n³_2とT_n⁴_2について

図3-9に，T_n³_2とT_n⁴_2についてファクタリング法によるネットワーク変形を示 す．x³_n2T_n³_2，x⁴_n2T_n⁴_2とする．図 3-9 でx³_n2とx⁴_n2のE³の全エッジを稼働状 態としたネットワークxˆ³_n2とxˆ⁴_n2は，それぞれ図3-9の同型のネットワークA1 と B1 に変形できる．また，x³_n2とx⁴_n2のE³のうち 1 本だけが故障状態とした ネットワークはx¹_n1とx²_n1であり，E³を削除し整理するとネットワーク A2 と B2 のようになる．ここで，x¹_n1とx²_n1が取り得る全点間信頼度の最大値を比較 すると，

) ( max ) (

maxR x¹_n1  R x²_n1

となる．よって，2つのネットワークの全点間信頼度は，次式で計算される．

) ( ) ( ˆ )

( ) ( )

( ³_n2  pc E³ R ³_n2  pd E³ R ¹_n1

R x x x

) ( ) ( ˆ )

( ) ( )

( ⁴_n2  pc E³ R ⁴_n2  pd E³ R ²_n1

R x x x

61

図3-9 x³_n2とx⁴_n2の変形過程

これより以下の関係が成り立つ．

) ( )

( ³_n2 R ⁴_n2

R x x

全点間信頼度の比較は，図3-7から図3-9に示したようにネットワークを変形 しながら行う．以上の大小関係の比較から，次の定理が成り立つ．

定理3-1

2

n

k において，上記4タイプの信頼度の大小関係は以下のようになる．

3 , 2 ,

1

t に対して，

R(x

_n^t₊₂

) £ R(x

_n⁴₊₂

)

(3.1)

ドキュメント内 多目的ネットワークシステムの評価指標算出方法 に関する研究 (ページ 53-73)