图论最终是关系的研究。给定一组节点和连接，可以抽象化从城市布局到计算机数据的所有内容，图论提供了一个有用的工具，可以量化和简化动态系统的许多移动部分。通过框架研究图形可为许多布置、网络、优化、匹配和操作问题提供答案。
Internet的初步地图
图形理论对您来说听起来像是一个令人生畏的抽象话题，那么为什么您甚至应该花时间阅读有关它的文章？但是，尽管听起来可能不太适用，但是实际上图论有很多有用而重要的应用！在本文中，我将尝试简要解释其中的一些应用程序。为此，我将尽力说服您，至少具有该主题的一些基本知识对于解决您可能遇到的一些有趣问题很有用。
本文将通过一个具体示例展示如何使用图论来制定和解决路线规划/优化任务。更具体地说，我将考虑一个大型仓库，该仓库由位于不同位置/提货点的数千种不同物品组成。这里的挑战是，给定一个物品清单，您应该沿着哪个路径穿过仓库来拾取所有物品，但同时要使总行驶距离最小化？对于那些熟悉这类问题的人来说，这与著名的旅行售货员问题非常相似。
本文的目的不是全面介绍图论，这将是一项艰巨的任务。而是通过一个真实的例子，说服您，至少了解图论的一些基础知识会证明是非常有用的！
将首先对图论领域进行简要的历史介绍，然后重点介绍在许多截然不同的领域中的重要性和广泛的有用应用。在进行了更一般的介绍之后，我将把重点转移到上面讨论的仓库优化示例。
图论的历史
图的基本概念是由瑞士数学家莱昂哈德·欧拉（Leonhard Euler）于18世纪首次提出的，莱昂哈德·欧拉（Leonhard Euler）是18世纪最杰出的数学家之一。他关于著名的“柯尼斯堡七桥问题”的著作通常被认为是图论的起源。
普鲁士的克尼格斯堡市（现为俄罗斯加里宁格勒）坐落在普雷格尔河的两侧，包括两个大岛，克奈普霍夫和隆塞，它们相互连接，或者与城市的两个大陆部分相连，七个桥（如下左图所示）。问题是要设计一条穿过城市的步行路线，一次只能穿过一次这些桥梁。
欧拉认识到相关的约束条件是四块土地和七个桥梁，因此绘制了第一个已知的现代图形视觉表示。一个现代的曲线图，如在右下方图像，是由一组点，被称为表示v ertices或节点，由一组被称为边缘线的连接。
来自维基百科
从涉及城市和桥梁等具体问题的抽象到图形，使该问题在数学上易于处理，因为这种抽象表示仅包含解决问题的重要信息。欧拉实际上证明了这个特定问题没有解决方案。但是，他面临的困难是合适的分析技术的发展，以及随后的测试，这些测试以数学上的严格性确立了这一主张。从那里开始，几十年来一直处于休眠状态的称为图论的数学分支，应用终于暴发了。
图论概论
如前所述，我并不打算对图论进行全面介绍。以下部分仍包含有关不同种类的图等的一些基础知识，这与我们稍后将讨论路径优化的示例相关。
图论最终是关系的研究。给定一组节点和连接，可以抽象化从城市布局到计算机数据的所有内容，图论提供了一个有用的工具，可以量化和简化动态系统的许多移动部分。通过框架研究图形可为许多布置，网络，优化，匹配和操作问题提供答案。
图形可用于对物理，生物，社会和信息系统中的许多类型的关系和过程进行建模，并且具有广泛的有用应用，例如
1. 在社交媒体等网络中查找社区（推荐朋友/联系方式），或者在最近几天内通过联系在社区中传播COVID19。
2. 在搜索引擎中对超链接进行排名/排序。
3. GPS / Google地图查找最短路径。
4. 研究化学中的分子和原子。
5. DNA测序
6. 计算机网络安全
7. ….. 还有很多…。
具有6个节点的图的简单示例
稍微复杂一些的社交媒体网络
如前所述，有几种类型的图描述了不同类型的问题（以及其中的约束）。（的上一篇文章中也可以找到各种图形的很好的下面的部分代表了该文章的子集。
图的类型
有不同类型的图形表示形式，当以编程方式解决包括图形的问题时，我们必须确保我们了解所使用的图形的种类。
- 无向图
顾名思义，节点之间不会有任何指定的方向。因此，从节点A到B 的边缘将与从B到A的边缘相同。
在上图中，每个节点可以代表不同的城市，并且边缘显示双向道路。
- 有向图（DiGraphs）
与无向图不同，有向图在不同节点之间具有方向或方向。这意味着，如果从节点A到B有一条边，则只能从A移到B。
像前面的示例一样，如果我们将节点视为城市，则我们有一个从城市1到2的方向。这意味着，您可以从城市1到2行驶，但不能返回城市1，因为没有从该方向返回城市1的方向。 2.但是，如果我们仔细检查图表，我们会看到双向的城市。例如，城市3和4向两侧都有方向。
- 加权图
许多图形的边缘可能包含权重，以表示真实世界的含义，例如成本，距离，数量等。
可以是有向图或无向图。在此示例中，我们得到的是无向加权图。从绿色节点到橙色节点（反之亦然）的成本（或距离）为3。像我们前面的示例一样，如果要在两个城市之间旅行，例如绿色和橙色，我们必须行驶3英里。这些指标是自定义的，可以根据情况进行更改。对于更详细的示例，请考虑您必须从绿色到粉红色的城市。如果查看城市图，我们在两个城市之间找不到任何直接的道路或边缘。因此，我们可以做的是穿越另一个城市。最有希望的路线将是从绿色到粉红色，再到橙色和蓝色。如果权重是城市之间的成本，我们将不得不花费11美元通过蓝色旅行到达粉红色，但是如果我们选择另一条路线通过橙色，
每个边缘可能有多个权重，包括距离，行驶时间或金钱成本。这样的加权图通常用于对GPS和旅行计划搜索引擎进行编程，以比较飞行时间和费用。
图论→路径优化
仓库拣选货物最短路径问题
挑战：
这里的挑战是，在输入"拣选清单"的情况下，我们应该找到经过所有拣选点的最短路线，但还要遵守关于可能/允许行驶的地点的限制。这里的假设和约束条件是，仅允许在标记的"转折点"处穿越仓库的走廊。另外，每个走廊的行驶方向必须遵循指定的合法行驶方向。
解：
这个问题可以用图论的形式表达为优化问题。仓库中的所有取货点都在图中形成一个"节点"，其边缘表示允许的车道/走廊以及节点之间的距离。为了更正式地介绍这个问题，让我们从一个简化的例子开始。
下图表示2条走廊，每个走廊有5个搁板/拾取点。在此，所有架子都表示为图中的节点，地址范围为1-10。箭头指示允许的行驶方向，双箭头指示您可以两种方式行驶。很简单，对不对？
能够以图表的形式表示允许的行驶路线，这意味着我们可以使用图表理论中已知的数学技术来找到节点（即，我们仓库中的货架）之间的最佳"行驶路线"。
上面的示例图可以通过邻接矩阵进行数学描述。因此，下图右侧的邻接矩阵是我们"仓库图"的表示，它表示各个节点之间所有允许的行驶路线。
- 示例1：允许您从节点2→3出发，但不允许从3→2出发。这由右侧邻接矩阵中的" 1"指示。
- 示例2：允许您从节点8→3和节点3→8出发，再次由邻接矩阵中的" 1"表示（在这种情况下，它在行进方向上是对称的）。
回到我们的仓库问题：
实际的仓库当然比上面的示例更大，更复杂。但是，如何通过图形表示问题的主要原理保持不变。为了使实际问题更简单（并且更直观地适合本文），我减少了拾取点的总数（大约每50个架子中有一个，在下图中用黑色正方形标记）。将为所有拾取点分配一个1到74之间的地址（"节点号"）。图中还标出了前面提到的其他相关约束，例如每个走廊中允许的行驶方向以及走廊之间的允许"转弯点"和捷径。
简化仓库的图形表示
然后，下一步就是以邻接矩阵的形式表示该图。由于我们对寻找最佳路线和总距离感兴趣，因此我们还必须在矩阵中包括各个节点之间的行驶距离。
"仓库图"的邻接矩阵
该矩阵指示了关于允许的行进方向（允许使用"快捷方式"），所有其他限制以及节点之间的行驶距离（通过颜色显示）的所有限制。作为示例，在图形表示中所示的节点21和41之间的"快捷方式"也可以在邻接矩阵中清楚地识别。矩阵的"白色区域"表示不允许的路径，通过这些节点之间的"无限"距离来表示。
从图形表示到路径优化
仅仅以图表的形式对我们的仓库进行抽象表示，当然并不能解决我们的实际问题。想法是通过这种图形表示，我们现在可以使用图形理论中的数学框架和算法来解决它！
由于图优化是数学领域中众所周知的领域，因此有几种方法和算法可以解决此类问题。在此示例案例中，我基于" " 解决方案，这是一种用于在找到众所周知的。算法的一次执行将找到所有节点对之间最短路径的长度（总权重）。尽管它不返回路径本身的详细信息，但可以通过对算法的简单修改来重建路径。
如果将此算法作为输入输入"领料单列表"，然后在其中浏览要领取的物品列表，则应该能够获得最佳路线，从而使总行驶距离最小化以收集列表中的所有物品。
示例：让我们首先以可视化方式显示（简短的）拣货清单，如下所示：从节点«0»开始，在位置/节点15、45、58和73处拾取物品（这些位置如下图所示） ）。该算法通过计算"距离矩阵" D找到这些点之间的最短允许路线，然后将其用于确定领料单中所有位置/节点之间的总行驶距离。
· 步骤1：D [0] [15]→90 m
· 步骤2：
D [15] [45]→52 m· 步骤3：D [45] [58]→34 m
· 步骤4：D [58] [73]→92 m
总距离= 268m
从拣货清单优化驾驶路线
已经测试了多个"拣选清单"作为输入并验证了建议的行驶路线和计算出的距离，该算法已能够在所有情况下找到最佳路线。该算法遵守所有施加的约束，例如允许的行进方向，并使用所有允许的"快捷方式"来最小化总距离。
从路径优化到有用的见解
如上面的示例所示，我们开发了一种优化算法，该算法可以通过拣货订单列表上的所有点（针对仓库的简化版本）计算出最佳行驶路线。通过提供一列提货单作为输入，因此可以相对轻松地计算出每人平均行驶里程的统计数据。领料单。然后，还可以根据各种信息（例如项目类型，客户，日期等）对这些统计信息进行过滤。在下面的部分中，我将挑选一些示例，说明如何从这种路径优化工具中提取有趣的统计信息。
为此，我首先生成了10.000个拣货订单清单，其中每个清单的物品数量在1至30件之间，位于仓库中的随机取货点（上图中的地址3–74）。通过对所有这些选择列表执行路径优化过程，我们可以提取一些有趣的统计数据。
范例1： 根据每单位数量计算里程。领料单清单。在这里，您自然会假设总里程数增加了您必须选择的项目。但是，在某种程度上，这将开始趋于平缓。这是因为这样一个事实，即最终必须在仓库的所有走廊停下来提取货物，这又使我们无法利用巧妙的"捷径"来最大程度地缩短总行驶距离。这种趋势可以在左下图中说明，该图说明，对于每个拣配订单，大约15-20个单位以上，添加额外的物品并不会使总行驶里程更长（因为您必须开车穿过货车的所有走廊）仓库）。注意，这些图显示了每英里典型行驶里程分布的"密度图"。领料单清单
另一个有趣的统计数字，显示出相同的趋势，是右图中每个被拣选项目的行驶距离分布。在这里，我们看到，对于只包含少量物品的拣货清单，每英里的典型行驶里程。物品相对较高（差异很大，取决于一些物品位于同一走廊等情况下的"幸运"程度）。对于包含多个项目的拣货清单，每英里的里程数。项目正在逐渐减少。因此，为了进一步优化每个拣货订单列表应包含的物品数量，以使每个拣选物品的里程数最小化，这种统计数据可能会更有趣地进行深入研究。
估算每个列表/项目的行驶距离与每个列表的项目数。
示例2：在这里，我使用了真实数据，其中还包含客户ID形式的附加信息（此处仅针对两个客户显示）。然后，我们可以仔细查看每公里里程的分布。挑选两个客户的订单清单。例如，您通常需要开车较长距离来挑选一个客户与另一个客户的商品吗？而且，您是否应该向该客户额外收取这笔额外费用？
左下图分别显示了"客户1"和"客户2"的里程分布。我们可以据此解释的一件事是，对于客户2，大多数拣货订单列表的行驶距离比客户1短得多。这也可以通过计算每人的平均里程来显示。两个客户的拣货订单清单（右图）。
这种类型的信息可以例如用于实施定价模型，其中对客户的产品价格也基于每个订单的里程。对于订单涉及更多驾驶（因此也需要更多时间和更高成本）的客户，您可以考虑比涉及较短驾驶距离的订单开具更多发票。
总结：
图论不仅仅是一个抽象的数学概念，而且它实际上具有许多有用且有趣的应用程序！希望上面的示例对某些人在以后解决类似问题时很有用，或者至少满足您对图论及其某些应用的好奇心。
