GATE | GATE-CS-2006 |问题72

2号 ^N 图G的顶点对应于大小为n的集合的所有子集，即n>=6。G的两个顶点是相邻的当且仅当相应的集合正好在两个元素中相交。

G中顶点的最大度数为： （A） （n/2）C2*2 ^n/2 （B） 2. ^n-2 （C） 2. ^n-3 *3 （D） 2. ^n-1 答复: （C） 说明： 最大值 _K （kC2*2） ^{（n）−（k）} )=3C2*2 ^（n）−3) =3*2 ^（n）−3) . 这个问题的小测验