图论碎碎念（2.1）

本文作者：云屿

Hello,大家好，又到了图论碎碎念时间~~祝各位狗子端午安康~~书接上回，图论基础概念呢，这里也用一个例子来讲：好比说老张端午节在外卖上点了个粽子。

没错

二狗是个灵魂画手

整个事儿就可以用两个点一条线来表示。又由于是老李给老王送，所以这是一个有向图(由老李指向老张)。那么问题来了，突然有一天老张的邻居隔壁老王也想点个粽子。

快递员老李和隔壁老王

老李

老王

那老李就需要给两个人送粽子，他应该先给老王送呢，还是先给老张送呢？这就涉及后面网络规划的一些内容。网络规划在一些项目中已经有了实际应用。比如在大挑（全国大学生挑战赛）和双创（创新创业大赛）中的项目，已经做出实体了：一个外卖的头盔，可以自动接单，在外卖员送餐的路上规划好路线，然后再经过一些类似VR眼镜、语音播报之类酷炫的黑科技加成，让快递员在更短的时间内走更少的路，送更多的单。

不过俗话说杀鸡焉用牛刀。这样一个头盔肯定成本不菲，想要投入生产还有一定距离，而且这没必要：某东现在无人快递已经实现了，过几年都全面推广无人配送、无人驾驶了，快递小哥们还不知道给自己着点急？此时这个粽子问题就华丽丽的升华成了无人车（无人机航线）配送路径优化问题，当然，老张点粽子问题还可以升华为：单/多车，配重，TSP问题，有类似选题的狗子们可以考虑一下使用图论方法求解。

言归正传，像这种生活中的实际问题都可以用一个图来表示。那图呢，又可以用矩阵来表示，比如说老李给老张送和老李给老张和老王两个人一起送，每一种送货方式都可以用一个矩阵来表示。仔细的想【敲黑板！！！】因为外卖是大家都点过都经历过的事，那比照图论的基本概念可以这样看：几个对象？两个对象。所以几个点？两个点。有几种关系？很明显的关系是两个人之间谁给谁送，没有什么其他关系。（前提假设为此图中的边只表示一种关系）再加上老王，两种送粽子路线图就可以这么画：

并不是所有图中都只能有一种关系，比如在进度网络计划图中就存在虚箭线和实箭线两种不同的箭头，也就代表着两种不同的关系。

实箭线表示逻辑上B 工序在A工序之后进行，但是同时，B工序只有当C工序结束之后才能开始。但通常我们所指的图只含有一种关系。表示图的矩阵根据国际惯例又可以分为三种：

a)邻接矩阵

b)关联矩阵

c)边权矩阵

邻接矩阵（此后图片建议横屏食用）

同样关系，换成关联矩阵表示如下图：

这里思考：关联矩阵与其余两个矩阵不同之处在于？进一步，假设老李距离老张18单位，老张距离老王3单位，老李距离老王16单位，则得到边权矩阵的思路如下：

那当我们要比较两个图在逻辑上是否完全一样又该怎么做？欲知后事如何，请听下回分解。新学会的狗子们在留言区留下你们的Points Taken Home 吧~！