科研之友
微信
新浪微博
Facebook
分享链接
摘要
Dinits-Karzanov-Lomonosov showed that it is possible to encode all minimal edge cuts of a graph by a tree-like structure called a cactus. We show here that minimal edge cuts separating ends of the graph rather than vertices can be "encoded" also by a cactus. As a corollary, we obtain a new proof of Stallings' ends theorem. We apply our methods to finite graphs as well and we show that several types of cuts can be encoded by cacti.
- 出版日期2014-2
