论文并向国家有关部门或机构送交论文的复印件和电子版,可以将本学位论文的全部或部分内容编入有关数据库进行检索,可以采用影印、缩印、或扫描等复制手段保存和汇编本学位论文。
学位论文题作者签名:导师签名: 大连理工大学硕士学位论文 引 言 图论是组合数学的一个重要分支,也是离散数学的一个重要组成部分,它在数学领域和计算科学领域都有着广泛地应用。
1736年,Euler解决了K6nigsberg七桥问题,这是有文字记载的最早的图论研究文献。
因此,这一事件被大家认为是图论作为一门独立的学科出现的标志。
到1936年,K6nig编写了第一本图论专著,总结了图论二百年发展的主要成果。
自二十世纪中期以来,现实世界的需要使得图论领域的研究呈现出蓬勃发展的趋势。
随着计算机技术的广泛应用,图论的研究也注入了新的活力,利用计算机技术解决图论问题成为一个令人感兴趣的研究方向。
1976年,美国的Hanker等人利用计算机用了1200小时的计算时间,解决了数学家们一百多年来所未能解决的一个著名的图论难题一四色问题。
这一事件表明计算机技术的应用促进了图论的研究与发展。
因此,它在图论的发展历史中占有一个重要的位置。
图论发展至今,已经积累了许多难题,至今仍找不到有效的算法去解决,如求图中Hamiltom回路,Ramsey问题,笼问题以及计算任意图的支配数问题等等。
这些问题均属于NP完全问题。
自从1852年四色猜想的提出,在着色问题的研究就没有间断过。
而且着色的应用广泛如频率分配、课表安排等。
目前国内外对着色的研究集中在以下及个方面: (1)全着色、等全着色; (2)三一着色; (3)循环着色。
图的支配问题是近年来图论中另一个比较活跃的研究领域。
图的支配数是在实际问题中提出的。
因此,在现实生活的许多领域都有广泛的应用。
例如,在一个通讯网络的一些节点上放置发射器,要求每个发射器的节点一定和某个发射器的节点有一个直接的通讯线路。
如何选择节点,使得放置的发射器的数目最小。
对支配数的研究,目前国内外的研究集中在以下几个方面: (1)支配数; (2)完全支配数; (3)边支配数; (4)彩虹支配。
若干图的等全着色及彩虹支配问题的研究 1 基本概念 本文中未定义的术语参见徐俊明《图论及其应用》【11,Bondy和Murty的((Graph Theory with Applications))〔21,Haynes,Hedetniemi和Slater著的((Fundamentals of Domin— ation in Graphs))【3】和((Domination n Graphs:Advanced Topics))【4】. 1.1 图 一个无向图G定义为一个二元组(矿,E),记作G=(y,E),其中V=矿(G)是一个非 空集合,称作无向图G的顶点集;E=E(G)是由矿(G)中元素构成的无序对集合,即 E(G)={(“,1,)I“,1,∈矿(G)),称为无向图G的边集,简记为(“,V)为UV. 无向图与有向图统称为图。
本文中的图是指无向图。
边UV的端点U和v称为相邻的。
称点“,v和边洲相关联,同时,也称一条边为与它 的端点相关联。
若两条不同的边与一个公共的点关联,则称它们是互相邻接的边。
关联同一端点的一条边称为自环。
两条或两条以上的边关联一对端点,称为多重边。
既没有环也没有重边的图称为简单图。
P=p(G)=|V(G)I表示图G中的顶点数,称为图G的阶(Order). q=q(G)=l E(G)I表示图G中的边数,称为图G的大d、(Size). 当P=0的图称为空图(Empty graph),记作a. 当P=1,q=0时的图称为平凡图(Trivial graph),所有其它的图称为平凡图。
当V(G)和E(G)都是有限集,则称图为有限图;否则称无限图。
本文所涉及的图均为无自回路,无重边,有限的无向图。
1.2路与图的连通性 G的一条通路是指一个有限非空序列W=Voelvle2v2…ekVk,它的项交替地为顶点和边,使得对l≤f≤k,eI端点是_一l和Ⅵ.称w是从%到取的一条通路。
顶点‰和%分别称为w的起点和终点,而M,1,”..,v¨称为它的内部顶点。
整数k称为w的长。
在简单图中,通路可简单地由顶点序列来表示,即W=VO)v。
,V:,...,唯. 若通路W的边e,,e:,...,e。
互不相同,则w称为迹;这时w的长恰好是边数。
又若通路w的顶点vo,v1’...,v々也互不相同,则w称为路。
划分是指将一个正整数k表示为若干正整数的和,或者看作一个无序正整数组,这些正整数的和是k. 大连理工大学硕士学位论文 若一个胛阶简单图G各点的度为盔,则分正整数k为刀个部分的划分∑d,称为是图划分。
G的两个顶点材和v称为连通的,如果在G中存在(甜,v)路。
规定U和v是连通的。
如果对G中每一对顶点甜,v都有一条(“,1,)路,则称G为连通图,否则称为非连通图。
连通是顶点集V(G)上的一个等价关系,于是可将V(G)划分为一些等价类。
设V(G)的所有不同的等价类为K,K,...,圪,这G【K〕,G〔吃】,...,G〔圪】为G的连通分支,简称分支或支。
记G的分支个数为以G).于是G是连通图当且仅当w(G)=1. 连结甜和v中长度最短的通路的长度,称为U与v的距离,记为a(u,v).d(G)=max{d(u,1,)l“,’,∈V)为G的直径。
~1.3正则图与完全二部图 ‘ 在图G中,如果顶点“,v是相邻的,通常称U是v的一个邻接点,顶点“的邻域集合是图G中所有与U相邻的顶点的集合,记作N(u),其中N(u)={v UV∈E(G)). Ⅳ〔z,】-{U)UN(u),称作顶点U的闭邻域。
设甜∈V(G),称a(u)刊N(u)I为甜的度。
图G的顶点的最大度和最小度分别用A(G)和万(G)表示。
若图G的各顶点的度相同,则称图G为正则图,若任取U∈V(G),d(甜)=k则称图G为k-正则图,称它的正则度为k,此时N(u)={v I甜v∈E(G))如图1.1所示的图为3一正则图。
图1.1 3一正则图 Fig.1.1 3-regular graph 完全二部图Km.。
是满足以下条件所构成的图类: (1)顶点分为二个集合K,%,其中l K I=m,l砭卢n; (2)对于任意甜∈形,1,∈巧,若f≠/,则甜,V相邻(f,歹)=1,2. 若干图的等全着色及彩虹支配问题的研究 如图1.2所示的图为K2.。
完全二部图。
我们把所=1时的完全二部图墨.。
称为星图。
图l。
2岛.4完全二部图 Fig.1.2 K2,4 complete bipartite graph 1.4子图与生成子图 已知图G=(V,E)和H=(V’,E7),如果y’(日)∈V(G),E7(日)∈E(G),并且日中边 的重数不能超过G中对应边的重数,则称日是G的子图(Subgraph),记作H£G. 如果日是G的子图,并且H≠G,则称H是G的真子图(Proper subgraph),并且记作 H c G. 已知图日是G的子图,并且矿’(日)=V(G),则称日是G的生成子图(Spanningsubgraph).如图1.3所示。
1.5导出子图与边导出子图 已知图G=(V,E),S是y的一个非空子集,以S为顶点集,以两端点均在S中的边的的全体为边集所组成的子图,称为由S导出的G的子图,记作G〔S】.或简称G〔S】是G的导出子图(Induced Subgraph). 已知图G=(y,E),E’是E的一个非空子集,以E’为边集,以E’中边的全体端点为顶点集所组成的子图,称为由F导出
上一篇:
数控车床全闭环控制系统的研究
下一篇:
临床前药物安全性评价中毒性病理学新技术的应用