graph - 图论中的削减

Question

通常，割定义为图的子集。但是，我在某些地方读到必须连接剪辑中的所有节点。在这种情况下，所有子集都不能被切割。

1----2
 \   |\  
  \  | \ 
   \ |  \
    \|   \
4----3    \
|__________5

在这种情况下，集合 {3, 4, 5} 是不是切？（节点 4 和 5 未连接）

标签： graph

Answer 1

引用Reinhard Diestel 的图论研究生教科书，“割”的定义非常简单：

如果 {V1, V2} 是 V 的一个分区，则 G 的所有穿过这个分区的边的集合 E(V1, V2) 称为割。

注意：集合 S 的“分区”是完全覆盖 S 的一组不相交的 S 子集。

因此，如上所述，“切割”是一组边，而不是一组顶点。此外，没有要求 V1 或 V2 是连通子图。