飞码网-免费源码博客分享网站

点击这里给我发消息

图论在计算机领域的应用

飞码网-免费源码博客分享网站 爱上飞码网—https://www.codefrees.com— 飞码网-matlab-python-C++ 爱上飞码网—https://www.codefrees.com— 飞码网-免费源码博客分享网站
图形是表示地方之间联系的一种方式。在数学上,图是节点和边的集合。节点是由图的边连接在一起的位置。例如,如果你有两个小镇由一条双向公路连接,你可以将其表示为一个有两个节点的图,每个节点代表一个小镇,一条边,即公路,将两个小镇连接在一起。除了边缘是双向连接的非定向图外,还有定向图,其中的边缘只连接单向。例如,你可以把前面的例子中由一条路连接的两个城市表示为一个由两个节点和两条边组成的定向图,每条边连接其中一个节点和另一个节点。在城市的例子中,记录两个城市之间的距离可能也很方便;这可以通过给一条边增加一个 "权重 "来表示,这个 "权重 "是一个数字,通常对应于一条边所覆盖的距离(两个节点之间的距离)。

为什么图是有用的?


计算机科学家已经发展了大量关于图和对图的操作的理论。其中一个原因是,图可以用来表示计算机科学中许多原本抽象的问题。找到一种方法将问题的解决方法表示为图形,可以提出解决问题的新方法,甚至可以直接得出由图形理论衍生出来的解决方案。在讨论算法效率和试图证明某个算法是NP-Complete时,经常会用到这种技术;因为很多涉及图的问题,比如寻找穿越所有节点的最短路径(旅行推销员问题),都是NP-Complete,如果你能找到一种方法将一个问题表示为图,并表明它与其他NP-Complete问题之一类似,那么你就可以表明你要解决的问题也是NP-Complete,这就给了你一个提示,即解决这个问题需要花费大量的时间。

使用图形的另一个原因是,计算机用来解决的许多问题都涉及到表示对象、地点或概念之间的关系。因为图形可以是有方向的,也可以是无方向的,所以它们是一种灵活的显示联系的方法。例如,你可以把一个房间里的谁认识谁描述为一个节点的集合,每个节点代表一个人,而定向边则代表一个人认识另一个人。

由于图经常被使用,而且它们可以表示计算机科学中的许多问题,如旅行推销员问题或像房间里的人与人之间的关系这样简单的东西,它们是一种方便的表达问题的方法,许多人都很熟悉。这种熟悉感简化了建立问题心理模型的过程,最终导致问题的更好解决。

有哪些重要的图论术语?


有向图。有向图是指边缘只在一个方向上连接节点的图。

非定向图。非定向图是一个边缘双向(在两个方向)连接节点的图。节点。节点:节点通常画成一个圆圈,代表一个项目,可以与其他项目或节点相关联。节点有时也被称为顶点。

边缘:边缘代表节点之间的连接。根据图的类型,边可以是定向的,也可以是不定向的。边缘也可以有权重,权重可能对应于边缘之间的关系强度或距离。例如,如果一个图表示一张地图,那么每个边的权重将表示两个节点之间的距离。

连接。如果从任何一个节点可以到达任何其他节点,那么这个图就是连接的。

断开:如果从任何一个节点可以到达任何其他节点,那么这个图就是断开的。如果某些节点组形成了一个岛,与图的其他部分没有联系,那么这个图就是断开的。
飞码网-免费源码博客分享网站 爱上飞码网—https://www.codefrees.com— 飞码网-matlab-python-C++ 爱上飞码网—https://www.codefrees.com— 飞码网-免费源码博客分享网站
赞 ()
内容页底部广告位3
留言与评论(共有 0 条评论)
   
验证码: