Print

强迫数为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 一类特殊六角系统的强迫数
  • 参考文献
  • 致谢

    • 相关论文文献

    本文来源: https://www.lw50.cn/article/b2400ef37f690c1678810ba7.html