大门|大门-CS-2004 |问题90

在n个标记的顶点上存在至少（n）个的图 ^2. –3n）/2边？

（A） A. （B） B （C） C （D） D 答复: （D） 说明：

设图的边总数为e，顶点总数为e N .

因此，一个有e个边和v个顶点的图的形成方式的总数由我们在v个边中选择e个边的方式的总数给出

i、 e。

C（v，e）

现在，这里是e= （n） ² -3n）/2 和 n=2（v）/1 （简单图形中的最大边数） .

所以我们可以在C（v）中选择一条边， （n） ^2. -3n）/2）方式。

因为一个图要选择的最小边数是（n ^2. -3n）/2。

因此，可能的图形总数为：

C（v，e）+C（v，e+1）+C（v，e+2）+C（v，v）。

C（v，v-e）+C（v，v-（e+1））+C（v，v-（e+2））+C（v，v-v）。

从v-e开始= n（n-1）/2- （n） ^2. -3n）/2=n

因此

C（v，n）+C（v，n-1）+C（v，n-2）+C（v，0）。

解决这个问题我们会得到

这个解决方案由Namita Singh提供。

这个问题的小测验