图的同构判定算法研究

来源 :复旦大学 | 被引量 : 0次 | 上传用户:haijiehahaha
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
本文对图的同构判定提出了独特的思路,即将图的同构问题转化为电路的相同问题,从而得到了两图同构的又一必要(几乎充分)条件。   本文分析了判定图的同构所需要的条件,目前存在的图的同构判定算法以及这些算法的有效性;提出了一种新的同构判定算法,电路模拟法,并介绍了此方法所涉及的新概念,相同电路、图的伴随电路、全激励、节点电压序列以及节点电压序列集;详细介绍了电路模拟法的基本算法以及改进后的算法实现步骤,算法实现的框图,并将本算法与别的判定算法有效性进行了比较;利用电路模拟法对几组图进行了同构判定,证明了本算法的有效性,在大多数情况下都能快速有效的进行判定。   本文从节点电压序列内部的电压值是否相等和节点电压序列之间是否相等两个方面着手确定图的顶点之间的对应关系,因此本文的算法对判定绝大多数图是否同构是有效的且快速的。   
其他文献
在机械传动系统中,扭矩是反映系统性能的最典型机械量之一。扭矩测试已成为各种机械产品的开发研究、质量检验、优化控制、工况监测和故障诊断等必不可少的内容,因此利用合适
语音识别是当今人工智能领域的研究热点,目前,它越来越广泛地应用于社会生活的各个方面,提高了人机交互性,发挥了很好的社会效益。然而在实际环境中存在着很多不利因素影响着
本文旨在基于安全套接字层(Secure Sockets Layer, SSL)网络安全协议设计并实现一款采用Android操作系统的金融终端,该终端要求能在复杂的公共网络环境中安全稳定地运行,可实现
本文通过对荣华二采区10
期刊
OPC(OLEforProcessControl)规范是为了解决不同厂商提供的过程控制设备和商业应用软件之间不能自由通信的问题。OPC技术以OLE/COM/DCOM技术为基础,它的发展非常迅速,应用也越来
现代通信技术迅猛发展,拥有更宽工作带宽的通信系统更加受到青睐。作为系统的关键部分,功率放大器的工作带宽和效率直接影响到系统的整体性能。传统功放采用基于硅(Si)或砷化
本文简要介绍了虚拟仪器技术在仪器自动控制领域的特点,论述了现代仪器控制模型和其中涉及到的主要技术标准如GPIB接口、RS232接口等,深入分析了VISA(Virtual Instrument Sof
小麦花药培养是小麦单倍体育种的重要手段,是小麦品种改良和创造新种质重要途径之一。黑龙江省小麦单倍体育种采用的技术体系培养效率一直不理想,近年来为了提高小麦花药培养能力的研究主要集中在培养体系的选择和培养条件优化上。本试验引进匈牙利花药培养技术体系W14-F/190-2-Cu,与我省小麦单倍体育种中长期采用的技术体系进行比较,以选择适合黑龙江省普通春小麦品种和合成小麦品种花药培养的最佳培养体系。人工
学位
外周神经损伤可以诱导长时程的神经病理性痛。发生在包括受损神经、初级感觉神经元和相应支配的脊髓背角区域的多重的病理改变导致了神经病理性痛的起始、发展和长时程的维持