缺陷（图论）

缺陷是图论中的一个概念，用于完善与图中完美匹配有关的各种定理，如霍尔的婚姻定理。这是由厄伊斯坦-奥雷首先研究的。一个相关的属性是盈余。剩余的定义让G=（V，E）是一个图，让U是一个独立的顶点集，也就是说，U是V的一个子集，其中没有两个顶点被边连接。让NG(U)表示U的邻居集合，它由'V'中与U的一个或多个顶点有边连接的所有顶点组成。缺陷和匹配如果def(G;X)=0，这意味着对于X的所有子集U，|NG(U)|≥|U|。因此，根据霍尔婚姻定理，G承认一个完全匹配。相反，如果def(G;X)>0，这意味着对于X的某些子集U，|NG(U)|<|U|。因此，根据同一定理，G不承认完美匹配。此外，利用缺陷的概念，可以说明霍尔定理的一个定量版本。定理--每个双边图G=(X+Y,E)都有一个匹配，其中X的顶点最多只有def(G;X)是不匹配的。证明。让d=def(G;X)。这意味着，对于X的每个子集U，|NG(U)|≥|U|-d。在Y中加入d个假顶点，并将每个假顶点连接到X的所有顶点。根据霍尔婚姻定理，新图允许一个匹配，其中X的所有顶点都是匹配的。现在，通过删除d个假顶点来恢复原图；这就使得X的顶点最多只有d个没有被匹配。这个定理可以等效地表述为。紧集是X的一个子集，其缺额等于整个图的缺额（即等于xxx值）。紧集的交集和并集都是紧的；这是由上界超模集函数的属性得出的。在一个非偶数图中，一般来说，缺失函数不是超模的。

如果霍尔婚姻定理对一个图G来说是成立的，即如果G有一个完全匹配或一个具有正缺失的顶点集，那么该图就具有霍尔属性。如果def(G)=|V|-2ν(G)，则图具有强霍尔属性。很明显，强霍尔属性意味着霍尔属性。双边图有这两个属性，但是也有一些非双边图具有这些属性。特别是，当且仅当一个图是稳定的--其xxx匹配大小等于其xxx分数匹配大小时，它才具有强霍尔属性。

盈余V的一个子集U的盈余定义为。surG(U):=|NG(U)|-|U|=-defG(U)图G对子集X的剩余是由X的非空子集的最小剩余定义的。sur(G;X):=min[U是X的非空子集]surG(U)注意对非空子集的限制：如果没有这个限制，所有图形的盈余总是0。def(G;X)=max[0,-sur(G;X)]。在一个二方图G=（X+Y，E）中，盈余函数是一个子模集函数：对于X的每两个子集X1，X2。剩余紧集是X的一个子集，其剩余等于整个图的剩余（即等于最小）。具有非空交点的紧集的交集和并集都是紧的；这是由下限子模集函数的属性得出的。