图论中的网络

网络（图）是一组称为顶点的点，由称为边的线连接。本章教你读画网络、数度数、求边上权重之和，并用它们来模拟路线与连接等实际情形。

预期会根据表格或描述画出或补全网络、数度数，有时还要沿一条路线累加权重。图画整洁很重要，挤成一团的草图会数错。

只要图清晰，试卷二的题目通常结构良好、方法分给得慷慨。

每条边都连着两端，所以每条边恰好给它的两个顶点各加 1，共加 2。把所有顶点的度数相加，必然得到边数的两倍：Σ（度数） = 2 × （边数）。

这一下给了两样东西。已知边数时，它是求缺失度数的快捷方法；它又是自检：所有度数之和永远是偶数，所以如果你的度数加起来是奇数，那就在某处数错了。

一个环给它自己的顶点算 2；若有多条边连着同一对顶点，每条各自单独计算。

子图就是网络的一部分：保留原图的一些顶点和一些边，不新增任何东西。树是一种特殊的连通网络，没有回路，你无法从某个顶点出发、沿着边走而不重复，再回到起点。

树有一条值得记的整齐规则：有 n 个顶点的树恰好有 n − 1 条边。所以连接 6 个城镇的树恰好用 5 条路。

如果一个有 n 个顶点的网络有 n − 1 条边且连成一片，它就是树；再加一条边就会产生回路。

在有向网络里，每条边是单向箭头，所以一个顶点有两个独立的计数：出度（离开它的箭头）和入度（进入它的箭头）。路线必须顺着箭头方向走，不能逆着箭头前进。

在加权网络里，每条边还带一个数：以 km 为单位的距离、以 RM 为单位的成本，或以分钟为单位的时间。要求一条路线的总和，就按顺序列出你实际用到的边，只把它们的权重相加，顶点本身没有数值。

看清箭头、只加所选路径上的边，能避免这个课题里大部分丢分。

这个例子先用度数之和的规则求缺失度数，再把路线上的权重加起来，这是第二试卷常一起考的两项技能。