Cut-Set

cut-set也叫cocycle。任取一个支撑树，树上的边称为branch，图里其他的边称为chord。

任何一个cut-set必然包含任何一个支撑树的至少一条边。反过来，连通图$G$里的任何一个最小集合，如果这个集合包含所有支撑树的至少一条边，这个最小集合是一个cut-set。

任何一个cut-set必然包含任何一个cycle的偶数个边。

任取一个支撑树$T$，$b$为$T$的任何一个边，显然$\{b\}$是$T$的cut-set，$\{b\}$把图的顶点分为两部分，考虑整个图的一个cut-set，把图的顶点分成同样的两部分，而且这个cut-set只包含$T$的一个branch，其他的都是chord，这个cut-set称为fundamental cut-set respect to $T$。

支撑树$T$的任意一个边对应了唯一的一个fundamental cut-set。

对偶性，Fundamental cut-set和Fundamental cycle的关系，我们知道任选一个chord对应了一个Fundamental cycle，这个cycle上的边除了一个chord其他的是branch。进一步的每个branch对应了一个Fundamental cut-set，这个cut-set包含一个branch，其他都是chord。

一个cut-set respect两个顶点$v_1, v_2$意思是这个cut-set吧两个顶点分在两个不同的集合里。

Network Flows

一个weighted无向图，上面的cut-set的capacity是这个cut-set里的所有边的weight的和。

定理：$v_1, v_2$之间的最大可能flow等于所有的respect这两个顶点的cut-set里capacity最小的。