路集是指在網路圖中,從節點1出發,經過一串弧序列到達節點2的弧序列。
路集,最小路集,
路集
在網路圖中,從節點v1出發,經過一串弧序列可以到達節點v2,則稱這個弧序列為從v1到v2的一個路集或一條路。一個路集中所有弧對應的單元都正常時,系統就能正常工作。
如右圖,系統的路集共16個:
{A1,A2 },{A3,A4},{A1,A2,A3 },{A3,A4,A5 },{ A1,A2,A4},{A1,A3,A4 },{A1,A2,A5 },{ A2,A3,A4},{A2,A3,A5 },{ A1,A4,A5},{ A1,A3,A4,A5},{A1,A2,A3,A4 },{A2,A3,A4,A5 },{ A1,A2,A3,A5},{A1,A2,A4,A5 },{ A1,A2,A3,A4,A5}
最小路集
如果在一條路集的弧序列中,任意除去其中一條弧後,它就不再是一條路集,則稱該路集為最小路集。最小路集可以表示一種可使系統正常工作的最少單元的集合,即每一個單元都是必不可少的,減少其中任意一個單元,系統就不能正常工作。
上圖中,最小路集共4個:
{A1,A2 },{ A3,A4},{A1,A4,A5 },{ A2,A3,A5}