一个无向图包含 2020 条边,如果图中没有自环和重边,请问最少包含多少个结点?
时间: 2024-05-24 16:10:42 浏览: 69
由图论知识可知,无向图中的边数最多为 $\frac{n(n-1)}{2}$,其中 $n$ 为结点数。因此,当 $\frac{n(n-1)}{2}\geq 2020$ 时,这个无向图才有可能包含 2020 条边。
解得 $n\geq 64$,因此最少包含 64 个结点。但是,这只是一个下界,实际上可能存在更小的无向图满足条件,因此不能确定最少结点数。
阅读全文