任意非赋权图同构的判定算法

摘要

本发明涉及一种判定任意非赋权图同构的算法，所述算法包括针对任意非赋权图的同构判定，提出一种新的算法，即在两个图中分别依次删除最大度数顶点及其关联的边，并对其邻点进行标记，在余下的子图中,如法炮制,直至余下的子图为空图，然后按照顶点标记判断两图是否同构，通过计算、比较两图的度序列、被删除的顶点的度数以及它们邻点的度集合,证明两图同构问题的复杂度是多项式的。本发明方法结果准确，计算简单。

主权项

一种任意非赋权图的同构的判定算法，包括以下步骤：首先写出两个图的度序列，若两图的度序列不同则一定不同构，若相同进行以下判断：S1：如果G与F是正则图，对于G固定去掉任意一个顶点v_i及其邻点以及它们关联的边，写出其剩余子图的度序列，并对v_i的邻点重新标号；对于图F首先去掉任一顶点v_j和它的邻点及它们关联的边，写出其剩余子图的度序列，并对v_j的邻点重新标号，然后使j取遍F的所有顶点，分别写出各自剩余子图的度序列,并对v_j的邻点重新标号，若存在一个j＝k使得G的剩余子图与F的剩余子图的度序列与重新标号都相同，则认为v_i和v_k是对应顶点，对它们的邻点给予相同的标记，在两图中分别删除v_i和v_k及其关联的边，跳出循环判断剩余子图的同构性转S5，否则输出两图不同构；S2：如果G与F不是正则图：（1）若最大度顶点唯一，则此对顶点为对应顶点，将此对顶点标号为p（p∈{1,2,…,n}）号顶点，并对其所有邻点做第p次标记，然后删除此对顶点及其所关联的边后判断剩余子图的同构性，转S5，否则转（2）；（2）若最大度顶点不唯一，则根据度序列中的标注把顶点集合分成最大度顶点和非最大度顶点两个子集合，去掉两个顶点集合间的关联边，分别得到两个生成子图G′,G″和F′,F″，转S3；S3：分别写出两对生成子图G′和F′，G″和F″的度序列,若两对度序列中有一对度序列不相等则两图不同构；否则转S4；S4：（1）若G′和F′为正则图，对于G固定去掉G′中任意一个顶点v_i及其邻点以及它们关联的边，写出其剩余子图的度序列,并对v_i的邻点重新标号；对于图F首先去掉F′中与G′中v_i有相同标记的任意一个顶点v_j和它的邻点以及它们关联的边，写出其剩余子图的度序列，并对v_j的邻点重新标号，然后使j取遍F′中与G′中v_i有相同标记的所有顶点，分别写出各自剩余子图的度序列,并对v_j的邻点重新标号，若存在一个j＝k使得G的剩余子图与F的剩余子图的度序列与重新标号都相同，则认为v_i和v_k是对应顶点，对它们的邻点给予相同的标记，在两图中分别删除v_i和v_k及其关联的边，跳出循环判断剩余子图的同构性转S5，否则输出两图不同构；（2）若G′和F′不是正则图，令G′：=G,F′：=F，转S2；S5:判断剩余子图的同构性：若剩余子图为空图且有相同的标记序列，则两图同构；若剩余子图为空图但标记序列不同，则两图不同构；若剩余子图为非空正则图，则分别令各自剩余子图为G和F，转S1；若非空剩余子图不是正则图，则分别令各自剩余子图为G和F，转S2。