图中参数与树型结构的研究.pdf

⑧⋯瑼⋯博士学位论文图中参数与树型结构研究论文作者:陈园指导教师:胡智全教授学科专业:基础数学研究方向:图与组合论华中师范大学数学与统计学学院年
砌篎::
⑧舌、:沙哆年』月多。日日期:沙鵪露唷H日期:沙驴岁月;华中师范大学学位论文原创性声明和使用授权说明年原创性声明学位论文版权使用授权书程”中的规定享受相关权益。回垂途塞握銮后溢厦;旦兰生┒坏┤本人郑重声明:所呈交的学位论文,是本人在导师指导下,独立进行研究工作所取得的研究成果。除文中已经标明引用的内容外,本论文不包含任何其他个人或集体己经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集体,均已在文中以明确方式标明。本声明的法律结果由本人承担。作者签名:本学位论文作者完全了解学校有关保留、使用学位论文的规定,即:学校有权保留并向国家有关部门或机构送交论文的复印件和电子版,允许论文被查阅和借阅。本人授权华中师范大学可以将本学位论文的全部或部分内容编入有关数据库进行检索,可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。同时授权中国科学技术信息研究所将本学位论文收录到《中国学位论文全文数据库》,并通过网络向社会公众提供信息服务。本人已经认真阅读“咝Q宦畚娜氖菘夥⒉颊鲁獭保饨ū人的学位论文提交“咝Q宦畚娜氖菘狻腥姆⒉迹⒖砂础罢导师签名:博士学位论丈:
⑧中文摘要荩簦≥几十年来,,,即说明图中存在恰好两个叶子的支撑树或是最大度等于疵挥蟹种У愕闹С攀鳎匀痪陀腥缦挛侍猓耗芊窀保证图中存在至多鲆蹲拥闹С攀鳎蚴峭贾写嬖谟邢薷龇种У愕闹С攀鳎蚴图中存在最大度不超过闹С攀鞯纫幌盗形侍獾奶跫保敉嘉9芏倭通图,即说明图中存在以任意两点作为叶子集的支撑树,自然我们就可以试图探求在何种条件下,,判定一个图是否含一条哈密尔顿路从算法复杂性来讲是Ⅳ耆的,从而对上述一系列有关保证图中是否存在具有相应特征的支撑树问题也是Ⅳ一完全的,,运用坚韧度、独立数、连通度、领域并、度和等条件,集中讨论图中是否存在以下五类特征的支撑树的充分条件:,图中,特别地,;贾写嬖诼闳サ羲幸蹲雍螅畲蠖戎炼辔猭的支撑本文主要研究了在满足一定连通度条件下,@竦牧↘图,輓,则中含一条哈密尔顿路,即恰含两个叶子的支撑树;当时,若≥佗一,则写嬖谥多鲆蹲拥闹С攀鳎⑶宜得髁私崧壑械慕缇W詈每赡艿模疚奶岣吡ǘ龋考虑涣↘↘一騁中存在至多鲆蹲拥闹С攀鱢. 另一方面,本文也研究了连通图中类似的图且阶数,若輓一,,其中题,证明了图A 口博士学位论文Ⅸ【餻口
关键词:/,籪煌校一;支撑树;度和
瑃琹—...七;畇..琲琩;.瑆甌瑆’琣,..七一—.,琲,;畇尼.,籪琽,.
篕一;,籪籹猚,輓,.≥猭/輓唬堇褚,..,籪七.,≥,.;礼
⑧目录中文摘要..............:.....................符号说明....................................第一章综述..................................图的基本概念和符号...........................研究背景..................................С***一树问题..........................................灰蹲恿ㄍ嘉侍猓具有皇鞲傻闹С攀魑侍猓本文主要结论...............................结构安排.................................第二章↘图中的支撑树特征研究.............. 预备知识......................................................................