图表和应用

图算法可以解决现实世界中的许多问题。图纸对建模和解决实际问题非常有用。例如，在两个城市之间找到最小航班数量的问题可以通过图纸进行建模，其中顶部代表城市，同时代表两个相邻城市之间的航班，如下图所示。最小转运航班数量 两个城市之间的问题简化为图中两个顶点之间的最短路径。

图形问题的研究被称为图论。图论由 Leonhard Euler 于 1736 年成立时，他引入了图术语来解决这个名字七桥柯尼斯堡问题。普雷格尔河将普鲁士柯尼斯堡市(现俄罗斯加里宁格勒)分开。河上有两个岛屿。城市和岛屿由七座桥梁连接，如下图所示（a）所示。问题是，一个人可以步行，每座桥只有一次，然后回到起点吗？欧拉证明这是不可能的。

为了建立证据，欧拉首先通过消除所有街道来抽象柯尼斯堡城市地图，如上图所示（a）所示草图。接下来，他用一个点(称为顶点或节点）用一条线代替每个陆地块(称为边）如上图所示，更换每座桥（b）所示。这种具有顶点和边缘的结构被称为图。

看看图片，我们问是否有一条路径从任何顶点开始，只是通过所有的边缘，并返回到起始顶点。欧拉证明，每个顶点必须有偶数的边缘才能有这样的路径。因此，柯尼斯堡七座桥的问题并没有得到解决。

算法通常用于解决图形问题。计算机科学、数学、生物学、工程、经济学、遗传学和社会科学等各个领域都有许多应用。

基本图术语

图表由顶点和连接顶点的边缘组成。本章不假设您有任何图论或离散数学的先验知识。我们用简单明了的术语来定义图表。

图表是什么？图表是一种数学结构，表示现实世界中实体之间的关系。例如，上图代表城市之间的航班，下图(b)它代表了陆地之间的桥梁。

图片由一组非空顶点(也称节点或点)和一组连接顶点的边缘组成。为了方便起见，我们将图片定义为 G = (V, E)，其中 V 表示一组顶点，E 表示一组边缘。例如，下图中的V和E如下：

V = {西雅图，旧金山，洛杉矶， “丹佛”、“堪萨斯城”、“芝加哥”、“波士顿”、“纽约”， “亚特兰大”、“迈阿密”、“达拉斯”、“休斯顿”}；

E = {"西雅图"， “旧金山”}，{西雅图”， "芝加哥" {西雅图，丹佛，旧金山，丹佛， ... };

图片可以是向的，也可以是无向的。在有向图在中间，每个侧面都有一个方向，这表明你可以通过这个侧面从一个顶点移动到另一个顶点。您可以使用方向图来建模父子关系，其中从顶点开始 A 到 B 的边表示 A 是 B 父项。下图 (a) 有向图显示。

在无向图中，你可以在顶点之间双向移动。下图为无向图。

边缘可以是加权的，也可以是未加权的。例如，为了表示两个城市之间的飞行时间，您可以在上图中的每个边缘分配一个权重。

如果图中的两个顶点由同一边连接，则称为它们相邻。类似地，如果两边连接到相同的顶点，则称为它们相邻。图中连接两个顶点的边缘称为两个顶点重合。顶点的度与之相关的边数。

如果两个顶点相邻，则称为邻居。同样，如果两边相邻，则称为邻居。

循环将顶点链接到自己的边缘。如果两个顶点通过两个或两个以上的条边连接，这些边称为平行边。 简单图没有环或平行边的图。在完全图在中间，每两对顶点相连，如下图所示(b)所示。

如果图中任何两个顶点之间有路径，则图为连通的。图 G 的子图 是一张图，它的顶点集是 G 子集，边集是 G 子集。例如，上图 (c) 图中的图是图中的子图(b).

假设图是连接和无向的。 循环 它是一条从一个顶点开始，在同一个顶点结束的闭合路径。如果连接图没有环，那么它就是一棵树树。图 G 的生成树 是 G 连通子图，该子图包含 G 所有顶点的树。

以上就是图表和应用的详细内容，更多请关注图灵教育的其他相关文章！