图论中的网络：练习题

图论中的网络 的原创练习题，仿 数学试卷一（客观题） 与 数学试卷二（主观题） 的风格。每题都有解答，方便你检查方法而不只是结果。

一个图有 8 条边。所有顶点的度数总和是多少？

一个图的顶点度数分别为 3、3、2、2 和 2。这个图有多少条边？

在任何图中，奇数度顶点的个数必定是偶数。下列哪一个不可能是某个图中奇数度顶点的个数？

一个有向网络有 10 条有向边。所有顶点的入度总和是多少？

顶点上的一个环为该顶点的度数贡献多少？

一个加权网络连接城镇 P、Q、R 和 S，道路长度如下：P–Q = 5 km，P–R = 3 km，R–Q = 1 km，Q–S = 4 km，R–S = 6 km。从 P 到 S 的最短路径长度是多少？

在一个有 5 个顶点的完全图中，每个顶点都恰好用一条边与其他每个顶点相连。它有多少条边？

树是没有回路的连通图。一棵有 7 个顶点的树有多少条边？

在图中，度数为 0 的顶点叫什么？

下列哪个术语描述的是每条边都被赋予数值（如距离、时间或成本）的图？

网络图 G 有六个顶点 A、B、C、D、E 和 F，度数为 A = 4、B = 3、C = 3、D = 2、E = 2、F = 2。(a) 求所有顶点的度数总和。

(b) 据此求 G 的边数。(c) 说明并给出理由：这样的图能否画出。

一个加权网络显示五个城镇 P、Q、R、S 和 T 之间的道路，距离以 km 为单位：P–Q = 8，P–R = 5，Q–R = 3，Q–S = 6，R–T = 7，S–T = 4。(a) 列出从 P 到 T 的所有可能路径及其总长度。

(b) 据此确定从 P 到 T 的最短路径并说明其长度。

一个有向网络模拟四个路口 A、B、C 和 D 之间的单行道。有向边为 A→B、A→C、B→C、C→D、D→A 和 D→B。

(a) 写出每个路口的出度。(b) 写出每个路口的入度。

(c) 证明出度总和等于入度总和，并说明这个总和代表什么。

在一场国际象棋比赛中，7 名棋手各自与其他每位棋手恰好比赛一局。用一个图来建模，其中顶点是棋手，每条边是一局比赛。

(a) 说出每个顶点的度数并给出理由。(b) 求所有顶点的度数总和。

(c) 据此求比赛的总局数。