图论中,(cut)是将图的顶点分为两不交子集划分[1]割确定了割集,是两端分别在两子集中的边集,称这些边跨过(cross)了割。连通图中,割集唯一确定一个割,识别割有时是通过割集,而非顶点划分。

网络流中,s–t割指使得源与汇不在同一子集的割,其割集只含源一侧到汇一侧的边。s-t割的容量(capacity)定义为割集中所有边的容量和。

定义

是将图的顶点V分为两子集ST的划分。 割割集是一端点位于S、另一端点位于T的边的集合。 令st是图G的两顶点,则s–t是使得s属于St属于T的割。

在无权无向图中,割的大小(size)或权(weight)是跨过割的边数。加权图中,割的(value)或(weight)是跨过割的边的权重之和。

(bond)是真子集中没有其他割集的割集。

最小割

一个最小割。

最小割的大小或权不大于其他割。右图展示了最小割,其大小为2,且没有大小为1的割,因为这张图没有

最大流最小割定理指出,最大网络流等于分割了源汇的最小割的割边权重之和。有一些多项式时间方法可以解决最小割问题,最知名的是埃德蒙兹-卡普算法[2]

最大割

一个最大割。

最大割的大小或权不小于其他割。右图展示了最大割,其大小为5,且没有大小为6的割(即边的总数,写作),因为这张图不是二分图(有奇环)。

一般来说,找最大割是很难计算的。[3] 最大割问题是卡普的二十一个NP-完全问题之一,[4] 也是APX问题之一,这是说除非P = NP,否则不会存在多项式时间复杂度的近似方法。[5] 不过,可以用半正定规划,将其逼近到恒定的近似比[6]

注意从线性规划的意义上讲,最小割与最大割问题虽然可以通过改换目标函数的min、max使其变为另一个问题,但不是对偶的:最小割问题的对偶实际上是最大流问题。[7]

最疏割

最疏割(sparsest cut)使跨过割的边数对割的较小一侧的顶点数之比最小,目标函数偏向稀疏(跨过割的边更少)与平衡(接近二分)。这是NP问题,已知的最佳近似算法是近似,见Arora,Rao & Vazirani (2009)[8]

割空间

无向图的所有割的族(family)称作图的割空间(cut space),在算术模2的二元有限域上形成向量空间,以两割集的对称差为向量加法,是环空间正交补[9][10]若给边赋予正权重,割空间的最小权可由与图同顶点集的描述,称作最小割树[11]树的边都关联于原图的键,两节点st之间的最小割也就是与树中st的路径相关联的键中权最小的键。

另见

参考

  1. . networkx.algorithms.cuts.cut_size. [2021-12-10]. (原始内容存档于2021-11-18). A cut is a partition of the nodes of a graph into two sets. The cut size is the sum of the weights of the edges “between” the two sets of nodes.
  2. Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford, 2nd, MIT Press and McGraw-Hill: 563,655,1043, 2001, ISBN 0-262-03293-7.
  3. Garey, Michael R.; Johnson, David S., , W.H. Freeman, A2.2: ND16, p. 210, 1979, ISBN 0-7167-1045-5.
  4. Karp, R. M., , Miller, R. E.; Thacher, J. W. (编), , New York: Plenum Press: 85–103, 1972.
  5. Khot, S.; Kindler, G.; Mossel, E.; O’Donnell, R., (PDF), : 146–154, 2004 [2019-08-29], (原始内容存档 (PDF)于2019-07-15).
  6. Goemans, M. X.; Williamson, D. P., , Journal of the ACM, 1995, 42 (6): 1115–1145, doi:10.1145/227683.227684可免费查阅.
  7. Vazirani, Vijay V., , Springer: 97–98, 2004, ISBN 3-540-65367-8.
  8. Arora, Sanjeev; Rao, Satish; Vazirani, Umesh, , J. ACM (ACM), 2009, 56 (2): 1–37, S2CID 263871111, doi:10.1145/1502793.1502794.
  9. Gross, Jonathan L.; Yellen, Jay, , 2nd, CRC Press: 197–207, 2005, ISBN 9781584885054.
  10. Diestel, Reinhard, , , Graduate Texts in Mathematics 173, Springer: 23–28, 2012.
  11. Korte, B. H.; Vygen, Jens, , , Algorithms and Combinatorics 21, Springer: 180–186, 2008, ISBN 978-3-540-71844-4.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.