日本オペレーションズ・リサーチ学会
2021年 秋季研究発表会

1-D-1

ランダム K-out-of-N システムを利用したグラフ信頼性
01604880 早稲田大学
01208666 （国研）産業技術総合研究所

はじめに毛利裕昭*竹下潤一

MOHRI Hiroaki
TAKESHITA Jun-ichi的とする．なお，連結グラフ G が非連結になった
とき，すなわちある異なる 2 頂点 u, v ∈ V (G) が
本稿では単純で連結な（無向）グラフ G =(V (G), E(G), ϕG ) の 信 頼 性 に つ い て 議 論 す る ． あって u と v 間に道が存在しなくなったとき，Gは故障したと考える．
V (G)(̸= ∅) の元を頂点とよび，E(G) の元を辺とよぶ．ただし，本稿では V (G), E(G) はともに有限2. 方針集合であると仮定する．ϕG は接続関数とよび，Gの辺に G の頂点対を対応させる．e ∈ E(G) で u, v
N 個のユニットで構成され, N 個のうち少なくが ϕG (e) = uv(= vu) である頂点であれば，u と vとも K 個のユニットが故障したときにシステム全を e の端点とよぶ．ここで，u と v の順は無視する． 体が稼働しなくなるシステムを K-out-of-N シス
また，両端点が一致する辺をループと，両端点が異テムとよぶ．通常 K は定数であるが，Ito et al. [3]なる辺をリンクという．G が単純であるとは，G がでは K が確率変数となるランダム K-out-of-N シ
ループを持たずかつ，G の任意の異なる 2 頂点間がステムが提案されている．
高々1 つのリンクで結ばれているときをいう．さらいま，与えられたグラフ G = (V (G), E(G))（たに，G の頂点と辺の交代列 W = v0 e1 v1 e2 · · · ek vk
だし |E(G)| = M ）に対して，各辺 e ∈ E(G) を（ただし，ei ∈ E(G) (i ∈ {1, . . . , k}) で ei のランダム K-out-of-N システムのユニットに対応
両端点は vi−1 と vi ．
）を G における歩道といい， させ，各辺が独立で同一の故障分布関数 F (t) を
e1 , . . . , ek , v0 , . . . , vk がすべて異なるとき W を持つと仮定する．このとき，K の分布関数 Pk :=道という．そして，G が連結であるとは，G の任P (K ≤ k) (k = 1, . . . , M ) は，M 本の辺から k
意の 2 頂点間に少なくとも 1 つ以上の道が存在す本選択した際にグラフが故障する確率となるため，るときをいう．
グラフ全体の故障分布を考えることとランダム Kグラフはネットワーク構造を表現できるため，グout-of-N システムの確率変数 K の分布関数を考
ラフを用いて電気網，水道網，交通網など様々なえることを同一視することが可能である．
インフラストラクチャーのモデル化を行い，それさらに Ito et al. [3] では，各ユニットが独立でらの信頼性評価に利用されることがしばしばある． 同一の故障分布関数を持っている場合に，ランダ
例えば，信頼性工学分野では特別な 2 頂点（シンム K-out-of-N システム全体の故障分布関数がクとソース）を持つシステムに関して，各頂点と( )N∑N
各辺がそれぞれ故障分布をもつ仮定のものでシスF(t) =Pk(1 − F (k))k F (t)N −k (1)k
テム全体の故障分布，平均故障時間や最適保全計
k=1
画について研究されている [1]．一方，離散シスであることも示している．これを利用すれば，グテム分野では各辺や各頂点が一定の確率で故障す
ラフ G に対応するランダム K-out-of-N システムる仮定のもとで，巨大グラフ全体の連結性やそれの確率変数 K の分布関数を求めることで，グラフを効率良く判定するアルゴリズムが研究されていG の故障分布関数を導出することが可能となる．
る [2]．しかし，各頂点や各辺がそれぞれ故障分布
3. 主結果をもつ仮定のもとで，グラフ全体の連結性を議論
まず次の用語を準備する．
している先行研究はあまりない．
そこで本稿では，連結グラフの辺のみが故障す
定義 1. u, v ∈ V (G) (u ̸= v) とし F ⊂ E(G) とするとし，各辺は独立で同一の故障分布を持つと仮る．このとき，定し，グラフ全体の故障分布を導出することを目1.

• 辺集合 F ⊂ G(G) が G の uv-非連結化集合であるとは，グラフ G − F 内に u と v 間の道が存在しないときをいう．
• 辺集合 F ⊂ G(G) が G の uv-カット集合であるとは，F が uv-非連結化集合でかつ，F の任意の真部分集合 F ′ が uv-非連結化集合ではないときをいう．
また，|F | = k のときサイズ k であるという．
ある連結グラフ H = (V (H), E(H) に辺を 1 本追加し連結グラフ G = (V (G), E(G)) を生成することを考えると，その生成手順は次の 2 通りに場合分けできる．
（図 1 を参照せよ．
）(i) グラフ H の頂点とグラフ H の頂点ではない新たな頂点を両端点とする辺をグラフ H に追加し，グラフ G を生成する．
(ii) グラフ H の異なる 2 頂点である辺の両端点となっていない 2 頂点を両端点とする辺をグラ
フ H に追加し，グラフ G を生成する．
(i)

G = (V(G), E(G)) | E(G) | = M

H = (V(H ), E(H ))v0e+| V(G) | = | V(H ) | + 1 = N + 1(ii)| V(H ) | = N| E(H ) | = M − 1v+e+v−| V(G) | = | V(H ) | = N

図 1: グラフ H に辺を 1 本追加しグラフ G を生成する 2 通りの手順例．
ケース (i) と (ii) それぞれに対して，グラフ G に対応する確率変数 K の分布関数を求める漸化式を導出する．以下では，グラフ H = (V (H), E(H))
を頂点数が |V (G)| = N ，辺数が |E(G)| = M −1 (M ≥ 2)，連結で単純であるとする．また，グラフ H に対応するランダム K-out-of-(M −1) システ
ムの確率変数 K の分布関数を PkH (k = 1, . . . , M −1) とする．
命題 2. 任意の v0 ∈ V (H) をとり，v0 と新たな頂点v + ̸∈ V (H) を両端点とする辺 e+ を考える．このとき，V (G) := V (H)∪{v + }，E(G) := E(H)∪{e+ }であるグラフ G に対応するランダム K-out-of-M
システムの確率変数 K の分布関数 PkG は
 [() ()] / (M )H M −1 + M −1
P

kkk−1kPkG =


if1,G < 1,1 ≤ j ≤ M − 1 and Pk−1

otherwise()となる．ただし， M0−1 = 1 と定める．

(2)

命題 3. 隣接していない異なる 2 頂点 v, u ∈ V (H)をとり，v と u を両端点とする辺 e+ を考える．このとき，V (G) := V H ，E(G) := E(G)∪{e+ } であるグラフ G に対応するランダム K-out-of-(M − 1)システムの確率変数 K の分布関数 PkG は] /( ) [()(M −1)
MHH
PkH Mk−1 + Pk−1−n
kk−1kGPkG =if 1 ≤ k ≤ M − 1 and Pk−1 < 1,
1, otherwise(3)Hとなる．ただし，nk はサイズ k − 1 の H-非連結化集合のうち「ある唯一の uv-カット集合 F ′ ⊂ FHがあって，FH \ F ′ は H-非連結化集合ではない」()
をみたすものの個数である. また，P0H M0−1 = 0と定める．
任意の単純で連結なグラフ G は，生成手順 (i)と (ii) を繰り返し用いることで生成することが可能である．そのため，命題 2 と命題 3 を繰り返し用いることで，任意の単純で連結なグラフ G が対応するランダム K-out-of-N システムの確率変数
K の分布関数を導出できる．最後に (1) を用いることで，グラフ G の故障分布関数を求めることができる．
当日の発表では主結果の略証を与えるとともに，簡単な例を示す予定である．

参考文献[1] R. Barlow and F. Proschan, Mathematical
Theory of Reliability, Wiley, 1965.
[2] C. Colbourn, The Combinatorics of Network
Reliability, Oxford University Press, 1987.
[3] K. Ito, X. Zhao, amd T. Nakagawa, Random
number of units for K-out-of-n systems, Appl.
Math. Model., 45 (2017), 563-572.