图论练习卷（附答案）

一个森林（无圈图）有 16 个顶点和 5 个连通分量。它有多少条边 |E|？

求所示图 Σ deg 中所有顶点的度数之和。

这个连通图有欧拉回路、有不是回路的欧拉通路，还是两者都没有？点选你的答案。

1. 1欧拉回路
2. 2有欧拉通路，无回路
3. 3都不是

一个连通图有 7 个顶点和 10 条边。必须去掉多少条边 k 才能剩下一棵生成树？

用迪杰斯特拉算法求带权图中从 A 到 F 的最短路径的长度 d(F)。

从 D 到 E 的长度为 3 的途径有多少条？途径可以重复顶点和边。把这个数记作 N。