数学 · 图论中的网络

有向图、加权图和简单图

三种图的名称听起来相似，边上的数字又容易和度混淆。

三个检查就能给网络分类：有没有箭头，边上有没有数字，有没有环或重复的边。每个检查是独立的，所以一个图可以同时属于不止一种。

三个检查是什么？

没有环也没有重复边的图，通过了简单图的检验。同一个图也可以同时是有向的或加权的。

情境1。 四个市镇用道路相连，每条路两个方向都可以行驶。没有道路绕回自己，任何一对市镇之间也没有两条路。这个图是简单图，而且是无向的。

情境2。 同样的市镇，但道路标上了12 km、8 km、15 km和6 km。这个图是加权图，而且仍是简单图。

情境3。 学校食堂的排队系统：从柜台到餐桌只有单向的箭头，而且柜台到2号桌有两条箭头，代表两条不同的路线。这个图是有向图，也不是简单图，因为有一对顶点之间有两条边。

常见的失误，是把边上的数字当成顶点的度，或者反过来。权重写在边的旁边，度是在顶点上数出来的。

题目问“A的度”，就数A上的边，不要把权重加起来。

一个网络有顶点P、Q和R。边：P到Q，权重5；Q到R，权重3；R上有一个环，权重2。所有的边都是双向的。请给它分类。

Answer

箭头：没有，所以这个图是无向的。

数字：三条边都有权重，所以这个图是加权的。

环：R上有一个环，所以这个图不是简单图。

如果想让老师在新的网络上测试你的分类，可以了解线上一对一数学补习。

简单图没有环，也就是没有从顶点连回自己的边，而且同一对顶点之间没有两条边。每条边都只连接两个不同的顶点一次。

有向图的边上有箭头。每条边只走一个方向，就像单行道。没有箭头的边，两个方向都可以走。

加权图的每条边上有一个数，例如路程、费用或时间。这个数叫权重，说明的是边，不是顶点。

可以。一个道路全是单行、边上写了路程的网络，既是有向图，也是加权图。每一项特征要分开检查。

如果你分不清边上的数字和顶点的度，一对一数学课可以让老师在新的网络上测试你的分类，并指出是哪一步想错了。