Question

运筹学图论截集

运筹学的图论里，什么是截集？书上说的太拗口，有没有简单易懂的解释

Answer 1

对于一个有向图，将其点集合分成两个非空点集合，发点和收点分别属于这两个集合。将这样的弧称为一个截集：两点分别在前面划分的点集合里，且由发点所在的点集合指向收点所在的点集合。换句话说，连接两个非空点集合的弧，且有发点所在指向收点所在集合，称为一个解集。
解集的概念是为了找到一个有向图中最窄的瓶颈，这一点会帮助理解这个概念。