SPM 数学：如何掌握网络（图论）

网络由顶点（点）和边（连接）构成，每个顶点都有一个度，与它相连的边的数目。有向边和带权边则加入方向和一个数值，如距离或成本。

由于这一章较新，考官依赖定义，因此要精确掌握“顶点”“边”“度”“有向”和“带权”。

许多题目会给出一个表格或描述，要你画出网络，或反过来。所有度之和等于边数的两倍，这是检查你的图是否正确的快捷方法。

作答前把凌乱的图重画整洁，因为不清楚的图会失掉你其实已经拿到的分。

如果每一对顶点之间都存在某条路径（不管多长），这个网络就是连通的；如果至少有一个顶点自成一块，没有任何边把它和其余部分连接起来，这个网络就是不连通的。有些题目会要求你判断给定的网络是否连通，并说明理由，做法其实就是从某个顶点开始往外追踪，检查是否最终能到达其余每一个顶点。

如果有某个顶点用这种方法始终到不了，指出那个顶点就足以证明这个网络“不连通”。

SPM的题目经常以邻接表的形式给出网络，而不是画好的图，列出哪些顶点相连，并要求你据此画出网络图，或者反过来从图整理出表格。最稳妥的方法是先把顶点放好，在纸上分散排列，然后严格按照表格逐条添加连接，画一行就在表格上打勾标记。

试图把整张表记在脑子里边画边对，很容易漏画或重复画某条边；按行逐一处理就不会。

除了描述一个网络之外，这一章还要求你在其中找出特定的路径，比如恰好经过每条边一次的路径，或者两个特定顶点之间的路线，并说明这样的路径为什么存在或不存在。这又和顶点度数联系在一起：如果一个网络中度数为奇数的顶点超过两个，就不可能存在从一点出发、到另一点结束、恰好经过每条边一次的路径，能快速识别这个规律，往往就是题目真正在考的捷径。