论文部分内容阅读
图论是组合和离散数学的一个极为重要的分支,也是计算机科学的重要内容。本文研究的主要内容是由图的边标号推导出点标号的问题。自1963年G.Ringel提出的一个猜想,以及1966年A.Rosa提出的著名的优美树猜想后,人们开始广泛关注并研究图的标号问题。图论中的标号图有着重要的理论价值和广泛的应用背景,如:密码学,物理化学,地理,天文,网络设计,计算机科学等领域都广泛的应用了图论及其算法。 目前国内外已取得了不少关于全友好指标集与全边友好指标集的研究成果。本文主要研究简单图中扇图Fn与齿轮图Gn的全边友好指标集。具体分为: 1.当n为偶数时,扇图Fn的全边友好指标集为FEFI(Fn)={-(n+1),-(n-3),…,-1,3,…,n-5,n-1n≡0(mod4)-(n+1),-(n-3),…,-3,1,…,n-5,n-1n≡2(mod4); 2.当n为奇数时,扇图Fn的全边友好指标集为FEFI(Fn)={-(n+1),(n-3),…,-2,2,…,n-3,n+1n≡1(mod4)-(n+1),-(n-3),…,-4,0,4,…,n-3,n+1n≡3(mod4); 3.当n为偶数时,齿轮图Gn的全边友好指标集为FEFI(Gn)={-(2n+1),(2n-3),…,-1,3,…,2n-5,2n-1n≡0(mod4)-2n+3,-2n+7,…,-1,3,…,2n-5,2n-1n≡2(mod4); 4.当n为奇数时,齿轮图Gn的全边友好指标集为FEFI(Gn)={-(2n+1),-(2n-3),…,-3,1,…,2n-5,2n-1}。 通过研究已有图形的全边友好指标集的标号规律,并结合扇图与齿轮图的图形特点找出其普遍的规律,进而得到简单图中扇图Fn与齿轮图Gn的全边友好指标集的结论,并给出了相应的证明及例子来说明结论的正确性。