基于DNA计算的最大流算法在图聚类上的应用研究

摘要

提出使用DNA计算解决图聚类问题,提供了使用DNA两阶段法求最小切进行图分析的新思路.在使用两阶段算法前,首先根据一定的规则对给定图进行构造,使其适合使用DNA两阶段算法.在两阶段算法中,使用DNA分子对图中顶点、边进行编码.经过生化反应生成关于构造图从选定源节点到槽节点的所有路径,再利用电子计算求出关于给定源节点和槽节点的最小切,从而完成对图的划分,然后迭代执行两阶段算法直到获得满意的聚类数目为止.给出了算法的证明,说明了算法的可行性.