论文部分内容阅读
关于图的最小圈基的研究从产生发展到现在,众多的学者包括数学家,生物学家,物理学家等等已经提出了许多相关的方法。但应该指出的是,到目前为止,这些算法和结果都往往仅限于针对某种或某些类型的图的最小圈基结构,而从图的运算的角度考虑最小圈基的结构,这方面的工作确是鲜为人知的,本文正是首先由一般的情况着手,再扩展到射影平面的相关结论。
首先,我们研究2-连通的简单平面图的运算对最小圈基的影响:设G<,1>,G<,2>为2-连通的简单平面图,B<,1>为G<,1>的最小圈基,B<,2>为G<,2>的最小圈基。
1、当图G<,1> ∩G<,2>=x即G<,1>,G<,2>相交于一个点时,图G的最小圈基为G<,1>,G<,2>的最小圈基的并集。
2、当图G<,1> ∩G<,2>={x,y}即G<,1>,G<,2>相交于两个点时,由于图的运算使图的圈基维数增加了1,图G的最小圈基为G<,1>,G<,2>的最小圈基的并集以及一个新圈。
3、当图G<,1> ∩G<,2>=P<,xy>即G<,1>,G<,2>相交于一条过x,y两点的最短路时,图G的最小圈基为图G<,1>,G<,2>的最小圈基的并集。
4、当图G<,1> ∩G<,2>=P<,xy>,即G<,1>,G<,2>相交于一条过x,y两点的非最短路,且图G<,1>,G<,2>中所有的二度节点都位于路P<,xy>上。我们分两种不同的情况在定理2.2.4和定理2.2.5中做出了详尽论述。其中主要的思想是通过图的运算引进了新的通过点x,y的最短路,对原最小圈基做出相应的运算。
在第三章中讨论2-连通的在射影平面上可大边宽度嵌入图的最小圈基结构,并且就这样的大边宽度嵌入图有唯一最长而圈和不唯一最长而圈两种情况在定理3.1.2和定理3.1.3中做了详尽论述。考虑一个图的圈空间中圈基的组合结构,证明了一个图的所有最小圈基具有唯一结构,即任意的两个最小圈基之问存在1-1对应,使得相互对应的圈具有相同长度。由此可知,任两个最小圈基中所含k-圈(k≥3)的数目相同。
2-连通图G是可大边宽度嵌入射影平面N<,1>,记F为G的所有面圈集合,C<,max>为图G的最长面圈,若对任意非面圈的可收缩圈α,都有任意的β∈Int(α) F-C<,max>,使得|β|<|α|,那么图G的最小圈基:B=(F - C<,max>)∪ C<*>(C<*>为G中最短不可收缩圈)。