NOIP 提高 2013 第一轮 第 11 题：二分图是指能将顶点划分成两个部分，每一部分内的顶点间没有边相连的简单无向图。

题目

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

选项

• A. 18
• B. 24
• C. 36
• D. 66

答案

C

题解

考点定位

本题考「二分图最大边数」,对应大纲 3.3.1 二分图（难度【2】）。

解题过程

12 点二分图：x(12−x) 最大于 x=6：6×6=36。

选 C。

易错提醒

① 均分最大化；② K₆,₆ 取得上界。