割边查看源代码讨论查看历史

割边假设有连通图G，e是其中一条边，如果G-e是不连通的，则边e是图G的一条割边。此情形下，G-e必包含两个连通分支。

[]

边割

[edge cut]

设X，Y是图G 的两个顶点子集，E[X,Y]是G中所有一个端点属于 X 另一个端点属于Y的边构成的集合。当\X时，称E[X,Y]是 X 在 G 中的伴随边割（associated edge cut），通常记作。不难看出，此时。一般地，图 G 的边子集是 G 的边割当且仅当 G\的连通分支大于 G 的连通分支数。特别地，如果边割，则称 e 为 G 的割边。利用边割的概念，可以对二部图作如下的刻画：图 G 是二部图当且仅当 G 中存在顶点子集 X 使得。另外，图中某个顶点 v 的伴随边割称作平凡边割（trivial edge cut）。显然，这是所有与 v 关联的边构成的集合。图中一个极小的非空边割称作键（bond）。所谓极小，是指一个键的任意真子集都不是边割。图中一个边子集是该图的边割当且仅当它是该图中一些键的不交并。

在有向图中也可以定义类似的概念。设 D 是一个有向图，X，Y 是 D 的两个顶点子集，A（X，Y）是 D 中所有尾属于 X 头属于 Y 的弧构成的集合。当Y=V（D）\ X 时，称弧集A（X，Y）是 X 在 D 中的伴随出割（associated outcut），通常记作。而弧集A（Y，X）称作 X 在 D 中的伴随入割（associatde incut），通常记作。