离散数学是计算机科学的基础理论，离散结构的基础知识和逻辑思维的形式化是信息技术类学生的基本功，离散数学的基本概念是理科专业学生进行信息类课程学习的重要基础。 本课程介绍计算机科学和信息技术理论基础的概念和思想方法，介绍数理逻辑、集合论、图论、抽象代数和形式语言与自动机等各部分的基本概念，介绍离散数学基本概念和空间信息技术之间的联系与结合，培养学生理解和掌握离散数学基本概念，采用形式化方法分析问题，并能自觉运用逻辑分析、结构层次分析和同构类比等思想方法解决问题的能力。
62-路径与连通性
Loading...
From the course by Peking University
离散数学概论 Discrete Mathematics Generality
155 ratings
From the lesson
图论：图的基本概念
Meet the Instructors
陈斌副教授
北京大学
[音乐]
hi，欢迎回来，接下来呢我们来介绍关于简单图的一些拓扑性质，
那么其中一个很重要的呢，就是图上的路径，
路径呢，说明了这个图，它的这个节点之间的一种连通的一种方式，
我们首先来看第一个拟路径，叫pseudo path，
那么拟路径呢是从一个顶点v1到 另一个顶点v2所定义的一种，一个结构，
是一个序列，那么这个序列呢是从 顶点开始，v1开始，到vl结束，
那么在这个序列当中，它是依照这个顶点，边，顶点，边这样的一个顺序
来排列这样的一个序列的，所以呢它有v1，然后e1，然后v2，e2，
v3，e3，然后一直到vl-1，到el-1，最后呢最后是vl。
那么其中这里头v1，v2，这个没有什么讲究，但是呢，这个e，
这夹在顶点之间的这个边就有讲究了， 这个ei呢它应该要等于vi到vi+1，
也就是说这个ei这条边它应该是要以它前后的两个顶点
作为端点，这样的这个边才可以放到这个序列里来，
然后呢，这样的序列才能够称之为叫一条叫做拟路径的。
当然如果是一个有向图，那么它包括的是有向边的话，那么就是vi到vi+1的
这个二元组，如果是一个无向图，那么它就是一个集合，vi，vi+1 这么一个集合，它是一条无向边。
总之呢不管是有向边也好无向边也好， 那么这个ei都应该以这个它的前后
vi和vi+1作为两端的这个端点。
那么在这样的一条拟路径中间， 我们把这个它所包含的边的数量就称之为拟路径的长度，
当然我们知道如果1，2，3，4一直到l是 连续的话，那么这个长度呢就应该是l-1，它包括了从e1到el-1
这么多条这个边， 我们来看看这个，我们下面这个图的这个例子
这是一个拟路径的例子，那么首先，这个图呢包含了a，b，c，d，e
这么五个节点，它是一个无向图，它是一个简单图，
那么其中有一条拟路径是这样的，从a开始， a然后呢，a所关联的一条边1，
然后呢再到了e，那么1这条边呢就是以a，e作为两个端点，所以a，1，e
然后呢再到7，然后再到b，然后再到3，然后再到c，
然后呢再，再返回来，还是3这条边， 然后呢再回到b，所以呢这里有一个b，3，c，3，b
然后再经过2，再回到a，当然这个呢是一条 完全符合这个拟路径定义的这么一个
节点和边夹杂在一起的一个序列，所以 呢它是一个合格的一个拟路径，而且呢它的长度，它包含
了5个边，所以呢它的长度为5，这个拟路径的长度为5。
这是拟路径。
第二个拟路径呢， 也可以从c开始，我们可以从c开始，c，然后它所关联的
因为接下来呢要么就是3，4，5，这其中的一个， 所以我们选择了4，c，4，然后呢自然就是e，
然后呢再4，再c，回到c，然后呢再用3到b，
再到7，再到e，再回到
4，然后再最后呢回到了c，所以呢这两个拟路径，我们发现呢，
它虽然符合这个拟路径的定义，但是呢如果按照
这个我们通常对于路径 的理解，我们来进行走路的话，除非你是散步来来回回的走，
否则的话呢，我们会发现它这里头有，第一个例子 它有重复的边，就这个3它重复了两次，
然后第二个例子呢，它不光有这个重复的边，4比如说它重复了三次，
而且还有重复的顶点，它这个e重复了两次，对吧，那么当然这个拟路径
对于说所谓的重复的边或者是重复的顶点它并没有任何的限制，
所以呢，你你只要是符合这个边，它 两个端点是在这个序列前后就可以了，那么这都是符合
条件的这个拟路径，那么当然如果说是重复的话，我们
可能会设法需要说在一些应用当中把这些重复的边或者节点去掉， 那么去掉了以后，它就形成了一些新的概念，
这叫做路径和通路，所谓的路径呢就是说如果说拟路径当中的 边各不相同的话，我们就把这种拟路径称之为
路径，就叫做路径，比如说我们还是同样的一个例子， 那么像这个路径呢，就是a，1，e，然后7，b
然后呢3，c，然后到4，再到e，再到6，再到d，
那么所涉及到的边是1，7，3，4，6， 是没有重复的，虽然顶点有重复，e，
因为e它关联了有1，7，4，6这四个，四条边， 但是呢，它虽然经过了两次这个e，但是并没有
把这个边进行重复，第一次经过e呢是到7，然后第二次经过e呢是到4，
这条边，从4进来，然后再从6出去， 所以这样的，只要是边各不相同，我们就称之为路径。
那么如果在这个路径里面，我们进一步地说，
这个路径当中的顶点也要各不相同的话，那么就把这种路径就称之为通路，
通路里边，就不能够允许包含相同的顶点了，
比如说a，1，e，然后呢7，然后b，然后3，然后c，然后5，
然后d，那么这个呢，是一个长度为4的 一个通路，它经过了所有的这个a，b，c，d，e，
五个顶点，啊这是一个通路，那么我们如果这个路径和通路
它的第一个顶点和最后一个顶点是同一个顶点的话，也就是说，它经过，绕了一圈又回到- 了原地，
那么这种呢，就称之为闭合的， 那么v1等于vl的路径呢就称之为闭路径。
比如说a，2，然后呢b，7，然后呢e，4，然后c，5，
然后d，6，再通过e，然后再经过1，然后返回到a，
那么这个呢就是经过了一圈，返回到顶点a的这么一个闭路径。
那么它之所以是路径，我们看出来它中间的没有重复的边，对吧？
那么如果是头尾两个顶点是相同的通路，那么就称之为回路，啊回路
回路呢，里边不光是不包含相同的边，也不能包含相同的
顶点，那当然除了这个第一个和最后一个之外， 所以呢有这么一个例子，从a出发，
a，1，e，6，然后呢d，然后再到5，再到c，
然后再经过3这条边回到b，b呢再通过2这条边再回到a，
那么a呢绕了一圈再回到这，那么这条通路呢它的长度呢就为5，
它关联了5个不同的顶点，其中呢第一个顶点
和最后一个顶点是相同的，所以这个就不算是一个顶点了，那么它经过了5个顶点
有5条边，回到了原地，这种呢叫做回路。
那么关于路径和通路呢，有一些性质，我们可以推导出来，其中
第一个呢，是路径和通路的这个定理，它说在有n个顶点的这个图当中，
当然这个图呢是简单图，就是无向，无环，没有
重边的这种简单图，在这个图里头，如果有
顶点从u到v的这个拟路径的话，也就是说它成功地造出了这么一个序列，
从u开始，然后边，其他顶点，然后再什么什么，
再其他的边，一直到，最后呢关联到v的那条边，然后最后 能够到达v这个顶点的话，那么构成了一条拟路径，
如果存在u到v的拟路径，那么u到v呢，就必然会有路径，
那我们知道路径是一种特殊的拟路径，也就是说它的边是不重复的，
那么在这呢，我们实际上可以通过 拟路径来构造出路径来，
那么也就是说只要是在这个拟路径里头查找这个相同的这个边，
那么相同的边呢，只要把这个相同的边之间，
它的这个边进行压缩，给它替换掉，再把相同边之间的所有的这些
其他的边和节点全部都剔除，不要， 然后把这两个相同边之间的这个内容全部压缩过来，
那么它就能够变成一条路径了，就是反复地用这种边压缩的方法，
然后最后呢能达到没有重边的这个目的，最后呢能够，终于能够构造出这个路径出来，所以呢
只要有u到v的拟路径，它就必然会有，存在u到v的路径，也就是边不重的，
然后而且呢，必然会有长度不大于n-1的这个通路，
我们知道通路呢是，不光是边不重，而且顶点也不重， 那么这个它之所以能够保证说长度不大于n-1，
那很显然，只要你长度大于n-1，你一旦达到n了以后，
那么这条拟路径，就这条通路上，必然会有n+1个顶点，它的长度才会n，
那么很容易，根据这个鸽笼原理，n+1个顶点里边，肯定
会有，其中有两个顶点它是完全相同的顶点，
对吧？那么如果存在相同的话，那就不再是通路了，所以呢
这个只要是一个通路，在n个顶点的图当中， 它的这个通路的长度肯定不会大于n-1，
所以呢我们是在拟路径
当中考虑了，首先考虑边压缩的方案，然后呢再考虑点压缩的方案，
只要在路径当中，有两个相同的 这个顶点，我们就把这个相同顶点之间的所有的内容
都给它删掉，把这两个相同顶点重在一起，这个呢就叫做重复顶点的压缩。
只要有重复顶点的压缩这样的一个操作，我们就可以构造出通路来，
那么关于闭合的这个路径，和闭合的通路，
也有这个相应的定理，那么在一个有n个顶点的图当中，
如果有一个顶点v到v，就是从v出发，然后回到v的这个闭路径的话，
那么一定会有一条从v到v，长度不大于n的回路， 那么这个实际上也可以用鸽笼原理来进行证明，
因为长度为n的这个回路，它就已经包含了n个不同的顶点了，
你如果长度再长，那么它就
这个回路上的顶点就必然会重复，因为它最多只有n个不同的顶点嘛，
所以呢这个闭路径和回路的这个定理也很容易地进行证明。
Explore our Catalog
Join for free and get personalized recommendations, updates and offers.
Coursera provides universal access to the world’s best education,
partnering with top universities and organizations to offer courses online.
© 2018 Coursera Inc. All rights reserved.
