平面图的强迫集、反强迫集与交错集之间的关系

代理获取

页面导航

目录
摘要
著录项
相似文献
相关主题

摘要

设G是一个图.G的完美匹配是指覆盖G中所有顶点的两两不交边的集合.设M是G的一个完美匹配。S?E(G).若S?M且S不被包含于G的其它完美匹配,则称S是M的强迫集;若S?E(G)\M且G?S有唯一的完美匹配M,则称S是M的反强迫集.M的最小强迫集和最小反强迫集的大小分别称为M的强迫数和反强迫数,记作f(G。M)和af(G。M). G中所有完美匹配的强迫数的最大值和反强迫数的最大值分别称为G的最大强迫数和最大反强迫数,记作F(G)和Af(G).
　　边交替出现在M和E(G)\M中的圈称为M-交错圈.两个M-交错圈称为相容的,如果它们要么不相交要么仅相交于M中的边处.对于平面二部图G。Pachter等人证明了 f(G。M)等于 G中互不相交的M-交错圈的最大个数,雷洪川等人证明了af(G。M)等于G中相容的M-交错圈的最大个数.
　　设R是平面图G中若干内面的集合.若G有一个完美匹配M使得R中所有面的边界都是 M-交错圈,则称 R是 G的一个交错集.进而,若交错集 R中的面互不相交,则称R是G的一个共振集.G的最大共振集的大小称为G的共振数,记作res(G).显然。Pachter等人的结果蕴含着F(G)≥res(G).
　　六角系统H是2-连通的有限平面图,它的每个内面都以正六边形为边界.H的最大共振集称为Clar集,其大小称为Clar数,记作C l(H).郑茂林等人证明了H去掉任意 Clar集后所剩图有唯一完美匹配; Salem等人证明了 H去掉任意极大交错集后所剩图也有唯一完美匹配.结合Pachter和郑茂林等人的结果,徐丽琼等人证明了: H有达到强迫数最大值的完美匹配 M,使得 H中互不相交的M-交错面圈(即。M-交错六角形)的最大数目等于M的强迫数;从而证明了C l(H)=F(H),并且猜想方格子图的最大强迫数能在多项式时间内计算出来.其中方格子图是无限平面方格网上的有限连通子图,它的每个内面都是方格并且每条边被包含在至少一个方格上.
　　六角系统H的最大交错集的大小称为Fries数,记作F ries(H).显然。Af(H)≥F ries(H).雷洪川等人通过证明 H有达到最大反强迫数的完美匹配 M使得 H中M-交错六角形的数目等于M的反强迫数,证明了F ries(H)=Af(H).
　　受上述工作的启发,我们进一步研究六角系统和方格子图中完美匹配的强迫数、反强迫数与交错面圈个数之间的关系.
　　本论文共分为五章.第一章首先给出一些文中用到的概念、术语和记号,而后从物理化学角度介绍共振集和匹配强迫数的提出背景并综述相关的研究进展,最后概述我们所取得的主要结果.
　　第二章我们研究了方格子图的最大共振集和极大交错集的性质,给出并证明共振数与最大强迫数之间的关系.具体地,我们证明了:方格子图去掉任意最大共振集后所剩图有唯一完美匹配;方格子图去掉任意极大交错集后所剩图也有唯一完美匹配;方格子图的共振数等于其最大强迫数,进而证实了徐丽琼等人提出的猜想.
　　第三章我们研究了六角系统H的最大强迫数和交错六角形个数之间的关系.通过改进郑茂林等人的方法,我们证明了:对于 H中每个达到强迫数最大值的完美匹配M(即f(H。M)=F(H))。H中两两不交的M-交错六角形的最大数目等于M的强迫数;由C l(H)=F(H)知。H有一个由M-交错六角形构成的Clar集;进而,对于H中任意F(H)个两两不交的M-交错圈,它们的内部彼此不相交,且每个圈在H中围成一个线性六角链.
　　第四章我们研究了方格子图H中匹配强迫数和交错方格子个数之间的关系.证明了:对于H中每个达到强迫数最大值或次大值的完美匹配M(即f(H,M)=F(H)或f(H。M)=F(H)?1)。H中两两不交的M-交错方格子的最大数目等于M的强迫数;当f(H,M)=F(H)时。H中任意f(H,M)个两两不交的M-交错圈彼此有不相交的内部,且每个圈在H中围成一个锯齿形链.
　　第五章我们研究了六角系统 H中匹配反强迫数和交错六角形个数之间的关系.证明了:对于H中每个达到反强迫数最大值或次大值的完美匹配M(即af(H。M)=Af(H)或 af(H。M)=Af(H)?1)。H中 M-交错六角形的数目等于 M的反强迫数。H中任意 af(H。M)个非交叉的相容 M-交错圈彼此有不相交的内部,且每个圈在 H中围成一个线性六角链.本章最后,我们研究了不含三亚苯作为好子图的六角系统H,证明了: H中每个完美匹配M′的反强迫数都等于M′-交错六角形数目的充要条件是H不含三亚苯作为好子图.

著录项

作者
周向前;
展开▼
作者单位

兰州大学;

展开▼
授予单位兰州大学;
学科数学、应用数学
授予学位博士
导师姓名张和平;
年度 2016
页码
总页数
原文格式 PDF
正文语种中文
中图分类图论;
关键词
六角系统; 方格子图; 完美匹配; 反强迫集; 交错集; 平面图;

相似文献

中文文献
外文文献
专利

1. 强反凸模糊集与反凸模糊集、严格反凸模糊集间的关系研究 [J] . 车雨红 . 价值工程 . 2012,第016期
2. 交错系统分离集和生成集关系的研究 [J] . 程建康 ,陈溥 ,杨贶 . 科技风 . 2017,第023期
3. Vitali集与Bernstein集之间的关系 [J] . 沈佳婧 . 通讯世界 . 2019,第004期
4. 在“补残”与“出世”之间——论《老残游记》一集与二集的对话关系 [J] . 谢博远 . 汕头大学学报（人文社会科学版） . 2019,第011期
5. 直觉权与凸直觉模糊集之间的关系研究 [J] . 王利香 ,付云鹏 ,袁学海 . 辽宁大学学报（自然科学版） . 2019,第002期
6. 浅论智能控制与决策对数学基础的促进——模糊集(Fuzzy set)可拓集(Extension)集对分析(SPA)界壳论(Jieke Theory)粗糙集Vague集与统一集论 [C] . 王拓 ,贺仲雄 . 2001年中国智能自动化会议 . 2001
7. 几类笛卡尔积图的H-强迫集和H-强迫数 [A] . 张文娟 . 2015

平面图的强迫集、反强迫集与交错集之间的关系

目录

摘要

著录项

相似文献

相关主题

期刊订阅