临界边查看源代码讨论查看历史

临界边(critical edge)是图论的基本概念之一，临界边是这样的边：从一个图上去掉它之后，能使所得图的点覆盖数减小。设e是G上一条边，若点覆盖数β(G-e)<β(G)，则称e是G的关于点覆盖的临界边，简称临界边。若G的每一条边都是关于点覆盖的临界边，则称G为关于点覆盖的边临界图

[]

相关概念

点覆盖数 覆盖(covering)是数学的一个重要概念，这里指一类节点子集，具体地说，图的一个节点子集使该图的每一条边都与这个子集中一个节点关联，称这样的节点子集为覆盖集，也称点覆盖集，简称覆盖。图G的最小覆盖，也称最小点覆盖，是指在图的所有覆盖中，节点数最少的覆盖。G的最小覆盖的节点数称为G的覆盖数，或点覆盖数，常记为β(G)。一个图称为覆盖临界图，或点覆盖临界图，若从这图上去掉任何一条边后，所得的图的覆盖数都小于原图的覆盖数。设有一个最小覆盖M，若对于它的任何一个子集M′，与M′中节点相邻的不在M中的节点的数目总不比M′的节点数少，则称M为一个外部最小覆盖或外最小点覆盖，不是任何一图都有外最小覆盖。事实上，一个图有外最小覆盖当且仅当它有一个点核，或边核。

点核 点核(vertex core)是图论的一个重要概念，指图的一个子图，由图G的基数与G的边覆盖数相等的所有独立集的并所产生的节点导出子图，称为G的点核。并非所有的图都存在点核，由G的基数与G的点覆盖数相等的所有边独立集的并所产生的边导出子图，称为G的边核。同样，并非所有的图都有边核。但已证明：一个图有点核当且仅当它有边核；且它们都与存在外最小覆盖等价

定义

图G的一个匹配M称为G的一个边独立集，G的最大匹配所含的边数称为G的边独立数或匹配数。记为。

在一个图中，如果删除一条边将使得独立数增加，则称该边是临界的，对于一对不相邻的顶点，如果添加一条边把它们连接起来将会使得独立数增加，则称这一对顶点是准-临界的。

注：边独立集与点覆盖有密切关系，由于任意一个顶点不能覆盖边独立集中的两条边，因此图有大的边独立集，就有大的点覆盖集。另一方面，边独立集中不同的边不能用同一个顶点覆盖，因此图G中任何点覆盖集所含的点数不会小于任何边独立集含的边数。