建设网站要电脑才能吗,网站开发待遇好吗,制作网页的步骤,深圳画册设计师Hi#xff0c;你好。我是茶桁。
之前的一节课中#xff0c;我们了解了图的来由和构成#xff0c;简单的理解了一下图的一些相关概念。那么这节课#xff0c;我们要了解一下图的表示#xff0c;种类。相应的#xff0c;我们中间需要穿插一些新的知识点用于更好的去理解图…
Hi你好。我是茶桁。
之前的一节课中我们了解了图的来由和构成简单的理解了一下图的一些相关概念。那么这节课我们要了解一下图的表示种类。相应的我们中间需要穿插一些新的知识点用于更好的去理解图比如说邻接矩阵。
图的表示
我们一般用什么样的形式来表示图呢方法其实也是非常多样的。一开始说到定义的时候就采用的集合表示的方法。集合表示什么意思呢就是我们定义里面所说的那样G V, E一个序偶。
V和E, 集合里面的元素各是多少用集合的那种表达式可以展开就行了这个就叫做「集合表示」。
图形表示也很常见上节课一开始说到这个图的由来包括我一直跟大家说这个图是一个怎样的东西的时候都是采用的这种非常形象直观的方式去给大家进行讲解。
那它有什么样的特征呢图里面V中结点都是用小圆圈来表示的这个有序的结点对u,v表示由结点u指向结点v的有向边e。这个时候如果它是有方向的那我们就把这条边的u称为e的始点因为它是由u指向v的,v称为e的终点或者把它俩统称为端点。
如果是一个无向图首先我们需要先来理解一下有向、无向是一个什么样的意思。比如在一个图里面 我们在里边是没有箭头的,它就是一个无向图。如果是由v3指向v2那在就有一个箭头了它就是一个有向图或者说有向边。
大家注意对于无序的情况的表示符号是用圆括号来表示的和上面的那种尖括号是不一样的这个要区别一下。那无序的结点对(u,v)或者(v,u)表示结点u和结点v之间的无向边。这里就不区分始点终点了统称为端点此时仅称u, v为边e的两个端点。如果把v放前面u放后面也是一样等价。因为它是无序的。
我们来看一下怎么样根据这个图的几何表示给它转换成图形表示。首先告诉你这个图是一个集合表现的形式是由v和e表示的。
设图GV, E, 且V {v1,v2,v3,v4,v5}, E {e1,e2,e3,e4,e5}
我们只知道顶点和边还不够还要知道这些边是连接着哪两个顶点的。
图中的边为 e1(v1,v2), e2v1,v3, e3(v1,v4),e4(v2,v3),e5v3,v2,e6(v3,v3)
这样才算告诉你完整的信息。如果只是告诉V,E部份其实等于没有告诉你任何东西你都不知道这些边是连接了哪些顶点的。所以下面那些边的信息是关键。
需要注意的就是第一、我们要区分它是有向边还是无向边第二、这些点的相对位置是否重要。就比如V1是不是得画在画布的中央或者左上角或者画在其他什么位置这些位置重不重要。以及我们连接这些顶点的这些边非得是直线吗还是说圆弧也行或者其他的曲线都行只要连接上两个点。这些是大家需要考虑的。
这里你可以先不往后看了自己尝试着去画一下。画的漂不漂亮完全没有关系就包括可能有的结点有的圈画的比较大有的结点的这个圈画的比较小没有任何关系。包括这些点哪一个在正中间哪一个在左上角、左下角、右上角、右下角这个完全没有任何讲究。顶多就是有一些约定俗成的习惯。就像之前说到那个概率统计里面的正态分布曲线一样。高斯分布其实有很多种但是一般我们都给它做一个标准化转化成标准正态分布去研究。
我们高中写解析几何题一样你会发现往往的我们这些椭圆题或者双曲线的题他都是以这个坐标轴圆点为中心的那难道椭圆就不能是以其他点为中心吗并不是这样子。其实这个更多的时候只是为了降低一种繁琐的程度没有说就一定要怎么样怎么样这个大家需要知道一下。
好我们现在来看一下这个答案G的图形表示为 这道题就是这个样子有些边是有向的有些边呢是无向的。这个信息区分就是通过是圆括号还是尖括号来区分。尖括号就表示它是一个有向边圆括号的就是无向的也就没有箭头。这其中e1、e3、e4、e6是无向边e2、e5是有向边。具体的这些点是要画在什么样的一个位置其实压根不重要。
比如V5这个点是一个孤立的点。它是一个孤点那你画在任意地方都一样都可以。只要不改变这个图的本身结构就行。你不能V3和V5连上那这个就不行了。
接下来我们来看一道相反的题就是我们知道了图形表示现在需要我们将其转成集合表示。我们已知图GV,E的图形表示如下写出相应的G的集合表示。 这个其实也很简单就是分两步一个求v一个求e。首先看一下总共有几个顶点然后分别把它们写成一个集合。再之后这些顶点又有多少个边相互连接哪些边是有向的哪些边是无向的。其答案如下
G V, E {1, 2, 3, 4, 5} {1, 11, 2(1, 4)(1, 5)(2, 3)❤️, 54, 34, 5}
题目不难,就是一种转换。带着大家熟悉一下两种表现形式。大家这时候不要嫌麻烦或者偷懒。这个其实很简单但是很多东西如果不去自己尝试一下你不会发现一些可能之前发现不了的东西。不下笔的话往往不会了解到一些信息。这个只有自己去尝试了之后才能明白。
一些点需要给大家说一下就是这些边的表现形式非常多样外面那个大圈就是由1那一点引出来的转转转回到了自己本身这样画是OK的。如果我们在这里只是画一个小小的圆圈同样表示这个边这两个是等价的。
画成这种形状这里这个图画成这种形状是否代表着我这个它包含的里面2345的这些点呢其实是没有任何关系的。这个图里不存在什么包含不包含的这种关系别看它好像给这些围起来了里面的点好像是被它围在中间一样不是这个样子的所以这些边、点的表现形式非常多。更多的时候我们是看怎么样美观怎么样写起来画起来比较工整。
这题答案集合表现就是GV,E再把v和e给拆开v是一个集合所以用花括号表示。它就是这5个点1、2、3、4、5很简单。关键是这些边我们要把这些边给找出来。这个边其实你一个一个去找按顺序去找就行了。它有几条边它有哪一个指向找出来。再按照这样的顺序把这些点给找出来在这个集合里面。
因为集合本身是一种无序的一种结构所以在这里顶点集写成{1,2,3,4,5}。但是如果写成一个非常乱的顺序比如{2,4,3,5,1}也完全可以完全等价。
学习这些不要纠结这些东西你要知道它是一个无序结构所以你怎么样写都OK。为什么我们一般写成这种顺序结构呢就是美观比较符合人类的阅读习惯。如果你非写成一个乱序压根就不算错。同样对于e里面e这个集合也是一个一个括号写。它里面就是一些边的集合了在这里边的顺序可以任意对调。
关键还有个什么就是大家要把这些有向边、无向边要区分开来。就是这个表示方法容易出错容易统一的用这个圆括号去表示了大家尽量避免这个问题。
说完了这个两种表现形式之后我们再来看一下它们各自有什么优缺点。
首先集合表示的优点是可以精确描述图的组成信息。因为我们已经把组成这个图的两个基本要素一个是顶点一个是边都给它罗列出来了。所以它是非常精确的。集合表示的缺点就是比较抽象不易于直观理解。这个是很明显的尤其是我们说到边比如说我给你这个集合表现形式虽然我告诉你哪些点有哪些边但是你不可能像图这样一眼望过去就知道哪两个点之间有这些边连接以及这些边是否有向还是无向有向的话是由哪个点指向哪一个点这里面有没有环。都不是那么直接容易看出来的。
再来看看图形表示图形表示的优点就是集合表示的缺点反过来了因为它可以很直观形象地表示出来所以易于我们人类去理解。但是它有一个致病的缺点如果这个图里面的结点或者边数量比较小的话那用图来表示完全可以而且非常直观。但是如果结点以及边数量非常多几千亿个就像这个宇宙中的这种类银河系的这种系外星系或者超星系团数以千万计或者说数以亿计如果要用图形表示的话那就不可能了。那你得画到什么时候计算机即便能画出来人也看不过来。
所以说他们俩各自都有一些优缺点。
那我们关于图的表示只有这两种方式了吗一个图形表示一个集合表示。其实并不是其实图的表示是一个三国争霸的状态还有一霸没有出现这个一霸就叫做矩阵表示。
我们在这里将它列出来给大家看一下 A G [ 0 1 0 0 1 1 1 0 1 0 0 0 0 1 1 1 0 1 0 0 1 0 1 1 1 0 0 1 0 1 1 0 1 1 1 0 ] \begin{align*} A_G \begin{bmatrix} 0 1 0 0 1 1 \\ 1 0 1 0 0 0 \\ 0 1 1 1 0 1 \\ 0 0 1 0 1 1 \\ 1 0 0 1 0 1 \\ 1 0 1 1 1 0 \end{bmatrix} \end{align*} AG 010011101000011101001011100101101110
我在这里列出来的这种形式就是矩阵表示。是不是很疑惑这个矩阵表示是怎么样去表示一个图的呢
除了集合以及图形表示之外为什么会多出来这么一种矩阵表示因为我们很多时候尤其是进入信息化时代大部分的数据处理都是用计算机去做的图也不例外。我们也希望计算机能帮助我们去处理关于图的这些数据然而对于计算机而言集合的形式或者图形的形式都不太适合。集合的形式输入给电脑里面电脑它往往也不大明白这个该怎么处理图形的形式可能更差。
我们知道现在人工智能就有一个领域叫做计算机视觉就是专门让计算机去像人类一样拥有视觉识别的功能。不过用于处理图可能还是有点勉强。可是矩阵是一个非常适合计算机的形式我们上线性代数的时候就知道在计算机里面我们可以去做矩阵运算所以就想到用矩阵能不能去表现这些图。
邻接矩阵
如果我们用矩阵来表示的话那我们得先约定一些东西。本身矩阵和图是两个差别很大或者说隔得有点远的东西。那我们怎么样去给它做出一些约束呢
首先我们这个矩阵里面的这些行列需要有固定的次序行列的位置不同代表不同的矩阵其次需要讲图中的结点按某种既定顺序排列再次若并未给出具体排序则顺序默认为书写结点集V时的结点顺序。
我们知道即便仅仅是行列的位置不同这两个矩阵也是完全不同的。比如我把这个2*2的矩阵第一行1、2第二行3、4做一下转置那第一行就变成13第二行就变成2、4。这就表示成两个不同的矩阵了。
所以矩阵的行列是有一个固定的次序的它不能任意的变动。为了满足这个条件我们需要需要将图中的结点按照某种既定的顺序做个排列。如果你没有按照这种规则去做出排列那我们这种顺序就默认成书写这个结点集V的时候的结点顺序。
比如我们有5个点就像我们之前那道题里面{1,2,3,4,5}分别标号是12345的是5个点如果写成35214没有给它一个具体的排序方式的话我们就可以按照35214这种顺序去约定它。第一个点就对应着标号为3这个点第二个点就是标号为5的这个点以此类推35214。
好说到这里可能大家还不是很明白为什么要做这种约束。接下来就需要用到刚才说的一个内容了设这个图是GV,E其中V{v1,v2,…,vn}并且已经确定了各结点的排列次序则将n阶方阵 A G ( a i j ) n x n A_G(a_{ij})_{nxn} AG(aij)nxn称为G的邻接矩阵其中 a i j { 1 , 若 V i 与 V j 间右边 0 , 若 V i 与 V j 间无边 i , j 1 , 2 , . . . , n \begin{align*} a_{ij}\begin{cases}1, 若V_i与V_j间右边 \\ 0, 若V_i与V_j间无边 \end{cases} i,j 1, 2, ..., n \end{align*} aij{1,若Vi与Vj间右边0,若Vi与Vj间无边i,j1,2,...,n 这个邻接矩阵里面的每一个元素 a i j a_{ij} aij它代表了代表了这个矩阵里面第i行、第j列的这个元素。它的取值只有1和0。这个逻辑关系其实非常简单就是说你vi这个点和vj这个点如果是有边连接的话你对应的这个元素就是1如果两个点之间没有边的话那它就是0这个是只有两个取值的。所以这个邻接矩阵本身的取值是非常简单。取1还是取0就完全取决于e就是看e。如果有边就是1无边就是0。
我们接下来看一个例子给出了一个图G写出图G的邻接矩阵。 这个里面总共有V1到V6总共有6个点我们就按照这个下标的顺序来给它做个排列。
按照下标的顺序排列也就是说行方向是按照V1到V6的方向列方向也是按照V1到V6的这个方向去排布。然后我们会观察到行和列所交的位置代表了V1和V2之间有没有连线。如果有的话就是1没有的话就是0。
大家可以去自己尝试一下你就看一下矩阵列出来是怎样一个形式。我这里给大家列一下 因为V1、V6都是一样的大家会发现这个矩阵其实是一个对称的结构。因为, 行1列2是表示V1和V2连线是1行2列1呢同样表示V1和V2的连线也是1。所以对于无向图而言邻接矩阵就是一个对称的结构是一个沿对角线对称的结构。
但是如果是一个有向图的话那就不一样了这个时候约定V1行代表了由V1指向的点如果在这里V1、V2之间的这条边是由V1指向V2的方向是指向V2的在行1它代表V1指向V2。但是如果在行2就又不一样了代表了由V2指向V1。
我们再反过来看如果箭头是由V1指向V2的话并没有一条边由V2指向V1在这里它就是0了。所以有向图无向图在这方面会稍微有点不一样大家注意一下就OK了其实它表达的意思呢很简单。 A G [ 0 1 0 0 1 1 1 0 1 0 0 0 0 1 1 1 0 1 0 0 1 0 1 1 1 0 0 1 0 1 1 0 1 1 1 0 ] \begin{align*} A_G \begin{bmatrix} 0 1 0 0 1 1 \\ 1 0 1 0 0 0 \\ 0 1 1 1 0 1 \\ 0 0 1 0 1 1 \\ 1 0 0 1 0 1 \\ 1 0 1 1 1 0 \end{bmatrix} \end{align*} AG 010011101000011101001011100101101110
写成这个形式的就跟刚才一样了。
那么我们刚才呢说了很多这种约束条件就比如说这个图的邻接矩阵因为行和列位置交换一下的话都对应着不同的矩阵所以我们说了要约定这个节点或者说顶点的一个默认排序。那在这里我们探讨一下图的这个邻接矩阵这个矩阵的形式是唯一的吗
一般而言同一个图按照不同的顶点排列次序写出的邻接矩阵形式上是不同的但是相互之间可以通过调换某些行或列的位置而得到。对邻接矩阵的行或列进行交换对应的实际上是在对顶点的排序中调换顶点的位置。若不考虑顶点排序的不同产生的邻接矩阵的不同则图与邻接矩阵之间是一一对应的。实际操作上往往略去顶点排序不同导致的邻接矩阵的多样性 选择任意一种顶点次序得出的邻接矩阵作为该图的邻接矩阵。
以上几句话的意思就是告诉大家不要纠结你选定一个之后把这个顶点的排列顺序给写下来然后我们就按照这个顺序去做这个邻接矩阵就行了。不用去管它有可能会有其他形式的一个排列其他形式的排列你不能说它不合理都是合理的但是不用去管那些。就按照你写的这个去做就可以了。
在说了图的邻接矩阵之后我们已经学了三种图的表现形式了。一个集合表示、一个图形表示、还有矩阵的一个表现形式。接下来我们要来看看图的种类。
图的种类
其实图的分类方法也有非常多种首先按照它这个边有没有方向我们可以分成3类。一类是有向的就比如下面这张图 一类是无向图,就是它这个边都没有方向的 还有一类就是混合图,混合图就是里面既有有向的边也有无向的边这种叫做混合图。 混合图大家不要觉得奇怪往往也会有一些实际运用。它这些边看似感觉像是没有方向的但是实际上它代表了一对方向相反的连接相同端点的一对。在混合图中可以将无向边转换为方向相反的两条有向边来处理 为什么要做这样的转换呢因为我们知道有向边和无向边的处理是有点不一样就像我们在写程序的时候把一个int和一个浮点型的变量加在一起的话这个程序自动的会做一个强制类型转换。就变成一个精度更高的浮点型的形式。
如果按照图的里面有无平行边重边来分类的话可以分成以下几类
多重图有平行边的图 线图无平行边的图
简单图无环的线图 简单图和线图之间的区别就是看它有没有环。
还有一种分类方法按边或者顶点是否赋于权重进行分类氛围赋权图和无权图。
赋权图: G是一个三重组V,E,g或四重组V,E,f,g 其中V是结点集合E是边的集合f是V到负实数集合的函数g是从E到非负实数集合的函数。
关于「权」我们刚才所说的包括之前那个高铁线路的例子里面高铁线路里面线段的长度并不代表真实的这个线段长度的关系。图边的长度并不能代表任何东西没有任何含义。当然在这我们就可以通过赋予权重的形式来给图更多的实际意义。
赋权图其实和图的定义非常相似只不过就是多了一个或者两个函数。f是关于V也就是从顶点到非负实数的一个映射函数。它可以把每一个顶点赋予一个非负实数。g是给每一条边赋予一个非负实数它们都是一个函数。 这张图中有a b c d四个点。现在我们不单单的是只有点和边给每个顶点赋予了一些数字同样的给每条边赋予了一些数字。先不管它这个实际意义是什么只是一种抽象的数据结构。我们可以人为的给它这些数字赋予一些意义。比如说可以表示距离a、d和b、d之间的一个距离。
顶点的数值又代表了城市的半径有多大我们可以根据自己的需要去赋予它实际意义。但是它对应的这种数据的数学抽象模型都是一样的。
我们根据题目里面给的这些数字能不能写出这个相应的函数呢
f(a)9, f(b)6,f©7,f(d)10,g((a,b))50,g((a,c))70,g((a,d))45,g((b,d))40,g((c,d))35。
其实形式也非常简单我们就需要注意一下关于顶点一般约定俗称是用f来表示g是代表了边的函数。所以在这里a、b是用这个括号括起来代表一个边所以它是套两层括号。
就是把这个函数名称写出来,然后括号再加上你对应的顶点或者对应的边数值是多少就是这么简单。这个就是赋权图里面函数的写法。
赋权图函数这些数字的含义往往在我们一些优化方式里面尤其是在一些路径规划里面是非常有用的。有的同学可能是学过像greedy这种弹性算法它这里面往往针对的就是有这种权重的图去研究的。因为它要算最短路径图如果没有赋予它相应的权重的话那它没有意义。
还有一件事大家可以注意一下就是赋权图要么是一个三重组合要么是一个四重组合。也就是说要么是V,E,g, 要么是V,E,f,g。这里面不管是三重还是四重都包含了g。而f往往是可有可无的。
这代表往往大部分情况如果研究有权图边的权重绝大部分情况下都是有的。几乎你不会遇到只有顶点有权重而边没有权重这种情况。顶点可以没有权重但一般按照实际问题来讨论的话往往边的权重是会有的。
现在我们一共了解了三种分类方法不过大家不要觉得这三种方法是彼此孤立的、只是一个单纯的并列关系并不是这个样。往往是综合应用的比如刚才我们举例的赋权图全称应该是「无向赋权简单图」。
首先它是一个无线的第二它有权重第三呢它是一个简单图因为它是一个无环的线图。
OK在讲完图的种类之后咱们这节课就结束了。下节课就是比较有意思的一个点了「最短路径问题」是非常重要的一个问题。
