单位区间图的配对k-DPC容错性问题

[目的]为研究不相交路径覆盖问题,在单位区间图上探讨1-不相交路径可覆盖、2-不相交路径可覆盖、k-不相交路径可覆盖在删除顶点和经过指定边后仍保持DPC性质的结构。[方法]利用单位区间图的结构特点以及路覆盖的结构性质,结合数学归纳法和反证法来研究单位区间图的配对多对多k-DPC容错性问题。[结果]单位区间图G任意删去p个点且经过q条边,仍是配对k-DPC,当且仅当G是(2k+r-1)-连通,其中(p+q)≤r。[结论]单位区间图的容错性路覆盖问题与哈密顿性质以及连通度有紧密联系。研究方法和研究结果为区间图配对k-DPC容错性问题的研究提供了理论依据,同时有助于设计在单位区间图上寻找配对k-DPC容错性的有效算法。