Man*_*tis 12 language-agnostic graph-theory subgraph
是否有已知的算法或方法来查找图中的所有完整子图？我有一个无向的,未加权的图形,我需要找到其中的所有子图,其中子图中的每个节点都连接到子图中的每个其他节点.
是否有现有的算法？
pol*_*nts 15
这被称为集团问题 ; 它很难,一般都是NP-complete,是的,有很多算法可以做到这一点.
如果图形具有附加属性(例如它的二分),则问题变得相当容易并且在多项式时间内可以解决,但是否则它非常困难,并且仅对于小图形是完全可解的.
在计算机科学中,集团问题指的是与在图中找到特定完整子图("集团")相关的任何问题,即,每对元素连接的元素集.
Clique问题包括:
- 找到最大集团(一个顶点数量最多的集团),
- 在加权图中找到最大权重集,
- 列出所有最大派系(不能放大的派系)
- 解决测试图表是否包含大于给定大小的集团的决策问题.
这些问题都很难:集团决策问题是NP完全的(Karp的21个NP完全问题之一),找到最大集团的问题既是固定参数难以处理又难以近似,并列出所有最大集团可能需要指数时间因为存在具有指数多个最大集团的图.然而,存在针对这些问题的算法,这些算法以指数时间运行或者在多项式时间内处理某些更专业的输入图.