锐客网

  1. 首页 > it技术 > >

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

#

【平面图】 对于一个图 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固件(附带虚拟机)