A graph with 90 vertices and 20 edges must have at least __ connected component(s).
时间: 2024-06-13 08:06:59 浏览: 192
数据结构英文教学课件:19_Graph_02.pdf
根据引用中提供的信息,我们可以使用以下公式来计算至少有多少个连通分量:
连通分量数 = 顶点数 - 边数 + 连通块数
其中,连通块数是指无法从图中任何一个顶点到达的顶点数。因此,我们可以将上述公式中的顶点数和边数代入,得到:
连通分量数 = 90 - 20 + 连通块数
因为每个连通分量至少包含一个顶点,所以连通块数的最小值为1。因此,我们可以将连通块数取1,得到:
连通分量数 = 90 - 20 + 1 = 71
因此,一个有90个顶点和20条边的图至少有71个连通分量。
阅读全文