NOIP 提高组初赛 · NOIP 2013 提高组初赛试题 第 11 题

二分图是指能将顶点划分成两个部分，每一部分内的顶点间没有边相连的简单无向图。 那么，$12$ 个顶点的二分图至多有（ ）条边。

拿到题先抓定义：二分图只能跨组连边。把12个顶点拆成两组a和12-a，边数就是a×(12-a)。这是个二次函数，对称轴在a=6，直接算最大值36。

学生最容易把二分图当成'完全图砍一半'，以为12个顶点的完全图有66条边，一半就是33条，选B。其实完全图里顶点之间任意两点都有边，而二分图要求同组顶点之间不能有边，所以不能简单除以2。还有人会误用三角形不等式或以为边数只和顶点数线性相关，忘了跨组连边的本质是'两集合的笛卡尔积'，导致算出错误数值。

考点定位

这道题考查二分图的最大边数，核心就是理解二分图的结构约束。

概念落地

二分图的关键在于：顶点能被分成两个不相交集合，集合内部没有边，所有边都必须连接两个集合。这意味着，如果两组顶点数分别是a和b，那么最多能连的边数就是a×b（每个a集合的顶点都能和每个b集合的顶点连一条边）。