大图中子图的可测性质

对于给定的距离参数ε,性质测试算法A需以高概率正确地区分给定的对象具备预定性质Π与ε-远离性质Π。若存在Π的测试算法A满足其询问复杂性独立于规模参数n,则称Π是可测的。设H是一个图,性质H-free为不含H-子图的图所构成的集合。在有界度模型中,Goldreich与Ron证明了对任意连通图H,性质H-free是可测的[9]。在邻接矩阵模型中,证明了对任意图H,不管其连通与否,性质H-free是可测的。