图填充(packing),理学-数学-图论-特殊图,设是一图族,一个图的一个-填充(-packing)就是与图族中的某图同构的两两点不交的的子图的集合。称的一个点被-填充覆盖(covered),如果它属于-填充的一个子图。特别地,若,那么称一个-填充为一个-填充。由于在一个图的边集和与同构的此图的子图组成的集合之间是有一个自然的对应,因此很容易得出一个图的每一个-填充都对应的一个匹配,反之亦然。一个填充的大小(size)是指被这个填充覆盖的点的个数。的填充中大小最大的-填充称为的最大-填充(maximum-packing)。如果-填充覆盖的所有点,那么它就是的一个完美-填充(perfect-packing)或者-因子(-factor)。图填充理论是匹配理论的推广,对于无向图的图填充问题的研究已经得出很多多项式时间算法以及一些NPC的结果。接下来介绍有向图的图填充问题的一些概念。一个有向图的一个有向-填充(directed-packing)就是与图族中的某有向图同构的两两点不交的的子图组成的集合。称的一个点被有向-填充覆盖(covered),如果它属于有向-填充的一个子图。