7,129
个编辑
更改
跳到导航
跳到搜索
第164行：
第164行： − + 第203行：
第203行： −
→ESU (FANMOD)算法及对应的软件
ESU和RAND-ESU两种算法都比较简捷，所以实现起来都很容易。『ESU首先找到大小为{{math|k}}的所有诱导子图的集合』，并命名这个集合为Sk。因为EUS以递归函数的形式实现，该函数的运行可以演示为深度为{{math|k}}的树状结构，称为ESU-Tree（见图）。每一个在ESU-Tree上的节点都表示递归函数的状态，这个递归函数需要两个连续集合的SUB和EXT。SUB指的是在目标网络的相邻节点上{{math|{{!}}SUB{{!}} ≤ k}}。如果{{math|{{!}}SUB{{!}} {{=}} k}}，那么这个算法可以找到一个完整的诱导子图，所以在此情况下{{math|S<sub>k</sub> {{=}} SUB ∪ S<sub>k</sub>}}。相反，如果{{math|{{!}}SUB{{!}} < k}}，那么这个算法必须把SUB扩大，才能实现基数为{{math|k}}。EXT这个集合包含了所有的满足以下两个情况的节点。第一，每个在EXT的节点必须至少与在SUB的一个节点相邻。第二，他们的下标必须比在SUB的第一个元素大。第一个条件保证了SUB节点的展开产生相关的图，第二个条件能使ESU-Tree树状图上的分支变得离散。所以，这个方法可以避免过度计算。注意，EXT集合不是一个固定的集合。所以每一步都有可能扩展满足于以上两个条件的新节点。下一步包含了在ESU-Tree分支上的子图的分类，将它们分为非同构的大小为{{math|k}}的图类。因此，ESU决定了子图的『频率以及浓度』。这一阶段的实施仅通过运用McKay的nauty算法，<ref name="mck1">{{cite journal |author=McKay BD |title=Practical graph isomorphism |journal=Congressus Numerantium |year=1981 |volume=30 |pages=45–87|bibcode=2013arXiv1301.1493M |arxiv=1301.1493 }}</ref><ref name="mck2">{{cite journal |author=McKay BD |title=Isomorph-free exhaustive generation |journal=Journal of Algorithms |year=1998 |volume=26 |issue=2 |pages=306–324 |doi=10.1006/jagm.1997.0898}}</ref>这一算法可以通过图的同构测试来把每个子图进行分类。所以，ESU能够在目标图中通过递归算法，找到所有规模大小为{{math|k}}的诱导子图集合，且使用高效的工具来确定他们的频率。
ESU和RAND-ESU两种算法都比较简捷，所以实现起来都很容易。ESU首先找到大小为{{math|k}}的所有诱导子图的集合，并命名这个集合为{{math|S<sub>k</sub>}}。因为EUS以递归函数的形式实现，该函数的运行可以演示为深度为{{math|k}}的树状结构，称为ESU-Tree（见图）。每一个在ESU-Tree上的节点都表示递归函数的状态，这个递归函数需要两个连续集合的SUB和EXT。SUB指的是在目标网络的相邻节点上{{math|{{!}}SUB{{!}} ≤ k}}。如果{{math|{{!}}SUB{{!}} {{=}} k}}，那么这个算法可以找到一个完整的诱导子图，所以在此情况下{{math|S<sub>k</sub> {{=}} SUB ∪ S<sub>k</sub>}}。相反，如果{{math|{{!}}SUB{{!}} < k}}，那么这个算法必须把SUB扩大，才能实现基数为{{math|k}}。EXT这个集合包含了所有的满足以下两个情况的节点。第一，每个在EXT的节点必须至少与在SUB的一个节点相邻。第二，他们的下标必须比在SUB的第一个元素大。第一个条件保证了SUB节点的展开产生相关的图，第二个条件能使ESU-Tree树状图上的分支变得离散。所以，这个方法可以避免过度计算。注意，EXT集合不是一个固定的集合。所以每一步都有可能扩展满足于以上两个条件的新节点。下一步包含了在ESU-Tree分支上的子图的分类，将它们分为非同构的大小为{{math|k}}的图类。因此，ESU决定了子图的『频率以及浓度』。这一阶段的实施仅通过运用McKay的nauty算法，<ref name="mck1">{{cite journal |author=McKay BD |title=Practical graph isomorphism |journal=Congressus Numerantium |year=1981 |volume=30 |pages=45–87|bibcode=2013arXiv1301.1493M |arxiv=1301.1493 }}</ref><ref name="mck2">{{cite journal |author=McKay BD |title=Isomorph-free exhaustive generation |journal=Journal of Algorithms |year=1998 |volume=26 |issue=2 |pages=306–324 |doi=10.1006/jagm.1997.0898}}</ref>这一算法可以通过图的同构测试来把每个子图进行分类。所以，ESU能够在目标图中通过递归算法，找到所有规模大小为{{math|k}}的诱导子图集合，且使用高效的工具来确定他们的频率。
'''返回'''
'''返回'''
|}
|}
===G-Tries===
===G-Tries===