🏷️ 知识点：完全图
以下关于图的叙述中，正确的是（ ）。
A. 强连通有向图的任何顶点到其他所有顶点都有弧 B. 图的任意顶点的入度等于出度 C. 有向完全图一定是强连通有向图 D. 有向图的边集的子集和顶点集的子集都构成原有向图的子图
[tag_link]
正确答案：C
结论
C 正确。
推导
有向完全图对任意不同顶点都含相应方向的弧，因此任意顶点可达其他顶点，必强连通。A 把“存在路径”误作“直接有弧”；B 无一般性；D 子图中的边端点必须属于所选顶点集。
易错点
强连通要求路径可达，不要求每对顶点间都有一条直接弧；完全图才提供直接弧。
一个有 28 条边的非连通无向图至少有（ ）个顶点。
A. 7 B. 8 C. 9 D. 10
[tag_link]
正确答案：C
结论
至少需要 9 个顶点。
推导
8 个顶点的完全图恰有 C(8,2)=28 条边，但它连通。要保持非连通，可取一个 8 顶点完全子图再加 1 个孤立顶点，共 9 个顶点。
易错点
只计算 C(8,2)=28 会忽略非连通条件；8 顶点无法同时容纳 28 条边并保持非连通。
具有 51 个顶点和 21 条边的无向图的连通分量最多为（ ）。
A. 33 B. 34 C. 45 D. 32
[tag_link]
正确答案：C
结论
最多有 45 个连通分量。
推导
要让连通分量尽可能多，应把边集中在尽量少的顶点上。21 条边可由完全图 (K_7) 提供，因为 (\binom{7}{2}=21)。其余 44 个顶点均孤立，因此连通分量数为 (1+44=45)。
易错点
不要把 21 条边简单地当作 21 个分量；一条边会把两个顶点合并到同一个连通分量。极值构造应优先使用边数恰好足够的完全图，再保留孤立点。
若图的邻接矩阵中主对角线上的元素皆为 0，其余元素全为 1，则该图一定（ ）。
A. 是无向图 B. 是有向图 C. 是完全图 D. 不是带权图
[tag_link]
正确答案：C
结论
该图一定是完全图，答案为 C。
推导
主对角线全为 0 表示没有自环；其余 (n(n-1)) 个位置全为 1，表示任意两个不同顶点之间都存在相应连接。在简单图的邻接矩阵约定下，每一对不同顶点均相邻，故为完全图。
易错点
矩阵是否对称才能进一步判断有向或无向；题干只给出对角线和非对角线取值，不能据此断言图的方向性。矩阵元素为 1 也不排斥“无权表示”，所以“不是带权图”不是必然结论。