给定无向图G =(V，E)，确定G是否为完整图 [英] Given an undirected graph G = (V, E), determine whether G is a complete graph

问题描述

我很确定这个问题是P而不是NP，但是我很难提出多项式绑定算法来解决它.

I'm pretty sure this problem is P and not NP, but I'm having difficulty coming up with a polynomially bound algorithm to solve it.

推荐答案

您可以:

1. 检查图中的边数是否为 n(n-1)/2 .
2. 检查每个顶点是否连接到精确的 n-1 个不同的顶点.

1. check that number of edges in the graph is n(n-1)/2.
2. check that each vertice is connected to exaclty n-1 distinct vertices.

这将以多项式的 O(V²)运行.

希望有帮助.

这篇关于给定无向图G =(V，E)，确定G是否为完整图的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！