广义循环图彩虹支配问题的研究

摘要

图论不仅是组合数学的一个重要分支，而且还是离散数学的一个重要分支。图的彩虹支配及其相关问题，是近年来一个比较热门的研究问题。研究图的彩虹支配问题不仅具有重要的理论价值，而且具有重要的应用价值。它已被广泛地用来解决计算机科学、信息科学、网络理论等学科的问题，对其研究具有重大意义。
　　本文主要研究的是广义循环图的2-彩虹支配问题，研究结果如下：(1).研究了广义循环图C(n;{1,2})的2-彩虹支配问题，求出了其2-彩虹支配函数的精确值；(2).研究了广义循环图C(n;{1,3})的2-彩虹支配问题，求出了其2-彩虹支配函数的精确值；(3).研究了广义循环图C(n;{1,2,..., k})的2-彩虹支配问题，求出了其2-彩虹支配函数的精确值。
　　本文所研究的广义循环图的2-彩虹支配问题，是一个 NP-完全问题。研究它不仅对彩虹支配问题有重大的意义，而且对其它的NP-完全问题也有借鉴作用。这些研究结果进一步丰富了循环图的彩虹支配的精确解。

目录

缩 略 语 表

1 引言

1.1 基本概念

2 图的彩虹支配问题发展

2.1 支配的起源与发展

2.2 支配的基本概念

2.3 支配的计算复杂性

2.4 支配集的应用

2.5 彩虹支配的研究进展

2.6 本文工作

2.7 本章小结

3 广义循环图C(n;{1,2})的2-彩虹支配问题

3.1 广义循环图C(n;{1,2})的2-彩虹支配问题

3. 2 本章小结

4 广义循环图C(n;{1,3})的2-彩虹支配问题

4 . 1 广义循环图C(n;{1,3})的2-彩虹支配数

4. 2 本章小结

5 广义循环图C(n;{1,2,..., k})的2-彩虹支配问题

5 . 1 广义循环图C(n;{1,2,..., k})的2-彩虹支配问题

5. 2 本章小结

6 总结

7 展望

致谢

参考文献

作 者 简 介