边覆盖是一类覆盖,指一类边子集。具体地说,图的一个边子集,使该图上每一节点都与这个边子集中的一条边关联,只有含孤立点的图没有边覆盖,边覆盖也称为边覆盖集,图G的最小边覆盖就是指边数最少的覆盖,图G的最小边覆盖的边数称为G的边覆盖数,常记为β′(G)。[1]在图1(a)中,都是极小边覆盖,其中是最小边覆盖,。(b)中都是极小边覆盖,。设图,若,使得v与e相关联,则称e覆盖v,并称为边覆盖集,或简称边覆盖。设为边覆盖,若的任何真子集都不是边覆盖,则称是极小边覆盖。边数最少的边覆盖集称为最小边覆盖,其所含边的个数称为边覆盖数,记作,或简记为。[2]