当前位置：首页 - 正文

图论算法中的“桥”是什么意思？

发布网友发布时间：2022-04-21 23:45

共4个回答

热心网友时间：2023-07-05 05:56

简单的说，图论中的桥是集合E的元素，称为边（或线）。

图G=（V,E）是一个二元组（V,E）使得E⊆[V]的平方，所以E的元素是V的2-元子集。为了避免符号上的混淆，默认V∩B=Ø。集合V中的元素称为图G的定点（或节点、点），而集合E的元素称为边（或线）。通常，描绘一个图的方法是把定点画成一个小圆圈，如果相应的顶点之间有一条边，就用一条线连接这两个小圆圈，如何绘制这些小圆圈和连线时无关紧要的，重要的是要正确体现哪些顶点对之间有边，哪些顶点对之间没有边。

图论本身是应用数学的一部份，因此，历史上图论曾经被好多位数学家各自独立地建立过。关于图论的文字记载最早出现在欧拉1736年的论著中，当时考虑的原始问题有很强的实际背景---遍历"桥"问题！在解答问题的同时，开创了数学的一个新的分支——图论与几何拓扑。

哥尼斯堡（今俄罗斯加里宁格勒）是东普鲁士的首都，普莱格尔河横贯其中。十八世纪在这条河上建有七座桥，将河中间的两个岛和河岸联结起来。人们闲暇时经常在这上边散步，一天有人提出：能不能每座桥都只走一遍，最后又回到原来的位置。这个问题看起来很简单有很有趣的问题吸引了大家，很多人在尝试各种各样的走法，但谁也没有做到。看来要得到一个明确、理想的答案还不那么容易。

1736年，有人带着这个问题找到了当时的大数学家欧拉，欧拉经过一番思考，很快就用一种独特的方法给出了解答。欧拉把这个问题首先简化，他把两座小岛和河的两岸分别看作四个点，而把七座桥看作这四个点之间的连线。那么这个问题就简化成，能不能用一笔就把这个图形画出来。经过进一步的分析，欧拉得出结论－－不可能每座桥都走一遍，最后回到原来的位置。并且给出了所有能够一笔画出来的图形所应具有的条件。这是拓扑学的“先声”。

在拓扑学的发展历史中，还有一个著名而且重要的关于多面体的定理也和欧拉有关。这个定理内容是：如果一个凸多面体的顶点数是v、棱数是e、面数是f，那么它们总有这样的关系：f+v-e=2。

热心网友时间：2023-07-05 05:56

桥是指一条边e属于E（G），使得G-e的连通片增加

连通片就是连通图，图连通的充要条件就是连通片个数为1

热心网友时间：2023-07-05 05:56

图论的桥是在解决平面图的平面嵌入时引入的一个概念。设H是图G的一个子图，在E（G）-E（H）上定义关系“~”如下：e1~e2当且仅当存在一条途径W使得：（1）W的第一条边和最后一条边是e1和e2；（2）W与H是内部不相交的。则G-E（H）的子图称为H中的桥！

热心网友时间：2023-07-05 05:57

图论〔Graph Theory〕是数学的一个分支。它以图为研究对象。图论中的图是由若
　　干给定的点及连接两点的线所构成的图形，这种图形通常用来描述某些事物之间的
　　某种特定关系，用点代表事物，用连接两点的线表示相应两个事物间具有这种关系
　　。
　　图论本身是应用数学的一部份，因此，历史上图论曾经被好多位数学家各自独立地
　　建立过。关于图论的文字记载最早出现在欧拉1736年的论着中，他所考虑的原始问
　　题有很强的实际背景。
　　图论起源于著名的柯尼斯堡七桥问题。在柯尼斯堡的普莱格尔河上有七座桥将河中
　　的岛及岛与河岸联结起来，如下图所示，A、B、C，D表示陆地。
　　问题是要从这四块陆地中任何一块开始，通过每一座桥正好一次，再回到起点。然
　　而无数次的尝试都没有成功。欧拉在1736年解决了这个问题，他用抽象分析法将这
　　个问题化为第一个图论问题：即把每一块陆地用一个点来代替，将每一座桥用联接
　　相应的两个点的一条线来代替，从而相当于得到一个「图」（如下图）。欧拉证明
　　了这个问题没有解，并且推广了这个问题，给出了对於一个给定的图可以某种方式
　　走遍的判定法则。这项工作使欧拉成为图论〔及拓扑学〕的创始人。
　　1859年，英国数学家哈密顿发明了一种游戏：用一个规则的实心十二面体，它的
　　20个顶点标出世界著名的20个城市，要求游戏者找一条沿着各边通过每个顶点刚好
　　一次的闭回路，即「绕行世界」。用图论的语言来说，游戏的目的是在十二面体的
　　图中找出一个生成圈。这个问题后来就叫做哈密顿问题。由於运筹学、计算机科学
　　和编码理论中的很多问题都可以化为哈密顿问题，从而引起广泛的注意和研究。
　　在图论的历史中，还有一个最著名的问题——四色猜想。这个猜想说，在一个平面
　　或球面上的任何地图能够只用四种颜色来着色，使得没有两个相邻的国家有相同的
　　颜色。每个国家必须由一个单连通域构成，而两个国家相邻是指它们有一段公共的
　　边界，而不仅仅只有一个公共点。四色猜想有一段有趣的历史。每个地图可以导出
　　一个图，其中国家都是点，当相应的两个国家相邻时这两个点用一条线来连接。所
　　以四色猜想是图论中的一个问题。它对图的着色理论、平面图理论、代数拓扑图论
　　等分支的发展起到推动作用。

声明：本网页内容为用户发布，旨在传播知识，不代表本网认同其观点，若有侵权等问题请及时与本网联系，我们将在第一时间删除处理。
E-MAIL:11247931@qq.com

焦点

图论算法中的“桥”是什么意思？

最新推荐

猜你喜欢

热门推荐