检索结果-南通市图书馆

维普期刊数据库

在线全文

学校读者我要写书评

暂无评论

超图的边着色

超图的边着色

作者：王娜新疆师范大学

学位级别：硕士

超图是一般图的重要推广,超图的着色概念也是一般图着色概念的自然推广。对于超图的着色有很多各种各样的应用背景,如时间表问题,资源的分配问题。而且它与其它的组合问题也有着广泛的联系,例如极值理论,Ramsey理论,概率方法,差值理论... 详细信息

超图是一般图的重要推广,超图的着色概念也是一般图着色概念的自然推广。对于超图的着色有很多各种各样的应用背景,如时间表问题,资源的分配问题。而且它与其它的组合问题也有着广泛的联系,例如极值理论,Ramsey理论,概率方法,差值理论等等。在近三十年中,超图的着色问题已经有许多人研究,并且获得了很多结果。第一章主要研究完全r-partitioned超图的边着色。设H是一个超图,它的顶点集合V被划分为r个部分即V={V,…,V),给定一个r维向量M=(p,p,…,p)(P∈N,1≤i≤r),H中的边集是V中的每个多重集E并且满足: M (|E∩V|,(|E∩V|,…,(|E∩V|),则我们称H是完全r-partitioned超图K,或记为K。本人在这一章里得到了四个主要结论和一个猜想。定理1.2.1:若完全r-partitioned超图K,并且设n≤n≤…≤n。如果2|n,则(q(H)-(n-1)(?)…(?),否则(q(H)-n(?)···(?)。定理1.2.2:若完全r-partitioned超图K,并且设n≤n≤…≤n。如果有t|n,或者(?)|(?)(1≤i≤r),则q(H)=((?))((?))…((?))(?)。定理1.2.3:若完全r-partitioned超图K,并且设n≤n≤…≤n。如果t(?)n且(?)(?)((?))(1≤i≤r),则定理1.2.4:若完全r-partitioned超图K,并且设n≤n≤…≤n。则(?) 猜想1.2.1:若完全r-partitioned超图K,并且设n≤n≤…≤n。则(?) 第二章研究了线性超图的边着色。设H是一个超图,如果对任意两条边E,E(i≠j),有|E∩E|≤1。若H是无圈的线性超图则我们称为线性超树。本人在这一章里得到了四个结论。定理2.2.1:设H是n个顶点上的无环线性超图,若S是由边秩大于等于3的边导出的部分超图。如果△-2,q(S)-3,则q(H)≤n。定理2.2.2:设H是n个顶点上的无环线性超图,若S是由边秩大于等于3的边导出的部分超图。如果△≤3,q(S)≤3,则q(H)≤n。定理2.2.3:设H为r阶射影平面,则q(H)=r-r+1。定理2.3.1:设H是线性超树,且H的最大度为△,则q(H)=△。第三章研究了路,0图,T(见图3.1)这三类图的成分着色。设H是个超图,对于它的一个k-边着色c:E(H)→{1,2,…,k),f(H,c)是由这k种颜色中同一色类导出的子超图中所含分枝数最少的子超图的分枝数。f(H)表示H中所有k-边着色中f(H,c)的最大值,本人在这一章里得到了三个结论。定理3.2.1:设P是n个顶点的一条路,则f(P)=(?)。定理3.2.2:f(T)=(?)+1,(见图1(a))。定理3.2.3:设G是0-图,则f(G) 2,(见图1(b))。

关键词：边着色完全r-partitioned超图线性超图线性超树成分着色

同方学位论文库评论

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

若干图的连续边着色

若干图的连续边着色

作者：闫秀琴山西大学

学位级别：硕士

具有重要的实际意义和理论意义的图的连续边着色问题是图论中的热点话题之一，它在组合分析和日程安排理论上有着非常广泛的应用．连续边着色问题首先是由Asratian和Kamalian在1987年提出的，其内容为：对于简单图G用颜色1，2，3…对其... 详细信息

具有重要的实际意义和理论意义的图的连续边着色问题是图论中的热点话题之一，它在组合分析和日程安排理论上有着非常广泛的应用．连续边着色问题首先是由Asratian和Kamalian在1987年提出的，其内容为：对于简单图G用颜色1，2，3…对其边正常着色，如果每一个顶点表现的颜色构成一个连续的整数集合，那么就称这个边着色是连续的．许多图是不可连续边着色的，为了测量与连续边着色的渐进程度，我们引入了图的一个新的不变量：图的亏度．图G的亏度def(G)是指加在G上使它可连续边着色的悬挂边的最小数目．本文分为三章，主要研究了若干图的连续边着色性．第一章我们给出了本文将用到的图论的主要术语、记号和基本概念．在第二节我们介绍了连续边着色方面的基本结论．第二章主要研究了一些圈图的连续边着色．在这章中，根据3-圈图的结构和性质，以及连续边着色的定义，得到了几类3-圈图的亏度，解决了它们的连续边着色问题．进而推广到k-圈图，我们通过运用归纳法和反证法的思想，讨论了一种k-圈图的连续边着色及其亏度问题．主要结论叙述如下： (1)若G是四条内部不相交的(u，v)路的并图，则 (2)令C,C,C是三个不相交的圈，P(i=1，2)是两条不相交的(V(C)，V(C))路．若G是C，C，C，P和P的并图，则def(G)=0． (3)若G是仅有一个公共顶点的n(n≥1)个圈C，C，…，C的并图，则第三章主要是通过运用归纳法思想研究了两种笛卡尔积图P×P和C×P的连续边着色问题．主要结论叙述如下： (1)若G是两条不相交的路P和P的笛卡尔积图，则def(G)=0． (2)令C是长为m(m≥3)的圈，P是与C不相交的一条长为n(n≥0)的路．若图G是C和P的笛卡尔积，则def(G)≤1．

关键词：边着色连续边着色亏度 3-圈图笛卡尔积图

同方学位论文库评论

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

重图边着色的两个新结果

北京邮电大学学报 1996年第4期19卷 71-74页

作者：刘焕平杨义先北京邮电大学信息工程系

利用Ｈ．Ｐ．Ｙａｐ在文献［２］中给出的方法，给出了关于重图边着色的两个新结果。

关键词：图边着色边色数

维普期刊数据库

在线全文

学校读者我要写书评

暂无评论

边着色临界图的构造

哈尔滨师范大学自然科学学报 1990年第2期6卷 23-28页

作者：李晓东

维普期刊数据库评论

在线全文

维普期刊数据库

学校读者我要写书评

暂无评论

关于N阶完全图KN的t边着色

广西大学学报(自然科学版) 1982年第2期 92-98页

作者：黄国勋李炯生广西大学中国科学技术大学

本文讨论的图都是简单图,即有限阶无圈、无重边的无向图.KN表示N阶完全图,其顶点集合记为V（KN）,边集合记为E.设B、DV（KN）,B∩D=φ,以B×D或D×B记由B与D之间的所有联线组成的边集合.设t是正整数,E1,E2,…,E1是E的一个分划.以c1,c2,... 详细信息

本文讨论的图都是简单图,即有限阶无圈、无重边的无向图.KN表示N阶完全图,其顶点集合记为V（KN）,边集合记为E.设B、DV（KN）,B∩D=φ,以B×D或D×B记由B与D之间的所有联线组成的边集合.设t是正整数,E1,E2,…,E1是E的一个分划.以c1,c2,…,c_t表示t种不同的颜色.把Ei中的每一条边着以颜色ci,1≤i≤t,則称赋以完全图KN的一种t边着色,此时KN也称为t边着色完全图,简称t色完全图.以V（KN）中

关键词：单色三角形完全图个数定理图(数学) K_N 边着色

在线全文

同方期刊数据库

学校读者我要写书评

暂无评论

2边连通3正则平面图的边着色

中国民航学院学报 1998年第3期16卷 68-73页

作者：秦玉祥中国民航学院教务处

对具有正常３边着色的２边连通３正则平面图的顶点定义了方向，并且在这样的图上建立了路径上的积分，进一步给出了２边连通３正则平面图是３边可着色的等价条件。

关键词：边着色 3正则图平面图图论

维普期刊数据库

在线全文

学校读者我要写书评

暂无评论

N阶完全图KN的t边着色

应用数学学报 1984年第4期 430-436页

作者：李炯生黄国勋广西大学中国科学技术大学

本文讨论的图都是简单图,即有限阶无圈、无重边的无向图.N阶完全图记为K,其顶点集合记为V(K),边集合记为E(K).设B、DV(K),B∩D=Φ.所有连接B的顶点与D的顶点的边的集合记为B×D,或D×B.设t是正整数,E,…,E是E(K)的一个分划.c,…,c表示t... 详细信息

本文讨论的图都是简单图,即有限阶无圈、无重边的无向图.N阶完全图记为K,其顶点集合记为V(K),边集合记为E(K).设B、DV(K),B∩D=Φ.所有连接B的顶点与D的顶点的边的集合记为B×D,或D×B.设t是正整数,E,…,E是E(K)的一个分划.c,…,c表示t种不同颜色.把E中每条边都着以颜色

关键词：单色三角形完全图顶点引理个数图(数学) K_N 边着色

在线全文

同方期刊数据库

学校读者我要写书评

暂无评论

关于唯一可3边着色图

应用数学学报 1984年第3期 285-292页

作者：黄济华浙江冶金经济专科学校

本文探讨了唯一可3边着色图的一些性质,从而否定了[2]中提出的两个猜想.一个是Fiovini和Wilson提出的,另一个是Greenwell和Kronk提出的.文中运用的概念和记号,除特别提到的外,一般都引自[1、2]. 唯一可k边着色问题,只剩下k=3时的情形了(... 详细信息

本文探讨了唯一可3边着色图的一些性质,从而否定了[2]中提出的两个猜想.一个是Fiovini和Wilson提出的,另一个是Greenwell和Kronk提出的.文中运用的概念和记号,除特别提到的外,一般都引自[1、2]. 唯一可k边着色问题,只剩下k=3时的情形了(见[2]).为此,[2]中指出了下述三个猜想:

关键词：边着色定理所得命题顶点度悬挂边

2n＋1名选手的循环赛与完全图K（2n＋1）的△（G）＋1-边着色

在线全文

同方期刊数据库

学校读者我要写书评

暂无评论

矿业科学技术 2007年第1期35卷 35-37页

作者：侴万禧安徽理工大学土木系安徽淮南232001

为解决2n＋1名选手的循环赛安排问题，本文给出了边矩阵和循环赛的定义、提出了求解K（2n＋1）的△（G）＋1个对集的一种算法，亦即是利用K（2n＋1）的△（G）＋1-边着色确定△（G）＋1个对集。文章还介绍了循环赛图的形成过程，讨论了2... 详细信息

为解决2n＋1名选手的循环赛安排问题，本文给出了边矩阵和循环赛的定义、提出了求解K（2n＋1）的△（G）＋1个对集的一种算法，亦即是利用K（2n＋1）的△（G）＋1-边着色确定△（G）＋1个对集。文章还介绍了循环赛图的形成过程，讨论了2n＋1阶循环赛图K^（i）（2n＋1）的个数问题。

关键词：循环赛完全图边着色边矩阵对集