一个无向连通图有n条边求最少顶点个数推导过程

Question

一个无向连通图有n条边求最少顶点个数推导过程
一个无向图有十个顶点30条边，采用邻接矩阵存储，邻接矩阵零元素个数

Answer 1

对于一个无向连通图，若要使边的数量最大，那么图需要形成一个完全图。对于完全图，每个顶点都与其它所有顶点相连，因此，有n个顶点的完全图的边数为n*(n-1)/2。如果我们要最小化顶点的数量，那么我们需要的就是最小的n，使得n*(n-1)/2大于或等于已知的边数。

我们可以通过解这个二次方程来找到n的值。在这里，我们不能直接找出n的表达式，因为n需要是一个整数。因此，我们需要对解进行向上取整，以保证边数大于或等于已知的边数。

具体来说，如果已知边数为m，我们需要找到最小的n，满足：
n*(n-1)/2 >= m
这是一个关于n的二次不等式，解这个不等式可以得到n的最小值。

关于邻接矩阵的问题，一个有10个顶点、30条边的无向图，其邻接矩阵为一个10x10的矩阵。在无向图的邻接矩阵中，如果两个顶点之间有边，那么对应的元素值为1，否则为0。对于无向图，其邻接矩阵是对称的，也就是说，矩阵的上半部分和下半部分是一样的。

因此，所有的边都可以在矩阵的上半部分或下半部分找到，每条边对应矩阵中的一个1。我们有30条边，因此，上半部分或下半部分有30个1。对角线上的元素表示一个顶点与自己是否有边，对于无向图，通常我们假设一个顶点不能与自己形成边，所以对角线上的元素为0。

因此，零元素的数量为：
10x10矩阵的总元素数100
减去上半部分或下半部分的1的数量30
再减去对角线上的元素数10
所以，零元素的数量为100 - 30 - 10 = 60。