6.1 选择题：度、连通与极值

先识别有向/无向、简单/多重、连通/强连通。极值题要同时满足全部限定，不能只套一个公式。

手工状态

有向边 A→B、B→C、C→A、C→D：出度为1,1,2,0，入度为1,1,1,1。A、B、C 强连通，D 只能被到达，故不与前三者同强连通分量。

结构与代码

多选：A 无向图奇度顶点数为偶数；B 有向图入度和等于出度和；C 连通 n 点图至少 n-1 边；D n-1 边图必连通。答案 A、B、C；D 可有环并含孤点。

正确性依据

奇度顶点成偶数由度数和为偶数推出；连通图取一棵生成树即给下界 n-1。

错解反馈

把边数 n-1 当连通充分条件；认为单向可达就是强连通；漏掉孤立顶点度为0。

迁移训练

6 点无向图有两个连通分量，生成森林有几条边？答案6-2=4。说明每个分量分别是一棵树。