论文部分内容阅读
图的连通性是图的最重要的性质之一,也是图论中的一个重要研究课题.由于连通图跟网络模型和组合优化的联系日益密切,从而使连通图理论拥有更加重要的理论价值和应用价值.连通图中的非基本边是研究3连通图结构特征的重要归纳工具,它作为有力的归纳工具,具有独特的优势:
第一,非基本边的处理简单方便,不会出现重边;
第二,非基本边的改变不影响其他任何边的存在.
因而,非基本边在探讨连通图的结构上应用的十分广泛.正因如此,近年来,关于连通图中非基本边的研究已成为一个热点问题.
本文通过研究连通图中的非基本边来刻画极小3连通图的结构特征.在本文中我们刻画恰含有6条非基本边的极小3连通图.
第1章主要叙述极小3连通图非基本边的研究背景和研究意义.
第2章回顾图论的一些基本概念,并介绍极小3连通图的一些重要性质.
第3章首先确定了恰含6条非基本边的极小3连通图中所含扇的数目.我们将简单极小3连通图中的所有基本边组成的边集进行等价划分,即一条基本边与另一条基本边等价当且仅当这两条基本边在同一个扇中.并且我们假设极小3连通图中不存在只有一条基本边且该基本边是两个平凡扇的公共边的这种等价类.若极小3连通图中存在这样的等价类,则可用一Ⅱ-型扇代替等价类中的一个平凡扇,使这样处理后的所得到的新图仍为极小3连通图,并且非基本边的数目保持不变.通过收缩新图中的某些Ⅱ-型扇就可以得到原图.所以我们通过研究处理后所得到的新图的结构就能得到原图的结构特征.由上述假设我们知道,每一个等价类在极小3连通图中对应唯一的一个扇,所以极小3连通图中等价类的数目就等于扇的数目.我们证明恰有6条非基本边的极小3连通图中的扇的数目k,3≤k≤5.
然后,分别刻画当k=3,4,5即扇的数目为3,4,5时恰含有6条非基本边的极小3连通图.
本文结论如下:
设G为不是轮的简单极小3连通图,则G恰含6条非基本边当且仅当G含有3个,4个或者5个扇,且G∈(p),其中(p)={A1,A2,…,A10,B1,B2,…,B27,C1,C2,…,C11},图A1,A2,…,A10,B1,B2,…,B27,C1,C2,…,C11见图7,图8,图9,图10,图11.
第4章结本文的结果并展望未来的研究工作.