图算法可以解决现实世界中的许多问题。图纸对建模和解决实际问题非常有用。例如,在两个城市之间找到最小航班数量的问题可以通过图纸进行建模,其中顶部代表城市,同时代表两个相邻城市之间的航班,如下图所示。最小转运航班数量 两个城市之间的问题简化为图中两个顶点之间的最短路径。
图形问题的研究被称为图论。图论由 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 所有顶点的树。
以上就是图表和应用的详细内容,更多请关注图灵教育的其他相关文章!