BCSP-X · 2024 BCSP-X 下半年活动基础知识测评（初中组） 第 10 题

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

这题考二分图的最大边数，核心是把16个点分成两堆，让两边点数越接近越好，再算两堆之间能连的边总数。

很多同学会下意识想‘每条边连两个点，16个点最多16条’，或者觉得分两堆就是8+8，然后误以为每堆内部还能连，忘了二分图定义里‘每堆内部不能有边’。还有人会拿完全图边数公式C(16,2)=120去减，结果算错。其实只要记住：二分图的最大边数就是把点平分，两堆之间全连，堆内不连。

这题考什么

题目问的是16个顶点的二分图至多能有多少条边。二分图的核心定义是：把顶点分成两个集合，集合内部的顶点之间没有边，边只能连在两个集合之间。所以求最大边数，就是要让两个集合尽可能大，同时还能互相连边。

概念：二分图怎么才能让边最多

既然边只能跨集合，那我们就得把16个点分成两堆。为了让边数最大，显然应该让两堆的点数尽量相等，因为如果一堆多一堆少，多出来的点没法和少的那堆连（已经连满了），只能自己跟自己连，但自己跟自己连是不允许的。所以最优分法是8和8。

命题人怎么挖坑

命题人最喜欢在这里设坑：要么让你算完全图的边数（C(16,2)=120），然后让你减去堆内的边，但你可能会算错堆内边数；要么让你直接想‘16个点，每个点连16条边’，结果忘了每个边被算了两次；还有人会以为分成8和8后，每堆内部还能连，完全忘了二分图定义。这些坑都是对二分图概念理解不深导致的。

拿到题先想什么→从哪入手

拿到题先想：二分图的最大边数就是把点平分，两堆之间全连。所以第一步就是把16个点分成两堆，每堆8个。第二步就是算两堆之间能连多少条边。因为每堆有8个点，两堆之间每对点都能连一条边，所以就是8×8=64条。

具体怎么算

把16个点分成两堆，每堆8个。两堆之间可以连的边数就是8×8=64。这就是答案。

避坑

最容易错的就是把完全图的边数C(16,2)=120当成答案，或者算成8+8=16，或者算成8×8=64但忘记这是两堆之间的边数。其实只要记住：二分图的最大边数就是把点平分，两堆之间全连，堆内不连。所以答案就是8×8=64。

考频与趋势

从历年考频看，二分图相关题目在信息学竞赛中出现频率较高，尤其是在图论部分。这类题目通常考查对二分图定义的理解和应用，以及简单的计算能力。从趋势来看，未来可能会继续考查二分图的最大边数、最小顶点覆盖等问题。

预测

基于现有考频数据，未来可能会继续考查二分图的最大边数、最小顶点覆盖等问题。暂无足够依据预测具体题目形式，但建议重点复习二分图的定义和性质，以及相关的图论算法。