2020——2021 第一学期《图论》期末考试
命题人: 金应烈
2020 年 12 月 23 日
一. (15 分) 选择题
1. (3 分) 给定顶点集和边集判断是否为强连通图。
2. (3 分) 利用握手定理求顶点数和边数。
3. (3 分) 完全 m 叉树顶点数、内点、叶子数目关系。
4. (3 分) 给定编码集合,找出哪个不是前缀码。
5. (3 分) 不存在完美匹配的是 (奇圈)。
二. (15 分) 填空题
1. 由三个顶点组成的不同构的无向图有 个,组成的不同构的有向图有 个。
2. 已知平面图有 6 个顶点,每个顶点的度为 4,则此平面图有 面。
3. 对于完全二部图 K
m,n
,γ(K
m,n
) = ,χ
′
(K
m,n
) = 。
三. (46 分) 证明题
1. (8 分) 连通图 G 具有 Euler 路的充分必要条件是 G 中有两个奇点。
2. (8 分) 设平面连通图 G 中没有长为 3 的圈,证明:
(1)
q
为
G
的边数,
p
为
G
的顶点数,
q
≤
2
p
−
4
。
(2) δ(G) ≤ 3。
1
评论0