计算机辅助下的图论问题研究

来源 :华南农业大学 | 被引量 : 0次 | 上传用户:luowenying124
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
图论是目前发展迅速、应用广泛的一个数学分支。在许多学科领域中,如运筹学、信息论、控制论、量子化学以及计算机科学等,其研究对象都可以抽象为图论中相关的概念,因此图论研究为这些学科中离散性问题的解决提供了新的办法。随着计算机技术高速发展,计算机技术与图论的交叉研究领域成为目前国际上图论研究的重要发展方向。本文旨在探索如何有效地使用计算机工具解决图论中的相关问题,推广和发展国内外图论的一些结果。主要成果如下:   (1)在计算机网络研究中,网络拓扑结构可以抽象为图论中的图,网络防病毒能力与图最大谱半径大小成反比。本文研究具有最大谱半径的图的判定问题。本文根据两类图C(n,k,d,t)和H(n,k)的特征,提出了图G(n,k,d,t)与图n(n,k)的邻接矩阵构造算法,编程计算了e=n+(d-l/2)+t-1,e≦2n-3时两类特殊图G(n,k,d,t)和H(n,k)的谱半径,确定了n≤200时w(n,e)中具有最大谱半径的图,并得到结论:当(n,e)取值为(60,69),(68,88),(80,85)时,图G(n,k,d,t)与图H(n,k)谱半径相同;当n∈[4,24]时,图G(n,k,d,t)具有最大谱半径。这部分结论推广了已有的研究成果。   (2)对于n阶反正则序列实现的连通图An和非连通图Anc,在Behzad(1967)和Merris(2003)研究的基础上,本文证明了反正则连通图An中含有K3子图数目△n。的递推公式△n=△n-2+en-2以及反正则非连通图Anc中含有K3子图数目△nc的递推公式△nc=△n-1+en-l-enc.   (3)提出了2-反正则图的概念,并根据度序列判定定理和同构图定义,实现了序列可图化和同构图的判定算法,得到n阶(n≤20)2-反正则可图化序列和对应的所有n阶(n≤10)非同构简单连通图。   本文所做的工作进一步完善了图谱理论的相关结论,为解决Cvetkovic的猜想创造了条件,发现并证明反正则图中含有K3子图数目的递推公式,以及获得部分2-反正则序列的所有非同构简单连通图,为进一步研究2-反正则图奠定了一定的基础。
其他文献
现代信息技术的发展促使世界各国进行教育信息化的改革。用IT技术辅助教学,特别是网络教学成为信息化教育的主要应用之一,它在提高教学效率的同时,缓解了知识爆炸对教育所带来的
短波通信是军事通信中不可替代的一种军事指挥手段。如何保证并提高短波电台通信质量,进而保证军事作战指挥通信的可靠性和安全性,成为军用短波电台生产厂家的重要目标。 传
传统的Key-Value存储系统受限于操作系统的内核处理开销,难以发挥底层新型网络和存储硬件设备高吞吐与低延迟的性能优势。用户级IO技术将传统内核功能转移到用户空间进行定制
伴随着软硬件技术的飞速发展,电子计算机已逐渐深入到人们生产生活的方方面面,这使得人机交互成为一个在理论和实践上都具有重要意义的研究课题。当前的人机交互主要依赖于键盘
学位
数字多媒体技术、计算机视觉技术以及三维图形硬件的飞速发展拓展了三维图形的应用前景,而三维造型技术与三维扫描技术的日益普及,大大的扩展了可供使用的三维模型的数量。这些
自从遥感技术发明和应用于信息获取以来,人类对外部世界的认知就发生了根本的变化,人们获取信息的深度和广度得到前所未有的提高。同时,航空遥感影像处理技术作为遥感技术的重要应用方向,也得到了迅速发展。但是,面对海量遥感数据,如何自动识别和提取影像中的地物信息也成为图像处理、模式识别、人工智能和机器视觉等领域面对的问题和难点。从航空影像提取道路和房屋已有二十多年的历史,但是很多模型都是建立在规则的地物信息
20世纪70年代后期Black-Scholes的期权定价模型出现后,复杂的数学模型、数值分析和大规模计算在金融中的应用越来越多。计算金融就是用计算机实现金融模型和系统的数学方法,其
学位
本文针对基于马尔可夫随机场模型(MRF)的图像分割技术进行研究,通过深入分析马尔可夫随机场模型用于图像分割时的优缺点,提出了改进方案,将其用于单帧图像的无监督分割和动态场
随着网络的普及,各地各类学校对数字化校园的建设有增无减。此前数字化校园一直处于现建现用的初级阶段。由于网络规模的扩大,信息量剧增、开放性日益增强,网络资源缺乏高效统一
随着现代科学技术的飞速发展、计算机的普及应用以及企业信息化进程的不断加快,办公自动化从上世纪50年代提出至今的半个世纪里,得到了空前的发展。目前,办公自动化技术越来越普