强迫数为2的六角系统

强迫数为2的六角系统

论文摘要

设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的六角系统H1和H2如果不是一个单个六角形和一个直链六角系统的情况,则都可以合并成一个强迫数为2的六角系统H,使得H可以把H1和H2作为两个单元进行强迫域分解.更进一步,文章给出了在一般情况下强迫数为1的两个六角系统H1和H2合并成强迫数为2的六角系统H的合成方法,最后对强迫域分解的应用进行了推广,得到了若干特殊六角系统图类的强迫数.

论文目录

  • 摘要
  • ABSTRACT
  • 第一章 引言
  • 1.1 相关背景及研究进展
  • 1.2 预备知识
  • 1.3 强迫域分解的定义
  • 第二章 六角系统的强迫域分解
  • 2.1 强迫域分解的存在性
  • 2.2 f(H)=2的六角系统的强迫域分解
  • 第三章 f(H)=2的六角系统的构造
  • 3.1 强迫域分解的规律
  • 3.2 f(H)=2的六角系统的构造
  • 第四章 强迫域分解的推广及应用
  • 4.1 寻找H的强迫集
  • 4.2 一类特殊六角系统的强迫数
  • 参考文献
  • 致谢
  • 相关论文文献

    标签:;  ;  ;  ;  ;  ;  

    强迫数为2的六角系统
    下载Doc文档

    猜你喜欢