一个无向图包含 2020 条边,如果图中没有自环和重边,请问最少包含多少个结点?
时间: 2024-05-24 09:10:42 浏览: 7
由图论知识可知,无向图中的边数最多为 $\frac{n(n-1)}{2}$,其中 $n$ 为结点数。因此,当 $\frac{n(n-1)}{2}\geq 2020$ 时,这个无向图才有可能包含 2020 条边。
解得 $n\geq 64$,因此最少包含 64 个结点。但是,这只是一个下界,实际上可能存在更小的无向图满足条件,因此不能确定最少结点数。
相关问题
若无向图有m条边,则邻接表中有几个结点
邻接表是一种表示无向图的数据结构,它由一系列链表组成,每个链表对应图中的一个结点,记录了与该结点相邻的其他结点。对于无向图,每条边在邻接表中都会被记录两次,因此邻接表中的结点个数为边数的两倍。
设图中有m条边,则每条边都会被记录两次,所以邻接表中的结点个数为2m。因此,无向图有m条边时,邻接表中的结点个数为2m。
若无向图中有n个顶点、e条边,则它的邻接表需多少个头结点,多少个表结点
对于一个无向图,每个顶点的邻接表中需要包含与其直接相邻的所有顶点。因此,我们需要n个头结点,每个头结点对应一个顶点,用于存储该顶点的相关信息,如顶点编号、入度、出度等等。同时,每个表结点用于记录与该顶点直接相邻的另一个顶点的信息,需要有e个这样的表结点,每个表结点包括两个字段:邻接点编号和指向下一个邻接点的指针。因此,总共需要n个头结点和e个表结点。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)