图表和应用

许多现实世界的问题可以使用图算法来解决。图对于建模和解决现实问题很有用。例如，找到两个城市之间的最少航班数量的问题可以使用图来建模，其中顶点代表城市，边代表两个相邻城市之间的航班，如下图所示。求最小联程航班数的问题
两个城市之间的问题简化为寻找图中两个顶点之间的最短路径。

图问题的研究被称为图论。图论由 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 中所有顶点的树。

以上是图表和应用的详细内容。更多信息请关注PHP中文网其他相关文章！