从连通图中挑选任意个不相邻的顶点的方法数是多少?
3211
2020.06.17
发布于 未知归属地

给定一个包含n个顶点的连通图,顶点编号从1n,从中挑选任意个不相邻的顶点,如何求一共有多少种方法(mod 10^9+7)?

例如这个图:
b.jpg

可以有以下的挑选方法:
{},{1},{2},{3},{4},{5},{6},
{1,3},{1,4},{1,5},{1,6},{2,4},{2,6},{3,5},{3,6},{5,6},
{1,3,5},{1,3,6},{1,5,6},{3,5,6},
{1,3,5,6}
一共21种方法。

这个问题怎么解,有多项式时间复杂度的解法吗?

评论 (2)