图论(一)基本概念

小恐龙 等级 552 0 0

图(graph)是数据结构和算法学中最强大的框架之一(或许没有之一)。图几乎可以用来表现所有类型的结构或系统,从交通网络到通信网络,从下棋游戏到最优流程,从任务分配到人际交互网络,图都有广阔的用武之地。

而要进入图论的世界,清晰、准确的基本概念是必须的前提和基础。下面对其最核心和最重要的概念作出说明。关于图论的概念异乎寻常的多,先掌握下面最核心最重要的,足够开展一些工作了,其它的再到实践中不断去理解和熟悉吧。

图(graph)并不是指图形图像(image)或地图(map)。通常来说,我们会把图视为一种由“顶点”组成的抽象网络,网络中的各顶点可以通过“边”实现彼此的连接,表示两顶点有关联。注意上面图定义中的两个关键字,由此得到我们最基础最基本的2个概念,顶点(vertex)和边(edge)。直接上图吧。
图论(一)基本概念

一、顶点(vertex)

上图中黑色的带数字的点就是顶点,表示某个事物或对象。由于图的术语没有标准化,因此,称顶点为点、节点、结点、端点等都是可以的。叫什么无所谓,理解是什么才是关键。

二、边(edge)

上图中顶点之间蓝色的线条就是边,表示事物与事物之间的关系。需要注意的是边表示的是顶点之间的逻辑关系,粗细长短都无所谓的。包括上面的顶点也一样,表示逻辑事物或对象,画的时候大小形状都无所谓。

三、同构(Isomorphism )

先看看下面2张图:
图论(一)基本概念)图论(一)基本概念
首先你的感觉是这2个图肯定不一样。但从图(graph)的角度出发,这2个图是一样的,即它们是同构的。前面提到顶点和边指的是事物和事物的逻辑关系,不管顶点的位置在哪,边的粗细长短如何,只要不改变顶点代表的事物本身,不改变顶点之间的逻辑关系,那么就代表这些图拥有相同的信息,是同一个图。同构的图区别仅在于画法不同。

四、有向/无向图(Directed Graph/ Undirected Graph)

最基本的图通常被定义为“无向图”,与之对应的则被称为“有向图”。两者唯一的区别在于,有向图中的边是有方向性的。下图即是一个有向图,边的方向分别是:(1->2), (1-> 3), (3-> 1), (1->5), (2->3), (3->4), (3->5), (4->5), (1->6), (4->6)。要注意,图中的边(1->3)和(3->1)是不同的。有向图和无向图的许多原理和算法是相通的。
图论(一)基本概念

五、权重(weight)

边的权重(或者称为权值、开销、长度等),也是一个非常核心的概念,即每条边都有与之对应的值。例如当顶点代表某些物理地点时,两个顶点间边的权重可以设置为路网中的开车距离。下图中顶点为4个城市:Beijing, Shanghai, Wuhan, Guangzhou,边的权重设置为2城市之间的开车距离。有时候为了应对特殊情况,边的权重可以是零或者负数,也别忘了“图”是用来记录关联的东西,并不是真正的地图。
图论(一)基本概念

六、路径/最短路径(path/shortest path)

在图上任取两顶点,分别作为起点(start vertex)和终点(end vertex),我们可以规划许多条由起点到终点的路线。不会来来回回绕圈子、不会重复经过同一个点和同一条边的路线,就是一条“路径”。两点之间存在路径,则称这2个顶点是连通的(connected)。
还是上图的例子,北京->上海->广州,是一条路径,北京->武汉->广州,是另一条路径,北京—>武汉->上海->广州,也是一条路径。而北京->武汉->广州这条路径最短,称为最短路径。
路径也有权重。路径经过的每一条边,沿路加权重,权重总和就是路径的权重(通常只加边的权重,而不考虑顶点的权重)。在路网中,路径的权重,可以想象成路径的总长度。在有向图中,路径还必须跟随边的方向。
值得注意的是,一条路径包含了顶点和边,因此路径本身也构成了图结构,只不过是一种特殊的图结构。

七、环(loop)

环,也成为环路,是一个与路径相似的概念。在路径的终点添加一条指向起点的边,就构成一条环路。通俗点说就是绕圈。
图论(一)基本概念
上图中,北京->上海->武汉->广州->北京,就是一个环路。北京->武汉->上海->北京,也是一个环路。与路径一样,有向图中的环路也必须跟随边的方向。环本身也是一种特殊的图结构。

八、连通图/连通分量(connected graph/connected component)

如果在图G中,任意2个顶点之间都存在路径,那么称G为连通图(注意是任意2顶点)。上面那张城市之间的图,每个城市之间都有路径,因此是连通图。而下面这张图中,顶点8和顶点2之间就不存在路径,因此下图不是一个连通图,当然该图中还有很多顶点之间不存在路径。
图论(一)基本概念
上图虽然不是一个连通图,但它有多个连通子图:0,1,2顶点构成一个连通子图,0,1,2,3,4顶点构成的子图是连通图,6,7,8,9顶点构成的子图也是连通图,当然还有很多子图。我们把一个图的最大连通子图称为它的连通分量。0,1,2,3,4顶点构成的子图就是该图的最大连通子图,也就是连通分量。连通分量有如下特点:
1)是子图;
2)子图是连通的;
3)子图含有最大顶点数。
注意:“最大连通子图”指的是无法再扩展了,不能包含更多顶点和边的子图。0,1,2,3,4顶点构成的子图已经无法再扩展了。
显然,对于连通图来说,它的最大连通子图就是其本身,连通分量也是其本身。

你是不是已经对没完没了的术语感到厌烦了。是的,不能再多了!有了这些,我们可以出发探索图论的世界了!

本文转自 https://blog.csdn.net/saltriver/article/details/54428685,如有侵权,请联系删除。

收藏
评论区

相关推荐

CSS Modules 解决 react 项目 css 样式互相影响的问题
CSS Modules 解决 react 项目 css 样式互相影响的问题 CSS Modules 解决 react 项目 css 样式互相影响的问题 (http
Android中一个Activity关闭另一个Activity或者在一个Activity中关闭多个Activity
前言 最近项目中涉及需要在一个Activity中关闭另一个Activity或者在一个Activity中关闭多个Activity的需求,不涉及到应用的退出。自己首先想了一些方案,同时也查了一些方案,就各个方案比较下优劣。 方案一 广播的方式 这个是最容易想到的,同时也是网上提供最多的。 由于多个Activity要使用,关闭页面
C语言入门系列之6.一维和二维数组
一、数组的概念有如下几组数据: 学生的学习成绩 银行的账单 一行文字这些数据的特点是: 具有相同的数据类型; 使用过程中需要保留原始数据 。 C语言为这类数据,提供了一种构造数据类型——数组。在程序设计中,为了处理方便,把具有相同类型的若干变量按有序的形式组织起来,这些按序排列的同类数据元素的集合称为数组
js-Answers一
JavaScript的组成 JavaScript 由以下三部分组成: 1. ECMAScript(核心):JavaScript 语言基础 2. DOM(文档对象模型):规定了访问HTML和XML的接口 3. BOM(浏览器对象模型):提供了浏览器窗口之间进行交互的对象和方法 JS的基本数据类型和引用数据类型
一句话总结java七大设计原则
开闭原则:对扩展开放,对修改关闭。依赖倒置原则:高层应该不依赖地层。单一职责原则:一个类只干一件事儿。接口隔离原则:一个接口只干一件事儿迪米特法则:不该知道的就不要知道。里氏替换原则:子类重写方法功能发生改变,但是不影响父类方法的语义。合成复用原则:尽量使用组合实现代码复用,不要用继承,要解耦。
用python爬取《龙岭迷窟》评论,看看比同系列鬼吹灯作品以及《盗墓笔记》好在哪里?
↑ 关注 + 星标  有趣的不像个技术号每晚九点,我们准时相约   大家好,我是朱小五 最近不知道大家发现没有,新出了几部国产好剧,其中小五比较喜欢的就是鬼吹灯系列的《龙岭迷窟》。 自从开播以来,获得好评无数,豆瓣评分开播8.4分,目前有所回落,维持在8.2分,无论是原著粉还是路人观众,都对这部新网剧赞誉有加。在《鬼吹灯》系列的众多影视化作品中名
爬取五大平台621款手机,告诉你双十一在哪买最便宜!
↑关注+置顶 有趣的不像个技术号 今晚0点,相约剁手大家好,我是朱小五 明天就是双十一了,看了看自己手里的卡的像IE浏览器的手机,感觉可能等不到5G普及了。 我!要!换!手!机! 去哪买呢? 作为一个机(pin)智(qiong)boy,肯定要比价啊,哪家便宜去哪家 我用Python爬取了某比价网站的手机数据,获取了其中五大平台(天猫,京东,
每日一题(一)
写在前面 刷题在北联大的BUU平台,每日一题,每日更新,嘿嘿 [HCTF 2018]WarmUp刚开始看这个题真的一点思路没有,看源码、抓包一波操作过后还是选择去找了wp。。。wp说原题是有个hint.php,扫目录也可以扫出source.phphint.php里面说真正的flag文件是ffffllllaaaagggg里source.php里面是源码,代码审
每日一题(二)
2021.01.25 不知道为什么,腾讯管家扫毒的时候把我这篇文章扫出来了,然后我顺手给清掉了,只能选择重新发一遍了 写在前面 每日一题每十题开一篇新文章 [RoarCTF 2019]Easy Calc刚进来是有一个计算器的功能,试了好大好大的数,没有发生溢出情况,查看源代码发现了东西访问calc.php发现过滤的 php 代码<?phperrorre
每日一题(三)
写在前面 不知道 Web 的每日一题还能坚持多久,做到以前那种大比赛的 Web 题时发现一天时间很难吃透,或者根本就是一天时间内搞不懂,还听协会里的 pwn 师傅说一道 pwn 题能打三四天,一个星期,所以可能以后每日一题往各个方向的基础题发展,下一步准备把固态买回来重装一遍系统,然后进军 pwn!!! [极客大挑战 2019]BuyFlag进入 pay.p
沉寂了一周,我开发了一个聊天室
前言最近一周没有发文章了,我在这里向大家说一声抱歉。今天,我们来从零开始开发一款聊天室。好,我们现在就开始。了解WebSocket开发聊天室,我们需要用到WebSocket这个网络通信协议,那么为什么会用到它呢?我们首先来引用阮一峰大佬的一篇文章一段话: 初次接触 WebSocket 的人,都会问同样的问题:我们已经有了 HTTP 协议,为什么还需要另一个协
JavaScript与Node.js一起打造一款聊天App
聊天是我们人与人交流最直接的方式,互联网的加入使我们交流更加便捷。我们手机上的微信、QQ是我们手机必不可少的应用软件。那么,我们是否可以做一款聊天应用呢? 之前我自己闲着没事,研究过一些技术,做了一款即时通讯应用,下面我将选取几幅具有代表性的图片供大家参考。一、应用示图 以上是这款应用的主要页面,功能可能相对简陋点,不过基本的功能已经实现了,下面我将给出
表白神器——python,一“枪”一个准,限用一次!!(两次以上就无效了)
高考结束,相信很多小伙伴的都会想在大学找到一个适合的对象,那么你有没有想过表白用啥方式,相信很多小伙伴都看过程序员大哥用代码写的表白程序,当时有没有想学习编程的冲动呢!相信很多小伙伴会有,那么,今天这边文章的主题就是教大家如何用python写出表白程序!今天用到的是python中的turtle库,现在就跟着动起手来,为自己心中的女神画出一颗颗小爱心,来表达出
这可能是目前最全的!java开发手册嵩山版
在这里分享一份 [mybatis从入门到精通] 的强力教程,定能够助你一臂之力。 Mybatis基本介绍1. ORM和MyBatis1. 对象/关系数据库映射(ORM)1. 基本映射方式1. 流行的ORM框架简介目前流行的编程语言,例如Java、 C等,都是面向对象的编程语言;而目前主流的数据库产品,例如Oracle、DB2等,依然是关系数据库。编程语言和底
每日一问(一)Handler相关知识
1、Handler负责发送Message和处理Mesage2、Message就是消息载体,可用what区分,也可传递对象3、Message Queue消息队列,存储Message4、Looper循环取出Message Queue里的Message交给Handler处理。5、一个线程只有一个Looper和Message Queue,子线程中使用Handler一