大门|大门-CS-2002 |问题25

无自环n节点无向图的最大边数为 （A） N ^2. （B） n（n-1）/2 （C） n–1 （D） （n+1）（n）/2 答复: （B） 说明： 背景要求-基础 组合数学

由于给定的图是无向的，这意味着边的顺序无关紧要。

由于我们必须在所有可能的顶点对之间插入一条边，因此问题归结为从顶点集中选择大小为2的子集的数量。

由于顶点集的大小为n，因此此类子集的数量由二项式系数C（n，2）（也称为“n选择2”）给出。使用二项式系数的公式，C（n，2）=n（n-1）/2。E

这一解释是由 Pranjul Ahuja。 这个问题的小测验