路集

最小路集

路集

在网络图中，从节点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}