论文部分内容阅读
图论研宄中一个重要而活跃的领域就是图谱理论,图的谱可以用来刻画图的某些性质。其中最为常见的是对图的邻接谱和拉普拉斯谱的研宄。由全图演变而来的变换图,因其谱可由原图来刻画,近来也是研宄的热点。 设D是无环无重边的有向图,顶点集V(D)= V,边集五(D)=E。则乃。表示顶点为V的无边有向图;D1表示顶点为V的完全有向图;D+=D是D的补图De。本文介绍了正则有向图D有四个变量x,y,t,h E{+,-,0,1}的变换图D21—,其中t= h。D的xyth-变换图是指有向图D2^、Dxy00=Dx U Dy。且D2^=Dx U Dy UT UHh,其中,当t=+时,丁*= T(D);当t=—时,丁*= Tcb(D);当t=1时,T*是以V和E为两部分顶点集的二部图,其边集为V xE。当h=+时,Hh= H(D);当h=—时,Hh=Hcd(D);当h=1时,Hh是以V和E两部分为顶点集的二部图,其边集为E x V。 接着用r正则有向图D的顶点数n,度数r,以及D的邻接谱来刻画其变换图D¥h所有的邻接谱。重要的是文章应用矩阵理论,研宄了变换图D#h,Dy;rfh,(D—、-1之间的同构关系,并由此找出了邻接同谱的变换图对,以及给出了邻接同谱但不同构的图对。 本文还用r正则有向图D的顶点数n,度数r,以及D的拉普拉斯谱来刻画了变换图Dx—所有的拉普拉斯谱。当t或h为零时,由于度矩阵的变化,与邻接谱可以按照;x与y相同来分类计算有所不同,其也需一一计算。 最后本文用D的顶点数n,度数r,以及D的有向生成树数目刻画了其变换图的有向生成树数目。