发明名称 |
一种基于谱分析的图同构判断方法 |
摘要 |
本发明属于集成电路领域,涉及一种基于谱分析的图同构判断方法;该方法将大规模纯电阻网络图建模为非混合无向简单图,将二维平面图映射成一维分布,根据处理后的一维分布的情况来判定两图是否同构。本发明方法对无向非混合简单图具有判断结果准确、快速的特点,特别是对于大规模无向非混合简单图,所述方法的速度明显快于目前性能较好的Nauty方法,能很好地应用于大规模集成电路中相同子电路的判定、有机化学中同分异构体的判定等领域。 |
申请公布号 |
CN104376139A |
申请公布日期 |
2015.02.25 |
申请号 |
CN201310357552.3 |
申请日期 |
2013.08.15 |
申请人 |
复旦大学 |
发明人 |
曾璇;谢敏;杨帆 |
分类号 |
G06F17/50(2006.01)I |
主分类号 |
G06F17/50(2006.01)I |
代理机构 |
上海元一成知识产权代理事务所(普通合伙) 31268 |
代理人 |
吴桂琴 |
主权项 |
一种基于谱分析的图同构判断方法,其特征在于,将大规模纯电阻网络图建模为非混合无向简单图,将二维平面图映射成一维分布,根据处理后的一维分布的情况来判定两图是否同构,其包括:对图的Laplace矩阵进行谱分析,计算出第二小特征值所对应的特征向量,对该特征向量进行处理,比较两处理后的特征向量是否相等,若相等则两图同构;若不相等,则对升序排列的第二小特征值对应的特征向量进行划分组成粗化图,对粗化图进行谱分析判断同构,若粗化图不同构,则两图不同构;若粗化图同构,则再对新点里的子图进行谱分析判断同构,若子图也一一同构,则两图同构。 |
地址 |
200433 上海市杨浦区邯郸路220号 |