| 【中文题名】 | 强迫数为2的六角系统 |
| 【英文题名】 | Hexagonal Systems with Forcing Number Two |
| 【学科专业】 | 运筹学与控制论 |
| 【论文级别】 | 硕士论文 |
| 【投稿时间】 | 2007-8-20 |
| 【中关键词】 | 六角系统,完美匹配,强迫数,强迫边,强迫集,强迫域分解 |
| 【英关键词】 | Hexagonal system,Forcing number,Perfect matching,Forcing edge,Forcing set,Forcing region decomposition, |
| 【分类导航】 | 数理科学和化学>数学>代数、数论、组合理论>组合数学（组合学）>图论> |
| 【论文摘要】 |
设M为图G的一个完美匹配．若M的子集S只包含在G的一个完美匹配M之中，则称S为M的一个强迫集．我们用f(G，M)表示M的最小强迫集所包含边的条数，用M表示G的所有完美匹配的集合。则G的强迫数为f(G)=min{f(G，M)|M∈M}．图G的边e称为强迫边如果它只属于G的一个完美匹配．P．Hansen，郑茂林和张福基，李学良分别在1994年和1995年刻画了所有有强迫边的六角系统．本文在强迫数为1的六角系统的基础上定义了强迫域分解的概念，由此得到了强迫数为2的六角系统，得到结论如下：六角系统H的强迫数为2当且仅当H的强迫域分解数为2；任意两个强迫数为1的六角系统H_1和H_2如果不是一个单个六角形和一个直链六角系统的情况，则都可以合并成一个强迫数为2的六角系统H，使得H可以把H_1和H_2作为两个单元进行强迫域分解．更进一步，文章给出了在一般情况下强迫数为1的两个六角系统H_1和H_2合并成强迫数为2的六角系统H的合成方法，最后对强迫域分解的应用进行了推广，得到了若干特殊六角系统图类的强迫数． |
| 【论文题纲】 |
|
摘要 |
4-5 |
|
ABSTRACT |
5-7 |
|
第一章 引言 |
7-15 |
|
1.1 相关背景及研究进展 |
7-8 |
|
1.2 预备知识 |
8-12 |
|
1.3 强迫域分解的定义 |
12-15 |
|
第二章 六角系统的强迫域分解 |
15-29 |
|
2.1 强迫域分解的存在性 |
15-17 |
|
2.2 f(H)=2的六角系统的强迫域分解 |
17-29 |
|
第三章 f(H)=2的六角系统的构造 |
29-40 |
|
3.1 强迫域分解的规律 |
29-32 |
|
3.2 f(H)=2的六角系统的构造 |
32-40 |
|
第四章 强迫域分解的推广及应用 |
40-44 |
|
4.1 寻找H的强迫集 |
40 |
|
4.2 一类特殊六角系统的强迫数 |
40-44 |
|
参考文献 |
44-46 |
|
致谢 |
46 |
|
| 【DOI】 | LunWen.ID:2.2008.11833 |
