ISRO | ISRO CS 2009 |问题51

一个有n个顶点和k个分量的简单图（没有平行边或循环的图）最多可以有 （A） n边 （B） n-k边 （C） （n）− k） （n）− k+1）边 （D） （n）− k） （n）− k+1）/2边 答复: （D） 说明： 设G是一个有k个分量的图。让n _我 是i中的顶点数 ^th 组件，其中1≤ 我≤ k、 然后，G中的边数等于其每个分量中的边之和。 所以，如果每个分量都是一个完整的图，G有最大的边数。 因此，图G中的最大可能边数为：

在每种情况下− k） （n）− k+1）/2将大于或等于上述表达式。

因此，在最大情况下，可以有（n− k） （n）− 具有n个顶点和k个分量的简单图中的k+1）/2边。 这个问题的小测验