根据视频，什么是二分图？
二分图是指其顶点被划分为两个不相交的集合的图，这两个集合分别称为左顶点和右顶点。每个顶点恰好属于一侧，并且每条边都连接一个左顶点和一个右顶点。
适用条件
- 该图是一个简单图。
- 顶点集被划分为两个不相交的子集。
- 每条边的两个端点属于相对的两边。
理解与推导
- 识别两个不相交的顶点集。
- 验证每个顶点恰好属于其中一个集合。
- 检查每条边是否将第一个集合中的一个顶点与第二个集合中的一个顶点相连。
例子
视频显示了两个分开的椭圆，一个包含 G 顶点，另一个包含 B 顶点，然后只在椭圆之间绘制交叉的边。
容易误解的地方
- 认为二分图只需要将顶点分成两组，而边仍然可以任意连接。
- 假设边可以连接同一侧的顶点。
观看对应讲解
YouTube2.11.7 二分图匹配
0:22 – 0:37原站看这一段 ↗
继续追问
答案依据视频资料生成并经过独立核验。若有疑问，请核对原视频或联系原作者。