买专利卖专利找龙图腾，真高效！ 查专利查商标用IPTOP,全免费！专利年费监控用IP管家,真方便！

龙图腾网获悉南开大学申请的专利一种基于双完全独立生成树的保护路由方法获国家发明授权专利权，本发明授权专利权由国家知识产权局授予，授权公告号为：CN119544584B 。

龙图腾网通过国家知识产权局官网在2025-07-08发布的发明授权授权公告中获悉：该发明授权的专利申请号/专利号为：202411696406.8，技术领域涉及：H04L45/02；该发明授权一种基于双完全独立生成树的保护路由方法是由胡洋;宁博设计研发完成，并于2024-11-25向国家知识产权局提交的专利申请。

本一种基于双完全独立生成树的保护路由方法在说明书摘要公布了：本发明为一种基于双完全独立生成树的保护路由方法，在一个节点数不小于14，边数大于（节点数‑2）（节点数‑3）2+4的网络拓扑结构中，得到一个有双完全独立生成树的网络，拓宽了对最小度的限制。利用边数条件来构造网络中的拓扑结构，这意味着本发明适用于更复杂和多样化的图结构，在广泛的图形拓扑中都有应用潜力，克服了现有技术无法在一般图中应用的局限性。本发明简化优化了构造过程，提高了完全独立生成树构造的普遍性和易用性。

本发明授权一种基于双完全独立生成树的保护路由方法在权利要求书中公布了：1.一种基于双完全独立生成树CIST的保护路由方法，其特征在于，所述方法包括以下步骤： 步骤1、建立一个路由网络拓扑结构，用n来表示图中的所有节点个数，且n≥14，网络拓扑结构的边数大于n-2n-32+4，此时度小于n2的节点个数x的取值范围为0≤x≤4，用G表示图，VG表示节点集，EG表示边集；确定度小于n2的节点分别记为u1,u2,…,ux，且这些节点的度随着下标数字的增大而增大； 步骤2、如果度小于n2的节点个数x为4，则按照以下具体步骤，找到CIST-划分： 从VG中任取个度大于等于n2的节点，加上度小于n2的两个节点，放入一个空的点子集V1中，再把剩下的节点放入另一个点子集V2中，得到{V1，V2}就是CIST-划分； 步骤3、如果度小于n2的节点个数为3，则按照以下具体步骤，找到CIST-划分： 从u1的邻点中任取两个不同的节点，记为和从u2的邻点中任取两个不同的节点，记为和从u3的邻点中任取两个不同的节点，记为和从中取出一个度最小的点，记为u'；并找到u'的个非邻点，记为点子集S；令V2＝VG\V1；此时，{V1，V2}就是CIST-划分； 步骤4、如果度小于n2的节点个数为2，则按照以下具体步骤，找到CIST-划分： 步骤4-1：如果在VG中存在一个节点w使得{w，u1，u2}这三个点之间的边大于等于2且u1的所有邻点还包含了除{w，u2}以外的节点，则按照4-2步骤执行，否则按照步骤4-3执行； 步骤4-2：从VG中找到两个节点和使得和从w的邻点中任取个不包含于节点，记为子集U；从VG中找到一个节点z使得满足z与U∪{w，u1，u2}中的一个节点相邻；令V1＝U∪{u1，u2，w，z}，V2＝VG\V1，转到步骤4-6，判断V2的导出子图是否连通； 步骤4-3：从u1的邻点中任取两个节点，记为和从u2的邻点中任取两个节点，记为和此时和与和不重合；如果和相邻，转到步骤4-4，否则转到步骤4-5； 步骤4-4：从的邻点中找到不包含于的个节点，记为点子集S；令V2＝VG\V1；转到步骤4-6； 步骤4-5：找到和的不包含于的一个共同邻点，记为u'；从的邻点中找到不包含于的个节点，记为点子集P；令V1＝P∪{u1，V2＝VG\V1；转到步骤4-6； 步骤4-6：如果V2的导出子图G[V2]是不连通的，转到步骤4-7；否则，转到步骤4-8； 步骤4-7：从节点子集V1中找到一个非割点的节点z2使得令U1＝V1\{z2}，U2＝VG\U1；此时，{U1，U2}就是CIST-划分； 步骤4-8：如果由V1和V2所生成的二部图BV1，V2，G是不含树分支的，转到步骤4-9，否则转到步骤4-10； 步骤4-9：此时，{V1，V2}就是CIST-划分； 步骤4-10：令H是一个仅包含BV1\{u1，u2}，V2，G-{u1，u2}的所有树分支的子图；从V2中找到一个不属于H的节点，记为w2；令U1＝V1∪{w2}，U2＝VG\U1；此时，{U1，U2}就是CIST-划分； 步骤5、如果度小于n2的节点个数为1，则按照以下具体步骤，找到CIST-划分： 步骤5-1：从u1的邻点中任取两个不同的节点，记为和其中是u1的所有邻点的度最小的那一个节点；从的邻点中找到不包含的个节点，记为节点子集S；令V2＝VG\V1；如果V2的导出子图G[V2]不连通，则转到步骤5-2，否则转到步骤5-3； 步骤5-2：从V1中任取一个非的节点，记为w；令U1＝V1\{w}，U2＝VG\U1；此时，{U1，U2}就是CIST-划分； 步骤5-3：如果BV1，V2，G是不含树分支的，转到步骤5-4，否则转到步骤5-5； 步骤5-4：此时，{V1，V2}就是CIST-划分； 步骤5-5：令H是一个仅包含BV1\{u1}，V2，G-{u1}的所有树分支的子图；如果V1包含H的一个叶子节点，则转到步骤5-6，否则转到步骤5-7； 步骤5-6：从V1中任取一个非u1且不包含于H的节点，记为z；令U1＝V1\{z}，U2＝VG\U1；此时，{U1，U2}就是CIST-划分； 步骤5-7：从V2中任取一个非且不是H的节点，记为w；令U1＝V1∪{w}，U2＝VG\U1；此时，{U1，U2}就是CIST-划分； 步骤6、如果度小于n2的节点个数为0，则按照以下具体步骤，找到CIST-划分： 步骤6-1：找到G的一个哈密顿圈，设为C＝v1v2…vnv1；令V2＝VG\V1；转到步骤6-2； 步骤6-2：如果由V1和V2的所生成的二部图BV1，V2，G是不含树分支的，转到步骤6-3，否则转到步骤6-4； 步骤6-3：此时，{V1，V2}就是CIST-划分； 步骤6-4：令H是一个仅包含BV1，V2，G的所有树分支的子图；如果V1包含H的一个叶子节点，则转到步骤6-5，否则转到步骤6-8； 步骤6-5：从V1任取一个不在图H中的节点，记为z1；如果BV1\{z1}，V2∪{z1}，G没有树分支，则转到步骤6-6，否则转到步骤6-7； 步骤6-6：令U1＝V1\{z1}，U2＝VG\U1；此时，{U1，U2}就是CIST-划分； 步骤6-7：在V1中任取一个不包含于H的节点，记为z2；令U1＝V1\{z2}，U2＝VG\U1；此时，{U1，U2}就是CIST-划分； 步骤6-8：在V2中任取一个不包含于H的节点，记为z；令U1＝V1∪{z}，U2＝VG\U1；此时，{U1，U2}就是CIST-划分； 步骤7、通过CIST-划分，统一记作{U1,U2}，找到该网络中的两个完全独立生成树，在双完全独立生成树的基础上，配置网络的通信路由。

如需购买、转让、实施、许可或投资类似专利技术，可联系本专利的申请人或专利权人南开大学，其通讯地址为：300350 天津市津南区海河教育园区同砚路38号；或者联系龙图腾网官方客服，联系龙图腾网可拨打电话0551-65771310或微信搜索“龙图腾网”。