#|图论 —— 网络流 —— 最小割 —— 平面图与对偶图

2022-01-02 #

【平面图】对于一个图 G=(V,E)，若其重画后，在平面任意两条边的交点除了图中点外，没有其他交点，那么这个图称为平面图
【#|图论 —— 网络流 —— 最小割 —— 平面图与对偶图】
文章图片

在平面图中，由边包围并且其中不含顶点的区域称为面
包围面 R 的所有边组成的回路称为面 R 的边界
回路长度称为面 R 的度，记为 deg(R)
具有相同边界的面称为相邻面
由平面图的边包围的无穷大的面称为外部面，一个平面图有且仅有一个外部面
所有面的度的和等于其边数 E 的两倍，即有：
文章图片

【对偶图】对于平面图 G=(V,E)，若图 G'=(V',E') 满足：

G 的任一一面 Ri 内有且仅有一点 vi'
对 G 的域 Ri 和 Rj 的共同边界 Ek，连接一条边 Ek'=(vi',vj') 且只与 Ek 交于一点
若共同边界 Ek 完全在域 Ri 中，那么 vi' 有一自环 Ek'

则称图 G' 为平面图 G 的对偶图

#|图论 —— 网络流 —— 最小割 —— 平面图与对偶图

文章图片

#|图论 —— 网络流 —— 最小割 —— 平面图与对偶图

文章图片

【平面图转对偶图】平面图与对偶图常应用于网络流中。
若网络流的图 G 能转换成一个平面图，那么有：

对偶图 G' 中的环对应平面图 G 中的割
平面图 G 的面数等于对偶图 G' 的点数，且 G 与 G' 的边数相同

利用最大流最小割定理转换模型，根据平面图 G 与对偶图 G' 的关系，若想求出 G 的最小割，那么令转换后的 G' 的每条边的长度等于他的容量，于是最小割的容量就等于最短路的长度。

推荐阅读

上一篇：新零售私享会精彩观点集萃|新零售私享会精彩观点集萃,一文读懂零售商业智能未来

下一篇：Win7虚拟机Docker构建ESP8266NodeMcu固件(附带虚拟机)