Connectivity of Hypercube 超方形的联通度

什么是连通度 Connectivity? 对图论或数据结构有所了解的小伙伴应该对连通度都有所了解。 简单来说,对于一个连通图,如果去掉某个顶点 (vertex),这个图就会被分割而变成非连通图,那么这个被去掉的点就被叫做“割点 (cut vertex)”,如下图。 在这个沙漏状的图中,去掉中间的顶点后,整个图就分割成两条直线,变成了非连通图。 而连通度(Connectivity),就是对任意一个连通图来说,割点的最小值。换句话说,就是最少要去除k个点才能让一个连通图分离。 联通度又分为顶点连通度(Vertex Connectivity)和边连通度(Edge Connectivity),分别用K