檢視割边的原始碼

'''割边'''假设有连通图G，e是其中一条边，如果G-e是不连通的，则边e是图G的一条割边。此情形下，G-e必包含两个[[连通分支]]。<ref>[https://zhuanlan.zhihu.com/p/42281156 图的割点和割边]知乎</ref>
{| class="wikitable" style="float:right; margin: -10px 0px 10px 20px; text-align:left"
|<center><img src=" https://i02piccdn.sogoucdn.com/18ad4194e925ffc3   " width="180"></center><small>[]</small> 
|}
== 边割 ==
[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），通常记作。
==参考来源==
{{Reflist}}
[[Category:330 物理学总论]]