大家好，又见面了，我是你们的朋友全栈君。
平面图定义：
图存在一种形式，所有的边只在顶点处相交，那么这个图就是平面图。
对偶图定义：
对于每一个平面图， 都有与其相对应的对偶图. 我们假设上面的例图是图G， 与其对应的对偶图G*， 那么对于G*来说， G*上面的每一个点， 对应的是G里面的每一个面. 比如说下面就是G*.
上面的点就是对偶图G里的点.
那么关于对偶图G*里的边呢 ? 对于G中本来的每条边e， 他是两个面(比如说面f1和f2)的交边， 那么在对偶图里， 我们对这两个面(f1， f2)所映射在G*里的点连线(f1* 连向f2*). 如果f1 == f2(比如说G中5， 6这条边， 边的两侧都是同一个面， 那我们就建一条回边.
图就长这样(回边在5， 6那里).
求网络流的最小割或最大流时，如果时平面图，就可以转化成对偶图，然后对对偶图求s’,t’的最短路，就是原网络的最大流和最小割。就是对偶图的点需要自己对应好。。
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/141340.html原文链接：https://javaforall.net
