论文部分内容阅读
书式嵌入的“书”是由一条书脊和多个书页构成.其中书脊为一条直线,书的每一页是由书脊所界定的半平面.对于给定图G的书式嵌入包括两方面内容:首先将G的顶点按照一个由线性标号所定义的顺序嵌入到书脊上,其次将E(G)中的每条边分放于各页,使得每页中的边均可画在该页上而互不相交.我们定义图G在某种已知顶点嵌入方式的情况下的书页数为在该嵌入方式下,使图G可嵌入的最少书页数,而定义在各种顶点嵌入方式下可嵌入的最少页数为图G的书页数.图的书式嵌入起源于许多领域,包括:计算机科学,大型集成电路理论,多层线路板印刷,平行机排序及Turning机图等等.本文主要研究了若干类图的书式嵌入问题. 第一章介绍了一些基本概念、符号及术语. 第二章研究了广义Petersen图的书式嵌入问题.设n和k的最小公约数为d(gcd(n,k)=d).记r为k|n的余数,即n=qk+r,并且记s=k?r.我们讨论了广义Petersen图P(n,k)书页数的上界并给出如下结果: (i)若n和d都是偶数,则pn(P(n,k))≤4.特别的,当k=2时,pn(P(n,k))=3. (ii)若n为偶且d为奇,则pn(P(n,k))≤5. (iii)若n为奇且k为偶,则pn(P(n,k))≤2s+1.特别的,当k=2时,pn(P(n,k))=3. (iv)若n和k都是奇数,则pn(P(n,k))≤k+1/2+3. 第三章研究了多环网络的书式嵌入.设N和αi都是偶数,对于i=1,2,3,当αi|N时,令si=αi/2.当αi∣N时,若gcd(N,αi)=2,则令si=αi/2+1.若gcd(N,αi)≠2,设N=kαi+t,则令si=αi?t/2(l+1),其中l是满足αi|lN的最小正整数.我们给出了如下结果并把三环网络的结果推广到了多环网络. (i)若di是偶数,di/2是奇数且αj=(di/2)αl,其中i≠j≠l且i,j,l∈{1,2,3},则pn(TL(N;α1,α2,α3))≤6. (ii)若di和dj是不等于2的偶数且dl是奇数,其中i≠j≠l且i,j,l∈{1,2,3},则pn(TL(N;α1,α2,α3))≤si+sj+3. (iii)若di和di2是偶数且dj和dl是奇数,其中i≠j≠l且i,j,l∈{1,2,3},则pn(TL(N;α1,α2,α3))≤si+7. (iv)若di=2且dj和dl是奇数,其中i≠j≠l且i,j,l∈{1,2,3},则pn(TL(N;α1,α2,α3))≤8.特别的,若dj=1,则pn(TL(N;α1,α2,α3))≤7. (v)若d1,d2和d3是奇数,则pn(TL(N;α1,α2,α3))≤11.特别的,对于i∈{1,2,3},若di=1,则pn(TL(N;α1,α2,α3))≤10. (vi)对于多环网络ML(N;α1,α2,...,αl)和任意的i∈{1,2,..., l},若di是奇数,则pn(ML(N;α1,α2,...,αl))≤4l?1.特别的,若di=1,则pn(ML(N;α1,α2,...,αl))≤4l?2. 第四章研究了图运算的书式嵌入问题.我们给出了路和圈的字典积、半强乘积的书页数上界,还研究了n条路笛卡儿积的书式嵌入问题并给出了一个算法,得到如下结果: 对于mi∈N,pn(Pm1?...?Pmn)≤2(n?1)?k.其中k表示P2的个数.