k-连通图中生成树和完美匹配上的可收缩边

摘要

图论是组合数学的分支，是一个具有悠久历史并且发展迅速的数学分支。它起源于一个古老的民间游戏—格尼斯堡七桥问题。1736年欧拉解决了上述问题，发表了关于图论的第一篇文章，图论由此产生。
　　图的结构特征是图论的主要研究方向之一，其中图的连通性一直是图论研究的重要课题。在研究图的连通性的过程中主要包括对图的结构特征进行探究和分析。在进行有关连通图的构造时，我们一般采用一些定义作为基础，并且运用特殊的运算来保持图的连通性，对复杂的连通图进行上述运算得到简单的连通图。因为可去边与可收缩边能够保持图的连通性，所以它们成为构造连通图的常用工具。
　　假设边e=xy∈E(G)，把顶点x，y都去掉，并把与这两个顶点关联的边都去掉，再将一个新的顶点u添加到图G中，并且将刚刚去掉的两个顶点的所有邻点与新增的顶点邻接。上述运算即为将边e收缩，得到的新图记为G/e。如果得到的新图依然能够保持原图的连通性，我们称这条边e是G的可收缩边，反之则为不可收缩边。
　　本文主要研究k-连通图中的可收缩边的存在性及数目，分别为k-连通图中生成树上的可收缩边数目以及如果图中存在完美匹配时完美匹配上的可收缩边数目，并得下述结果。
　　定理2.1假设G是阶数为n(n≥7)的k-连通图（k≥3），H是G的一棵生成树，满足图G的任意断片阶数都大于「k/2(])，则H上至少有k+1条可收缩边。
　　假设k-连通图中存完美匹配，给出其可收缩边数目的结果如下:
　　定理3.1假设G是阶数为n（n≥0）的k-连通图（k≥3），M是G的一个完美匹配，满足图G的任意断片阶数都大于「k/2(])，则M上至少有「k/2(])+1条可收缩边。

目录

声明

摘要

符号说明

第一章 绪论

§1．1 图论概述

§1．2 基本概念

§1．3 可收缩边相关结论

第二章 k-连通图中生成树上的可收缩边

§2．1 相关结论

§2．2 k-连通图中生成树上的可收缩边

第三章 k-连通图中完美匹配上的可收缩边数目

§3．1 相关结论

§3．2 k-连通图中完美匹配上的可收缩边数目

参考文献

致谢

攻读硕士学位期间发表的学术论文