Explore
For Enterprise
Join for Free
Log In

Explorar
Buscar
For Enterprise
Inicia Sesión
Únete de forma gratuita

基本定义

Loading...

离散数学

Universidad de Shanghái Jiao Tong

4.7 (22 calificaciones) | 5.7K estudiantes inscritos

离散数学是计算机专业基础课程之一。本课程重点讲解离散对象的计数问题、图论问题、网络流问题等计算机科学中的重要基本知识。本课程将为后续如数据结构、算法设计、复杂性理论提供必要的基础，课程内容在人工智能、机器学习、网络设计与分析等前沿领域有重要应用。课程重点培养学生逻辑思维能力及解决问题的能力。

Revisiones

4.7 (22 calificaciones)

5 stars
18 ratings
4 stars
2 ratings
3 stars
1 ratings
2 stars
1 ratings

De la lección

网络流

基本定义14:36

Impartido por:

Long Huan 龙环
助理研究员

Transcripción

[音乐] [音乐] [音乐] [声音] 各位大家好！本次我们开始讲解图论有关的知识点本次我们主要讲一些基本的定义，以及一些特殊的图，包含了比较多的一些基本概念首先什么是图呢？图我们说是一个有序对，包含两个元素，一个是 V，是所谓的顶点集，第二个是 E，是边集 E 呢我们说它是顶点集选二的这样一个子集，表现成在这里给了一个图 G。有的时候，为了方便我们也用函数的形式，也就是说 V(G) 或者 E(G) 来分别表示图 G 的顶点，以及和图 G 的边集什么叫画图？或者是什么叫把一张图画在一个、一张纸上？就是说我们用点用黑心的点来表示顶点，然后用直线来表示边。下面，我们给出了三个图的那个画法 G1、 G2、 G3。我们说给了一个图之后，它的画法一般来说是不唯一的图中顶点的个数我们取了一个名字叫做阶经常是用那个 V 加它的一个绝对值符号来表示。有的时候呢也用 G 的绝对值来表示图中顶点的个数，也就是 |G| 的大小。那么 E 呢，我们刚才说了，E 是顶点选二的这样一个子集那么其中的每一条边用小写的 e 来表示小写的 e 它有两个顶点，分别是 u 和 v 这个 u 和 v 我们在图中就称为它们是相邻的或者是说 u 是 v 的邻居。有的时候也称为 u 和 v 是相关联那么我们说每一条边与且仅与两个顶点相关联。因为每一条边的话它是由两个顶点所决定的那么 N(u) 呢是表示 u 的邻居点的个数这里举了一个例子。我们在这里的这张图中我们说 v1、 v2、 v3、 v4，一共有四个顶点那么图 G 的那个阶是 4，那么 v1 的邻居个数呢就是 4，因为它包含了四个邻居分别是v1、 v2、 v3 和 v4。那么顶点的度顶点的度数就是说我们的邻居的这个大小、邻居的这个大小那么刚才的那个图中我们已经提过了，刚才那个 G 的图中刚才这样一个 G 图中，它们 V1 的邻居的大小就一共是四个那么我们经常用两个符号 δ(G) 和 Δ(G) 来分别来表示图 G 的最小的度数和它的最大度数当然我们说任给一张图的话，它其中任意一个顶点的度数一定是小于等于边集的大小因为我们说度数就是它与多少个边相邻，那么跟它相邻的边的个数不会超过所有的边的个数我们看这样一张图 G。我们说最小，图 G 的最小的点的度数是 1。有两个点都只有一个邻居，就是用红色表示出来。那么它的最大的顶点度数 Δ(G) 呢是多少？是四。我们这里用蓝色这个点表示出来它与四个点相邻。好了，我们之前介绍的图都是无向图那么我们这里还要介绍所谓的有向图就是说我们刚才的边如果大家记得的话，我们说边 e 是等于这样一个 {u,v} 这样一个集合我们是通过一对顶点来定义一条边。注意这里是一个集合的表示。如果我们把这个集合表示换成一个有序对那么我们称它为一个有向阶，而原始的图称为一个有向图 u 呢经常称为 e 的起点，v 称为 e 的一个终点。在图中表示呢就是用一条从 u 指向 v 的这样一个箭头。我们把 u、 v 标在两侧，e 标在这个边的上头所以在本课中呢，除了显示声明以外，我们一般来说都是讲的无向图当我们说图论在生活中随处可见。这里给出了 2015 年上海市地铁一个线路图。大家可以看到，我们如果把每一个站理解成一个点，把两个站之间的那个地铁线路理解成一条边的话那我们就可以的相应的给出图的、这样一个图的这样当然现实中还有很多其他的问题，我们都可以抽象成图图论一个相关的重要概念叫做子图我们现在已经有两个图 G 和 G'。假如说我们知道 G 中包含的顶点，也就是说 V(G) 一定是都在 V(G') 中它 G 的顶点都是 G' 的顶点。并且 G 的边也都一定是 G' 的边那么我们说 G 是 G' 的一个子图比如说我们用这个现在这个黑色的表示图 G' 的话那么我们说红色表示的这些点和边形成原图 G' 的一个子图。我们现在对子图加一个要求如果我们还要要求 E 中的边呢，它正好等于 G' 中的边交上 V(G) 选二。也就是说凡是在 G' 中的边，并且这个点又已经是在 G 中的话那么这个边一定也在 G 中。那么这样的一个子图，我们叫做原始图 G' 的一个导出子图。大家看一下右边这个，还是同一个例子，我们用灰色表示原始的 G'，然后红色高亮表示是那个 G 的部分。我们问现在红色的部分是否是原图的一个导出子图呢？答案是否定的。因为我们说这三个点这三个点。比如说这一条边我们说它是在它是在原图 G' 中的。这条边也是在原图的 G' 中，但是它们没有在新的那个子图 G 中，所以它不满足导出子图的条件。那我们如果把这两条边加回去它就形成了原图的一个导出子图。类似的我们可以定义生成子图。就是说现在我们不要求所有在原图 G' 中的边。如果它的点也在 G 中的话，那么这个边也要一定在 G 中而是我们对点有要求。我们要要求 G 包含了 G' 中所有的顶点那么我们说 G 是 G' 的一个生成子图右边同样的给出了一个例子。下面原始的 G' 就是我们开始给出的那个黑色的图，那我们用红色表示了那个图 G。注意到现在红色包含原始 G' 中所有的点当然它的边也是原始图的一个子集。所以说我们说它是那个原始图的一个生成子图。大家一定要注意的是导出子图和生成子图的区别导出子图是说对边有一个强调，而生成子图是要求必须要包含所有的所有的顶点。当然我们说导出子图和生成子图都是原图的子图那么介绍了图之后，我们要介绍图对象之间的一些基本操作第一个是 G+eij 它的意思说就是在图 G 中间增加一条边 eij 这个 eij 呢，我们说它的两个顶点分别是 vi 和 vj 类似的去定义，从图 G 中减去一条边 eij 注意到我们如果这个减法操作，反复作用减法操作的话，那么我们可以得到原图 G 的任意的一个生成子图所以我们这个减这个边的时候，它的点是保留的接着我们可以把刚才的操作推广到集合之间我们这里用大 E 的 bar 表示，一根横线表示一个集合 E 拔呢是原图边集的一个子图 G 减去 E 拔表示从 G 中删去 E 拔中所有的边。还是要注意我们在删边的时候，它的两个顶点是保留的那么 G-v，前面三个操作都是与边有关的操作，后面两个是跟点有关的。我们从图 G 中减去一个点 v，是什么呢？我们要把这个点 v 以及相关联的边都删掉我们这里画一个图的例子。这是一个点和它相邻的另外一个点那么这是原图 G，我们现在把这个点 v 删掉。我们把这个点称为 v。那么我们要把这个点去掉并且要把这两条边都去掉。也就是说新图中间只会剩下两个点所以我们如果反复的操作减去这个这个点的这个操作的话呢，我们可以得到原图的任意的导出子图这里还是要强调的是导出子图。我们刚才说我们任意删边的话会得到任意生成子图，这两个之间的区别一定要小心那么类似的我们可以扩展到点集的操作。 v 拔是原始点集的一个子集。那么我们从 G 中删去 v 拔中所有的顶点以及与这些顶点所相关联的边换句话说，与边相关的操作，加法和减法，我们对点是没有影响的但是，当我们去删掉一些点的时候不单要删掉点，还要删掉点相关联的边就是说，我们刚才是用的加和减在一些文献中也经常看到用集合的符号，就是用并来表示加了一条边，比如说，用集合的减来表示删去一条边。类似的比如说，减去一个点，减去一个点集等等就是说这里和刚才的定义基本上是一样，只是说符号上什么的有所不同好了我们接着下来介绍一些重要的特殊图这些图中的一些概念在后面会被反复用到首先介绍一个比较简单的概念，是路径。我们从直观上讲，什么是路径呢？路径就是这样的一条线。 V 是，比如说是 n+1 个点，0 到 n。然后什么是 E？E 每一个表示的是从 i-1 号点到 i 的这样一个二元组。比如说这里是 0 号点、 1 号点、 2 号点、 3 号点等等注意的是，第 i-1 号点只和第 i 点相邻当然，我们说，比如说以 1 号点它跟 0 和 2 都相邻，就是说后面不断地增长出来有了路径之后我们可以定义环环和路径的唯一区别在于，路径的话，第一个点就是这个路径的，这个图的初始的这个顶点和最后这个顶点是不一样的而环的话要求我们沿着这个环走，它最后会走回来也就是说我们现在还是有 n 个点，那么第 i 个点和第 i+1 个点又或者是第 i-1 个点，它们都是相邻的最终，我们要加入一个特殊的边，是 1 和 n 大家注意，路径和环的区别，就在于我们最后有没有加入这条边。就是说，把整个路径给让它走回到出发点的这样的一条边从图上来讲，就是比如说这个 C3 表示 3 个点的环，C4 表示 4 个点的环，类似第二个我们想讲一个重要的特殊图是二分图二分图直观上讲，我们把点分成了两部分。第一部分包含 n 个点，第二部分包含 m 个点，我们用 Bn,m 来表示那么边呢都是在这两部分之间有边。就是前 n 个点和后面的 m 个点，它们之间有边。但是内部，u1 到 un 内部，或者是 v1 到 vm 内部没有边的。我们看一张图就明白了。比如说 B1，1，我们说分成了两部分，第一部分是上面这个点第二部分是下面这个点。它们之间有边，但是没有从比如说，没有从一个点到它自身的这样一个边然后第二个例子是 B1，2，我们说第一个集合中间包含下面的这一个点，第二个集合表现的是上面的两个点它们两个集合之间有边。但是，比如说上面这个集合的两个点之间是没有边的。类似的 B3，3，我们说把点分成两部分，下面这三个点和上面这三个点上下的顶点之间是有边的，但是上面的顶点之间没有边，下面的顶点之间也没有边还有一个在，无论在理论上或者在应用中都很重要的特殊图示，称为完全图完全图我们一般来说用 Kn 表示，n 是表示那个图的阶什么是完全图呢，就是说我给了你，比如说以 K3 为例给了，我们说 K3就是表示它有三个点 K3 是说它所有的顶点彼此之间全部相连这里的 K3，大家可以看，第一张图，所有的三个点三个点之间所有的边都加进去。类似的 K4，K4 是所有的四个点，每两个点都彼此相连。那么有多少条边呢？显然是有六条边那么有了完全图和二分图的概念，我们可以引申定义什么是完全二分图完全二分图是说，当然它首先是一个二分图。它的点是分成了两部分第一个部分是包含 n 个点，第二个部分包含 m 个点。我们这里注意，完全二分图是用 Kn，m 来表示什么是完全二分图呢？就是说，就是在定义二分图的时候，我们是说这里是用的一个子集关系。在定义完全二分图的时候，我们把这个子集关系我们把它变成了一个等号关系。比如说以 K1，2 为例子它的点分成两个集合。第一个集合只含有一个点第二个集合包含了两个点。但是第二个集合跟第一个集合中间的点呢，所有的所有的点它们都是相邻的这样一个关系类似的我们可以看 K3，3，就上面的三个点和下面的三个点全部相邻，下面的三个点和上面的三个点也全部相邻但是，它必须是一个二分图，也就是说上面的三个点之间没有边，下面的三个点之间也没有边好了，还有一个常见的一个图的概念是叫做一个正则图就是说我们定义了图，我们也定义了图的度数如果图中每一个点的度数都是一个常值小 r 的话那么我们把这个图称为一个 r-正则图。首先是最简单是 r 为 0 的时候 0-正则图就是所有的点的度数都为零，那是什么呢？我们称为空图这个图中只有有限个点，没有任何的边。这里是一个例子，包含了三个点的一个空图第二个当 r 为 1 的时候，我们称为 1-正则图，也就是说图中所有点的度数都为 1 这个时候是什么样子呢？它其实就是一些不相连的边集它可能，当然可能只有一条边，当然也可能是有限条边这样大家可以看到，在这样一条边或者是一个长度为 1 的路径它的每个点的度数确实都是 1 的。那么 2-正则图是什么呢？2-正则图我们说是不相交的一些环环上每个点的度数都是2。那么，2-正则图呢可以是一个环，也可能是若干个不相交的环。比如说在这里就是两个这里是两个不相交的环，一个是 C10，一个是 C3 那么 3-正则图的可能性就多了，这里只画了三个 3-正则图有个特殊的名字叫做立方图我们下面给出了三个 3-正则图的例子，每一个点的度数都是 3 这个在后面讨论中会用到这样一个概念在之前我们讲的图中，我们对点和边的添加没有做限制现在我们看有两类特殊的边。第一个叫自环自环说，是什么样一条边呢？是从一个点到它自身。换句话说，是存在这样一个点 v e={v, v} 这个集合。当然我们知道，它既然是集合的话，那么可以表示成其实只用到了 v 那么如果是这样一个，或者在图中就是右边这个那么称它为一个自环。那么什么是重边呢？重边是说我给了你 u 给了你 v 之后，如果有两条边有两条边 e1 和 e2 都以 u 和 v 作为顶点换句话说，这两个点之间有两条边的话，那么我们称 e1 和 e2 是重边。当然，我们说可能还有第三条边它也是重边，类似的情况。那什么是简单图呢？就是说，如果原始的图中没有自环也没有重边，注意我们这里都默认的是无向图那么我们就称它是一个简单图关于图中有两个会一直被用到的概念，第一个是称为路径，第二个称为游走。路径和游走首先是介绍路径。路径就是说我们沿着图上的顶点和边的这样一个一个序列去走，但是并且我们要要求这个走的过程呢它不允许出现环并且在这个走的过程中，每个顶点和每一条边至多只出现一次我们在图中看一个例子。我们在这个图中，我们说我们是从 v4 这个点一直走到了 v1，然后走到了 v5，然后走到了 v6，然后走到了 v3，然后是走到了 v7 大家可以看到，那么这个就是一个路径，这个就是一个路径它每一个点都只用到了一次，每一条边也只用到了一次。然后在写的时候呢，我们就是写成了这样一个大家可以看到，我们写成了这样一个顶点和边，v4 经过 e3 到达 v1，然后 v1 经过 e4 到达 v5，类似的那么什么是游走呢？游走是说我们现在还是沿着图上的顶点和边去走但是我现在走得比较松了，要求比较松我们可以允许环，而且点和边也可以重复使用这里我们还是看一个例子。从 v4 我经过边 e3 到 v1 然后经过 e4 到 v5，然后它经过 e5 到了 v2 当然它在 v2 上，大家可以看到，它可以多打一些圈然后再经过 e6 到 v6，然后比如说我再经过 e9 到 v5 再类似地走，最后一个走到的是，终点我走到了 v7 这个点注意的是，路径和游走都是说我们的，你可以理解成我们的笔按点在这个图上的某一点，然后沿着这个图走，我的笔始终不离开只不过路径呢，是要求点和边都不能重复使用而游走的话就是说，你只要是一个合法的走的方案，也就是说不离开，不离开你原始的图的话那么就是一个正确的一个游走方案好了，我们定义了图之后这里还有一个会被反复用到的概念，是称为所谓的连通性什么是连通图呢？如果图中的任意两个点 u 和 v 之间都有一条路径的话，那么我们称它是一个连通图否则的话，我们称图是一个非连通图。我们看一个例子，就是首先下面这个图的话，我们说它是一个连通图，以 u 和 v 为例这两个点，我们说它们之间存在一条路径，从 u 走到 v，当然可能还存在其它的路径，比如说我们走这一条我们走这一条，也是可以从 u 走到 v 的，但是只要存在这样一条就可以但是我们把原始的图做一点改动，我们把我们删掉两条边，删掉的边我们用虚线表示出来，我们把这两条边删掉我们说，它现在就不是一个连通图了，因为还是说 u 和 v 而已，在新图中，也就是右边这个图中我们从 u 到 v 不存在一个路径，路径我们刚刚定义好了它是形成了两个，两个子块那么对非连通图，或者是一般的图来说，我们可以定义所谓的极大连通子图极大连通子图它要要求满足三个条件，就是首先第一它是原图的子图，第二，它是连通的，第三它已经和原图相等了，或者说你在原图你在目前的这个连通子图上再增加点或者再增加边都会破坏连通性。我们看还是刚才这个例子我们说，我们把整个理解成一张图的话，我们说它其实是有三个极大连通分支，我们分别用红色、蓝色和绿色来表示。以红色这一块为例，我们再增加任意一个点比如说绿色这个点，那么从红色任意一个点到这个绿色的点，没有路径它连通性被破坏。那么刚才我们讲的这个例子中的每一块极大连通分支呢，都称为原始图的一个连通分支当我们说，连通分支可能，可能是包含多，对一个，对非连通图来讲它连通分支必然是不是唯一的。那么给一个图，它的极大连通分支的个数呢，是用 Con 这样一个 G，这个函数来表示。还是刚才这个例子，我们说刚才这个图，它的极大连通分支个数是 3 它是包含了三个连通分支。当然我们说，如果原始的图就是一个连通图的话，那么它的那个 Con(G) 的话就是 1 但是如果是非连通图的话，那么一定是大于等于 2 好了，我们这一次课介绍最后一个概念，是所谓的树就是，注意我们现在还是讨论的是无向图那么树是什么呢？被定义为无环的连通图就原始的图，它是一个连通的，但是又不含有任何的环，那么我们给它取一个名字叫做树这里是一些树的例子。比如说，大家可以看，第二个的话大家可以看到，其实是一个，就是一个路径。路径我们说第一个点和最后一个点之间是没关系的并且它显然是连通的，因为每一个点到后一个点之间，都是有边相连然后第三个例子，大家经常被称为所谓的星型图它成为一个星的这样一个形状，它也是一个无环的一个连通图当然还有最左边，这个可能就是一棵树的样子我们说树是一类非常重要的对象，在实际中有非常广泛的应用而且我们后面会专门讲到树的性质和树有关的一些重要算法好了，本次课我们主要讲了图上的一些基本概念和一些重要的一些特殊图好，谢谢大家

Explora nuestro catálogo

Inscríbete de manera gratuita y obtén recomendaciones personalizadas, actualizaciones y ofertas.

Coursera brinda acceso universal a la mejor educación del mundo, al asociarse con las mejores universidades y organizaciones, para ofrecer cursos en línea.

© 2019 Coursera Inc. Todos los derechos reservados.

Consíguelo en Google Play

Coursera
Acerca de
Liderazgo
Empleo
Catálogo
Certificados
Certificados MasterTrack™
Grados
For Enterprise
For Government
Para el campus

Comunidad
Learners
Partners
Developers
Beta Testers
Translators

Conectar
Blog
Facebook
LinkedIn
Twitter
Instagram
Youtube
Blog de Tecnología

Más
Términos
Privacidad
Ayuda
Accesibilidad
Prensa
Contacto
Directorio
Afiliados