🏷️ 知识点：顶点度
一个无向图有 23 条边，度为 4 的顶点有 5 个，度为 3 的顶点有 4 个，其余顶点的度均为 2，则该图有（ ）个顶点。
A. 11 B. 12 C. 15 D. 16
[tag_link]
正确答案：D
结论
该图有 16 个顶点。
推导
由握手定理，所有顶点度数之和为 2×23=46。度为 4 和 3 的顶点贡献 5×4+4×3=32，剩余顶点贡献 46−32=14。其余顶点度为 2，所以有 14÷2=7 个；总顶点数为 5+4+7=16。
易错点
边数不是度数和；无向图每条边连接两个端点，必须先用 2|E| 求度数总和，再除以其余顶点的度。
对邻接表的叙述中，（ ）是正确的。
A. 无向图的邻接表中，第 i 个顶点的度为第 i 个链表中结点数的两倍 B. 邻接表比邻接矩阵的操作更简便 C. 邻接矩阵比邻接表的操作更简便 D. 求有向图顶点的度，必须遍历整个邻接表
[tag_link]
正确答案：D
结论
选 D。
推导
无向图邻接表中每条边在两个链表各出现一次，所以第 i 个链表的结点数就是顶点 i 的度，不需要再乘 2。有向图顶点的出度可扫描自身链表，但入度要检查所有边表；求总度时必须遍历整个邻接表。
易错点
邻接表与邻接矩阵没有“所有操作都更简便”的绝对关系，应按操作类型和图的稠密程度选择。
对 n 个顶点的无向图和有向图，分别采用邻接矩阵和邻接表表示时，试问：
- 如何判别图中有多少条边？
- 如何判别任意两个顶点 i 和 j 是否有边相连？
- 任意一个顶点的度是多少？
[tag_link]
参考答案
1. 边数
- 邻接矩阵：无向图的非零（无权图即为 1）元素数为 2e，边数为非零元素数除以 2；有向图的非零元素数就是弧数 e。
- 邻接表：无向图每条边有两个边表结点，边数为边表结点总数除以 2；有向图的边表结点总数就是弧数。
2. 判断相邻
邻接矩阵中，无向图检查 A[i][j]（等价地检查 A[j][i]），有向图检查 A[i][j] 是否表示弧 i→j。邻接表中，扫描顶点 i 的边链表查找 j；无向图还可从 j 的链表查找 i。
3. 顶点度
邻接矩阵中，无向图顶点 i 的度是第 i 行（或列）的非零元素数；有向图第 i 行非零元素数为出度，第 i 列非零元素数为入度，度为二者之和。邻接表中，无向图顶点 i 的度是其边链表长度；有向图该链表长度为出度，入度需统计所有边表中指向 i 的结点，度为入度与出度之和。
易错点
无向图邻接表的边存储两次，而有向图每条弧只存储一次；有向图邻接表的链表长度只是出度，不能直接当作总度。